二叉樹算法

二叉樹算法

二叉樹的每個結點至多只有二棵子樹(不存在度大於2的結點),二叉樹的子樹有左右之分,次序不能顛倒。二叉樹的第i層至多有2^(i − 1)個結點;深度為k的二叉樹至多有2^k − 1個結點;對任何一棵二叉樹T,如果其終端結點數為n0,度為2的結點數為n2,則n0 = n2 + 1。二叉樹算法常被用於實現二叉查找樹和二叉堆。

基本信息

概念

二叉樹是每個節點最多有兩個子樹的有序樹。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)。二叉樹常被用於實現二叉查找樹和二叉堆。

基本形態

二叉樹也是遞歸定義的,其結點有左右子樹之分,邏輯上二叉樹算法有五種基本形態:

(1)空二叉樹——(a)

(2)只有一個根結點的二叉樹——(b);

(3)右子樹為空的二叉樹——(c);

(4)左子樹為空的二叉樹——(d);

(5)完全二叉樹——(e)

注意:儘管二叉樹與樹有許多相似之處,但二叉樹不是樹的特殊情形。

性質

(1) 在二叉樹中,第i層的結點總數不超過2^(i-1);

(2) 深度為h的二叉樹最多有2^h-1個結點(h>=1),最少有h個結點;

(3) 對於任意一棵二叉樹,如果其葉結點數為N0,而度數為2的結點總數為N2,則N0=N2+1;

(4) 具有n個結點的完全二叉樹的深度為int(log2n)+1

(5)有N個結點的完全二叉樹各結點如果用順序方式存儲,則結點之間有如下關係:若I為結點編號則 如果I>1,則其父結點的編號為I/2;

如果2*IN,則無左兒子;

如果2*I+1N,則無右兒子。

(6)給定N個節點,能構成h(N)種不同的二叉樹。h(N)為卡特蘭數的第N項。h(n)=C(n,2*n)/(n+1)。

相關詞條

熱門詞條

聯絡我們