前置知识：

[1] 树结构基础概念

简而言之，二叉树就是度最大为2的树。

什么是二叉树？

  • 每个结点最多有2棵子树； 即可以有0~2棵子树。
  • 左子树和右子树是有序的。
  • 即使某个结点只有1棵子树，也要区分左右子树。

image.png

二叉树的性质

  1. 非空二叉树的第 i 层，最多有 😄二叉树 - 图2 个结点( i >= 1 )。
  2. 高度为 h 的二叉树上，最多有 😄二叉树 - 图3 个结点( h >= 1 )。
  3. 对于任何一棵非空的二叉树，如果叶子结点的个数为n0，度为2的结点个数为n2，则有n0 = n2 + 1；

真二叉树

所有结点的度要么为0，要么为2。

满二叉树

所有结点的度要么为0，要么为2。所有叶子结点必须在最后一层。

完全二叉树

叶子结点只出现在最后两层，且最后1层的叶子结点都靠左对齐。这样的二叉树称为完全二叉树。

完全二叉树具备以下性质：

  1. 度为1的结点只有左子树。
  2. 度为1的结点要么是1个，要么是0个。
  3. 同样结点数量的二叉树，完全二叉树的高度最小。
  4. 假设完全二叉树的高度为h（ h >= 1），那么至少有 😄二叉树 - 图4 个结点，最多有 😄二叉树 - 图5 个结点(满二叉树)。
  5. 一棵有n个结点的完全二叉树( n > 0 ) , 从上到下、从左到右对结点从1开始编号，对任意第 i 个结点：
    • 如果 i = 1 ，它是根结点。
    • 如果 i > 1 ,它的父结点编号为 floor( i / 2 )。
    • 如果 2i <=n ,它的左子结点编号为2i。
    • 如果 2i > n , 它无左子结点
    • 如果 2i + 1 <= n , 它的右子结点编号为 2i + 1。
    • 如果 2i + 1 > n ,它无右子结点。