二元樹有以下五個性質:
1. 在二元樹的第i(i>=1)層最多有2^(i - 1)個結點。
2. 深度為k(k>=0)的二元樹最少有k個結點,最多有2^k-1個結點。
3. 任一非空二元樹,若其葉結點數為n0,度為2的非葉結點數為n2,則n0 = n2 +1。
4. 具有n個結點的完全二元樹的深度為int_UP(log(2,n 1))。
5. 若將一棵有n個結點的完全二元樹自頂向下,同一層自左向右連續給結點編號1,2,3,. . . . . . ,n,然後按此結點編號將樹中各結點順序的存放於一個一維數組,並簡稱編號為i的結點為結點i( i>=1 && i<=n),則有以下關係:
(1)若i= 1,則結點i為根,無父結點;若i> 1,則結點i 的父結點為結點int_DOWN(i / 2 );
(2)若2*i <= n,則結點i 的左子女為結點2*i;
(3)若2*i<=n=n ,則結點i的右子女為結點2*i+1;
(4)若結點編號i為奇數,且i! =1,它處於右兄弟位置,則它的左兄弟為結點i-1;
(5)若結點編號i為偶數,且i! =n,它處於左兄弟位置,則它的右兄弟為結點i+1;
(6)結點i所在的層次為 int_DOWN(log(2,i))+1。
部分性質的證明
性質1可以透過數學歸納法來證明
性質2證明:
由性質1可知,k層的最大節點總數可表示為2^0+2^ 1+…+2^ (k-1) = 2^k-1;
#3證明:
##########C由節點的角度看n1+n2+n0=n,設此為(1)式; ######再從邊的角度看,n2下接兩邊,n1下接一條邊,n個節點相連需要n-1條邊,可得2*n2+n1=n-1,此為(2)式; ######由(1)式-(2)式,可得 ######由(1)式(2)式,可得 ####5# -n2=1。 ###以上是二元樹的5個性質的詳細內容。更多資訊請關注PHP中文網其他相關文章!