二叉樹算法

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

基本介紹

• 中文名：二叉樹算法
• 套用學科：數據結構 
• 性質：第i層的結點總數不超過2^(i-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)。