二叉树

二叉树(binary tree，简写 BT)是一种度数为 2 的树，即二叉树的每个节点最多有两个子节点。每个节点的子节点分别称为左孩子、右孩子，它的两棵子树分别称为左子树、右子树。

二叉树的性质

• 在二叉树的第 i 层上最多有 $2^{i-1}$ 个节点( i ≥ 1 )。

• 深度为 k 的二叉树至多有 $2^{k} - 1$ 个节点( k ≥ 1 )。

• 对任意一棵二叉树，如果其叶节点数为 $n_0$，度为 2 的节点数为$n_2$,则一定满足 $n_0 = n_2 + 1$。

• 具有 n 个节点的完全二叉树的深度为 $floor(log_2 n) + 1$ 。

• 具有 n 个节点的二叉树的高度至少为 $log_2(n+1)$

• 对于一棵 n 个节点的完全二叉树的任一个节点(编号为 i )，有以下关系：

  • 如果 i = 1，则节点 i 为根，无父节点；如果 i > 1，则其父节点编号为 i/2。
  • 如果 2 * i > n,则节点 i 无左孩子，否则左孩子编号为 2 * i。如果 2 * i + 1 > n，则节点 i 无右孩子，否则右孩子编号为 2 * i + 1。
    

二叉树的形态

满二叉树（也叫完美二叉树，perfect binary tree）

在一棵二叉树中，如果所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上，这样的一棵二叉树称之为满二叉树。

性质

• 叶子只能出现在最下一层；
• 非叶子节点一定有两个孩子；
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子最多。
  

完全二叉树（complete binary tree）

对一棵树中的节点按从上至下、从左至右的顺序进行编号，如果每个节点的编号都与该位置在满二叉树中的编号相同，则称该树为完全二叉树。

性质

• 叶子结点只能出现在最下两层；
• 最下层若有叶子节点，一定集中在左侧；
• 倒数第二层若有叶子节点，一定集中在右侧；
• 如果节点只有1个孩子，则该孩子为左孩子；
• 同样节点数的二叉树，完全二叉树的深度最小。
  

完整二叉树（proper binary tree）

每个节点的子节点数量均为 0 或者 2 的二叉树。