二叉树的性质

[ZTCooper]

1. 第 i 层上至多有 2**(i - 1) 个结点（i >= 1）
2. 深度为 k 的二叉树至多有 2**k-1 个结点（k >= 1）
3. 对任何一棵二叉树T，如果终端结点数为 n0，度为2的结点（内部结点）数为 n2，则 n0 == n2 +1
4. 具有 n 个结点的完全二叉树的深度为 [log(n,2)] + 1
5. 如果对一棵有n个结点的完全二叉树（其深度为 floor(log(n,2)) + 1 ）的结点按层序编号（从第1层到第 [log(n,2)] + 1 层，每层从左到右），则对任一结点 i 有：
   • 如果 i ==1，则结点 i 是二叉树的根，无双亲；
     如果 i > 1，则其双亲 PARENT(i) 是结点 [i/2]
   • 如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；
     否则其左孩子 LCHILD(i) 是结点 2i
   • 如果 2i + 1 > n，则结点 i 无右孩子；
     否则其右孩子 RCHILD(i) 是结点 2i + 1