完全二叉树

1. 定义:

按层序遍历, 不能出现结点中断

1.1. 2. 直观理解: 以下都得满足

1. 叶结点只能出现在最后两层
2. 结点分支先排满左边

2. 性质:

1. 同样结点的树, 完全二叉树的深度最小
2. 对有n个结点, 则深度为$\lfloor lo{g}_{2}n\rfloor$+1(⭐)
3. 完全二叉树去掉最后一层, 就是满二叉树
4. 结点总数 ⇒ 三种结点的数量
   1. 先由结点总数 ⇒ 度为1的结点数
      1. 利用完全二叉树的结点总数奇偶性
   2. 再由结点总数 ⇒ 度为2的结点数
      1. 利用二叉树的性质
   3. 由以上信息 ⇒ 度为0的结点数
5. 结点总数 ⇒ 最后一层的结点数量
   1. 结点总数 ⇒ 深度
   2. 深度 ⇒ 去掉最后一层后的结点数
      1. 利用满二叉树的性质
6. 按层序编号, 则i结点的左子树为2i, 右子树为2i+1(⭐)
7. (⭐)度为1的结点数量= 总结点为奇数 > 1 总结点为偶数 > 0
   1. 推论: 度为1的结点数 + 叶结点总数 == 结点总数/2
8. 度为1的结点如果存在, 则该结点必定只有左子树