在二叉樹的葉節點的

我已閱讀，葉節點的在高度爲h的樹的數目至少爲H + 1在二叉樹的葉節點的

但是如下所示在PIC

樹的高度爲2，但葉節點的數量僅爲2（至少），而不是3.我錯在哪裏？

2011-02-05 Vikram

高度爲h的樹中樹葉的數量至少爲h + 1的說法顯然是錯誤的 - 只考慮長度爲h的鏈表，它只有一個葉節點。無論你讀的源是不正確的，還是對樹的結構做了一些額外的假設。

編輯：有可能是原始證據說樹中至少有h + 1個空指針。正如我們通過歸納可以看出的那樣，這種說法的確如此。作爲基本情況，單節點樹的高度爲0並有兩個NULL指針，所以聲明對於h = 0成立。對於歸納步驟，假設對於所有高度h爲h'的樹並且考慮任何樹身高h。它的一個子樹必須具有高度h - 1，歸納假設必須具有h NULL指針。現在考慮另一個子樹。如果沒有其他子樹，則根貢獻（h + 1）st NULL指針，我們完成了。否則，有一個高度爲k的子樹，因此歸納假設至少有（NULL）指針，所以樹本身至少有h + 1個NULL指針，完成證明。

來源

2011-02-05 08:33:14 templatetypedef

您發表的聲明是真實的，當且僅當你談論的是一個完美的二叉樹：

一個完美的二叉樹是一個完整的二進制樹中的所有葉子都在同一深度或同級別

來源

2011-02-05 08:36:22 Jakob

我知道這是舊的，但萬一別人遇到這裏，找到了葉：（N - 1） - （N/2）其中n =節點總數。在這種情況下，這是（4 - 1） - （4/2）= 3 - 2 = 1

來源

2013-05-09 05:07:26 LeftOnTheMoon

但它不適用於此，例如：http://imgur.com/dv40hJt – 2016-06-07 06:06:09

在二叉樹的葉節點的

回答

相關問題