計算二叉樹內部節點

Question

我可以找到一個有關全二叉樹的問題。

完整的二叉樹是一棵有根樹，其中每個內部節點只有兩個孩子。有500個葉子的完整二​​叉樹中有多少個內部節點？

我感覺答案250請解釋

Answer 1

任取兩片葉子，並結合他們創造一個內部節點。現在，你可以增加一個內部節點的數量，並刪除兩個使用過的葉子，它們比新葉子中的內部節點變換。

因此，如果我們呼叫f(n)有n個葉子的內部節點的數量，先前的參數會導致我們到f(n) = 1 + f(n - 1)，其中f(2) = 1。因此，f(n) = n - 1。

因此，對於500的結果爲499。

Answer 2

如果滿二叉樹（T）具有500種的葉子（L），則內部節點的數量是I = L - 1，即I = 500 - 1。

Result is 499.