binary-tree - 完全二叉树的节点（n）和高度（h）之间的关系证明

Question

我的作业内容如下

证明Full Binary Tree的节点(n)与高度(h)的关系为2^h=(n+1)/2。

我尝试了以下方法：

n = 2^(h+1)-1

n+1 = 2^(h+1)

n+1 = 2^h*2

所以

2^h=(n+1)/2

我知道这不可能那么简单。这就是我问的原因。

Answer 1

你从哪里得到 n = 2^(h+1)-1 ？如果你认为这个公式是理所当然的，那么就没有多少可以证明的了！

这种类型的锻炼通常通过归纳来解决。以下是步骤：

• 证明它适用于基本情况，h = 0。通常完全微不足道。
• 假设它适用于固定高度，即公式适用于 h = k
• 证明（在上述假设下）它对 h = k+1 成立。