首頁 > 常見問題 > 主體

二元樹的5個性質

藏色散人
發布: 2019-06-05 09:37:03
原創
14329 人瀏覽過

二元樹的5個性質

二元樹有以下五個性質: 

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中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板