證明樹

Question

節點（n）和滿二叉樹的高度（h）之間的關係的我有一個分配，讀取如下

證明完整的節點（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。