二叉樹演算法思想

Ⅰ 求二叉樹高度的原理、演算法是什麼，越詳細越好，C語言，謝謝

首先分析二叉樹的深度（高度）和它的左、右子樹深度之間的關系。從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，演算法中「訪問結點」的操作為：求得左、右子樹深度的最大值，然後加
1
。
int
Depth
(BiTree
T
){
//
返回二叉樹的深度
if
(
!T
)
depthval
=
0;
else
{
depthLeft
=
Depth(
T->lchild
);
depthRight=
Depth(
T->rchild
);
depthval
=
1
+
(depthLeft
>
depthRight
?
depthLeft
:
depthRight);
}
return
depthval;
}

Ⅱ 最優二叉樹演算法基本概念

最優二叉樹，也被稱為哈夫曼樹，是一種特殊的二叉樹結構，其目標是在一組帶權的葉節點中，構建出具有最小帶權路徑長度的樹。帶權路徑長度，是對二叉樹路徑長度概念的擴展，它指的是從根節點到所有葉節點的路徑長度之和，每個路徑長度與對應節點的權值相乘。記為：WPL = Wk·Lk，其中Wk表示第k個葉節點的權值，Lk是其路徑長度。

舉個例子，如圖所示的二叉樹，其帶權路徑長度WPL計算為2×2+4×2+5×2+3×2=28。對於一組特定的葉節點，例如權值為1，3，5，7，可以構建出多種不同形態的帶權二叉樹，每種樹的帶權路徑長度都會有所不同。如圖中的5種二叉樹，它們的帶權路徑長度分別是：

• (a) WPL = 1×2+3×2+5×2+7×2 = 32


• (b) WPL = 1×3+3×3+5×2+7×1 = 29


• (c) WPL = 1×2+3×3+5×3+7×1 = 33


• (d) WPL = 7×3+5×3+3×2+1×1 = 43


• (e) WPL = 7×1+5×2+3×3+1×3 = 29

最優二叉樹演算法的任務就是，在給定的帶權葉節點集合中，找出這樣一個二叉樹，它的帶權路徑長度是最小的，即它是最優的二叉樹。這樣的演算法在數據壓縮、編碼等領域中有著廣泛應用。

Ⅲ 二叉樹演算法是什麼

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

性質

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

2、深度為h的二叉樹最多有2^h-1個結點（h>=1)，最少有h個結點。

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