java - 二叉树

image

ZERO

    持续更新 请关注：https://zorkelvll.cn/blogs/zorkelvll/articles/2019/01/13/1547385493734

背景

    本文主要是记录在学习 Java - 二叉树 过程中的一些知识点备忘！

一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树

1、节点

节点是数据结构中的基础概念，是构成复杂数据结构的基本组成单位

2、树

树Tree是n(>=0)个节点的有限集；n=0时称为空树；在任意一棵非空树中：

• 有且仅有一个特定的称为根Root的节点
• 当n>1时，其余节点可分为m(>0)个互不相交的有限集T1、T2、……、Tn,其中每一个集合本身又是一棵树，并且称为根的子树

此外，树的定义还需要强调以下两点：

• n>0时根节点是唯一的，不可能存在多个根节点，数据结构中的树只能有一个根节点
• m>0时，子树的个数没有限制，但它们一定是互不相交的

树中节点的度：节点拥有的子树数目称为节点的度

树中节点关系：节点子树的根节点为该节点的孩子节点，相应地该节点称为孩子节点的双亲节点

同一个双亲节点的孩子节点之间互称兄弟节点

树中节点层次：从根开始定义起，根为第一层，根的孩子为第二层，以此类推

树的深度：树中节点的最大层次数称为树的深度或高度

3、二叉树

https://www.jianshu.com/p/bf73c8d50dc2
https://juejin.im/post/5ab5a01d518825555c1d9a24