完全二叉树#

备忘: 在所有的笔记中, 树都是从1开始编号(根结点为1, 不存在0为编号的结点). 并且除法为计算机中的整除(手算除法并且向下取整).

1. 下标为$1~n/2$的结点均为分支结点(出度>0), 而$(n/2+1)~n$为叶子结点(出度=0).

   • 从这个结论也可以得出, 对于完全二叉树来说叶子结点和分支结点是对半开的.

2. 完全二叉树只存在一个度为1的结点(我称之为分界结点):

   • 此结点一定是最后一个分支结点.
   • 它的编号一定为$n/2$.
   • 它必定只有左孩子(优先删除右孩子, 优先生长左孩子).
   • 它前面的结点全都是分支. 后者全都是叶子.

3. 当$n_总$为奇数, 树为完满二叉树(所有结点都有两个孩子).

4. 当$n_总$为偶数, 第$n/2$结点只有左孩子.

5. 完全二叉树的叶子节点只可能存在于倒数俩层.

   • 假设最大层数为$h_m$, 则叶子结点只可能出现在$h_m~(h_m-1)$层. (完全二叉树只能从最大结点开始有顺序地删除).

6. $i$ 结点的双亲为 $i/2$. 左孩子为 $2*i$ 右孩子为 $2*i+1$

7. 关于所有m叉树性质的继承 -结点 i 必定有 $2^(h_i-1)=i$.