二元樹的5個性質

二元樹有以下五個性質： 

1. 在二元樹的第ｉ（ｉ>=１）層最多有２＾(ｉ - １)個結點。 

2. 深度為k(k>=0)的二元樹最少有k個結點，最多有２＾ｋ－１個結點。 

3. 任一非空二元樹，若其葉結點數為n0，度為2的非葉結點數為n2，則ｎ0 = ｎ2 ＋１。 

4. 具有n個結點的完全二元樹的深度為int_UP（log(2，ｎ 1)）。 

5. 若將一棵有n個結點的完全二元樹自頂向下，同一層自左向右連續給結點編號１，２，３，． ． ． ． ． ． ，ｎ，然後按此結點編號將樹中各結點順序的存放於一個一維數組，並簡稱編號為i的結點為結點i（ ｉ>=１ && ｉ<=ｎ）,則有以下關係： 

（1）若ｉ= 1，則結點i為根，無父結點；若ｉ> 1，則結點i 的父結點為結點int_DOWN（ｉ / ２ ); 

（2）若２＊ｉ <= ｎ，則結點ｉ 的左子女為結點２＊ｉ； 

（3）若２＊ｉ＜＝ｎ＝ｎ ，則結點ｉ的右子女為結點２＊ｉ＋１； 

（4）若結點編號ｉ為奇數，且ｉ！ ＝１，它處於右兄弟位置，則它的左兄弟為結點ｉ－１； 

（5）若結點編號ｉ為偶數，且ｉ！ ＝ｎ，它處於左兄弟位置，則它的右兄弟為結點ｉ＋１； 

（6）結點ｉ所在的層次為 int_DOWN（log（2，ｉ））＋１。

部分性質的證明

性質１可以透過數學歸納法來證明

性質２證明： 

由性質１可知，ｋ層的最大節點總數可表示為２＾０＋２＾ 1＋…＋２^ (ｋ－１) = ２^ｋ-１；

#３證明： 

##########C由節點的角度看ｎ１＋ｎ２＋ｎ０＝ｎ，設此為（１）式； ######再從邊的角度看，ｎ２下接兩邊，ｎ１下接一條邊，ｎ個節點相連需要ｎ－１條邊，可得２＊ｎ２＋ｎ１＝ｎ－１，此為（２）式； ######由（１）式－（２）式，可得 ######由（１）式（２）式，可得 ####５# －ｎ２＝１。 ###

以上是二元樹的5個性質的詳細內容。更多資訊請關注PHP中文網其他相關文章！