二叉树，关于数字计算的高频考点

二叉树

1. 叶子节点等于分支节点数+1，即 t0 =t₂ + 1

2. 第 i 层至多有2^(i-1)个节点

3. 高度为n，最多含有2ⁿ - 1个节点

4. 节点数等于总度数加一，即 t = d + 1

满二叉树：

1. 高度为n，含有2ⁿ - 1个节点
2. 层序从1开始，节点 i 的左孩子为 2i，右孩子为
   2i + 1，父节点为 i/2

完全二叉树：

左上补满

1. 节点数目为 t
   t/2 向小取整，若
   i <= t/2 为分支节点
   i >= t/2 为叶子节点

2. 高度为n的完全二叉树，最少有2^(n-1)个节点，
   最多含有2ⁿ - 1个节点

3. 完全二叉树最多只有一个度为1的节点，
   即t₁ = 0或t₁ = 1

    	若完全二叉树有偶数（2k）个节点，则必有
    	t0 = k, t₁ = 1, t₂ = k-1
    	若完全二叉树有奇数（2k-1）个节点，则必有
    	t0 = k, t₁ = 0, t₂ = k-1
   1
   2
   3
   4

4. 求完全二叉树高度 n = ㏒₂(t+1) 向大取整
   或 n = ㏒₂t+1 向小取整