二叉樹屬性 - 平衡

Question

我想了解二叉樹屬性。但我不確定一件事：

def。二進制樹指出：

1. 二叉樹是平衡的，如果每個節點就認爲，內部節點的左子樹的數量和內部節點的右子樹的數量至多1不同

2. 如果任何兩個葉子差異，則二叉樹是平衡的。的深度是最多1.

我問我是否這兩個def。是相當的，我的意思是確定。 1統計Def。 2，反之亦然？ ......對我來說似乎是......但是誰能夠用例子來解釋這個屬性的（非）等價關係？

感謝， 帕特里克

Answer 1

不，這兩者是不等價的。

3 
/\ 
    2 7 
//\ 
1 5 8 
/\ \ 
    4 6 9 

是滿足財產2一棵樹，而不是財產1.

屬性1意味着財產2，但是。

主張：在對根據屬性1 n內部節點平衡二進制樹中，所有葉子都在深度

• k如果n = 2^k - 1
• k或k+1如果2^k <= n < 2^(k+1)-1，和有深度爲k+1的葉子。

證明：（通過感應在內部節點的數目）

對於n = 1 = 2^1-1，有在深度1一個或兩個葉片（根是在深度0）。

對於n = 2，一個子樹有一個內部節點，在該子樹的所有葉子都在深度爲2，其他子樹爲空或在深度葉1

讓n >= 2並考慮二叉樹是平衡根據屬性1與n+1內部節點。

如果n是偶數，n = 2*m，兩個子樹必須有m內部節點，深度屬性由歸納假設保持。

如果n = 2*m+1是奇數，則一個子樹具有m內部節點，另一個m+1。

1. 如果2^k <= m < 2^(k+1)-1，與m內部節點的子樹的葉子具有在深度k+1，並且可能在離開由感應假設深度k。具有m+1內部節點的樹也具有深度k+1並且可能（如果m+1 < 2^(k+1)-1）在深度k處離開。

2. m = 2^k - 1如果與m內部節點的子樹僅在深度k有葉，並用m+1內部節點的子樹的葉子具有在深度k+1和可能的深度k。