二叉树的性质 ~

• 非空二叉树的第 i 层，最多有2 ^i-1 个结点（ i ≥1 ）

推导：满二叉树中第一层有一个结点，即根结点，第二层有两个结点，第三层有四个结点，第四层有八个结点 …
以此类推，第 i 层，最多有2 ^i-1 个结点

• 在高度为 h 的二叉树上最多有2 ^h -1个结点 （ h ≥1 ）

推导：等比数列求和公式：首项 x（1 - 公比 ⁿ ）/（1 - 公比）
而在非空二叉树当中，公比 = 2，首项 = 1，而 n 则为二叉树的高度（或深度）
so：结点总数 = 1 x（1 - 2 ^h ）/（1 - 2），化简后得：2 ^h -1

• 对于任何一棵非空二叉树，如果叶子结点的个数为 n₀ ，度为 2 的结点个数为 n₂ ，则有：n₀ = n₂ + 1

推导：假设对于一棵非空二叉树，叶子结点的个数为 n₀，度为 1 的结点的个数为 n₁ ，度为 2 的结点的个数为 n₂，则
总结点数= n₀ + n₁ + n₂ ，总边数= n₁ + 2n₂
而每个结点上都对应一条边，除了根节点
so：总结点数 -1 = 总边数 —> n₀ + n₁ + n₂ -1 = n₁ + 2n₂ —> n₀ = n₂ + 1