二叉树的概念、分类和性质

1、二叉树的概念

二叉树：每个节点最多有两个分支（分支的度小于2）的树结构，可为空树。
根节点：一棵树最上面的节点称为根节点。
左右子树：某个节点的左分支叫做左子树，右分支叫做右子树。
左右孩子：某个节点的左、右分支的根节点叫做该节点的左、右孩子。
兄弟节点：具有相同父节点的节点互为兄弟节点。
节点的度：节点拥有的子树数。
叶子节点：没有任何子节点的节点称为叶子节点。
内部节点：非叶子节点称为内部节点。
根的层次：从根节点开始定义，根为第一层，根的孩子为第二层，如此计数，直到该结点为止。
树的深度和高度：二叉树中节点的最大层次称为二叉树的深度或高度。

2、二叉树的分类

1）、完全二叉树

在一棵二叉树中，除了最后一层，都是满的，并且最后一层或者是满的，或者是右边缺少连续若干节点，成为完全二叉树。如图所示：

2）、满二叉树

一棵深度为k，并且有$2^{k+1}-1$2k+1−1个节点的二叉树，成为满二叉树。如图所示：

3）、二叉查找树(Binary Search Tree)

又称为二叉搜索树，排序二叉树，可为空树，或节点满足左子树所有节点<跟节点<右子树所以节点，不存在相等值的节点，如图所示：

4）、平衡二叉树（Balanced Binary Tree）

是一种结构平衡的二叉搜索树，即叶子节点深度差不超过1，能够在O(logn)内完成插入、查找和删除操作,结构如图所示，常见的平衡二叉树有AVl树、红黑树等。

5）、AVL树

又被称为高度平衡树，是最先发明的自平衡二叉查找树，任何节点的两个儿子子树的高度最大差别为1，增加和删除可能需要通过一次或多次树旋转来重新平衡这个树，树图如图所示。

平衡前（非AVL树）：

平衡后（AVL树）：

6）、红黑树（Red-black tree）

是一种自平衡二叉查找树，又称为“对称二叉B树”，除了满足所有二叉查找树的要求之外还需要满足以下要求：

（1）节点是红色或者是黑色的

（2）跟节点是黑色的

（3）每个叶子节点都是黑色的（叶子是NIL节点）

（4）每个红色节点必须有两个黑色节点（从叶子到根节点的所有简单路径上不可能有两个连续的红色节点）

（5）从任一节点到其每个叶子的所有简单路径都饱和相同数目的节点

注:

NIL节点就是空节点，二叉树中庸NIL节点代替NULL

简单路径：指顶点序列中顶点不重复出现的路径

3、二叉树的性质

性质1：在非空二叉树的第i层上最多有$2^{i-1}$2i−1个节点。

性质2：深度为K的二叉树最多有$2^k-1$2k−1个节点。

性质3：对于任意一棵二叉树，如果度为0的节点个数为$n_0$n0​，度为2的节点个数为$n_2$n2​，则$n_0 = n_2 +1$n0​=n2​+1。

性质4：具有n个节点的完全二叉树的深度$k =\lfloor log_2n\rfloor+1$k=⌊log2​n⌋+1。

性质5：对于含n个节点的完全二叉树中编号为i（1$\leq$≤i$\leq$≤n）的节点：

1. 如果i=1，则i节点是这可完全二叉树的根，没有双亲，否则其双亲的编号为$\lfloor i/2\rfloor$⌊i/2⌋。
2. 如果2i>n，则i节点没有左孩子，否则其左孩子的编号为2i。
3. 如果2i+1>n,则i节点没有右孩子，否则其有孩子的编号为2i+1。