查詢高分資料的資料結構 二叉樹問題（重新排列等）。

一棵樹可以沒有稱為空樹的節點，並且只能有乙個根節點

一棵樹可以分為多個子樹組合，二叉樹有左子樹和右子樹。

淋巴結度：此節點的子樹數。 在上圖中，節點 1 的度數為 5，節點 2 的度數為 2。

樹的度數：所有節點度數的最大值，上圖中樹的度數為 5

葉節點：度數為 0 的節點。

層數：根節點位於第一層，根節點的子節點位於第二層。 等等。

節點深度：所有節點深度的最大值，圖中樹的深度為 4

樹的高度：所有節點高度的最大值，圖中樹的高度為 4

特徵：以下都是二叉樹。

二叉樹的特點：

所有節點均為 0 或 2

最後一層節點的度數為 0，其他節點的度數為 2

假設完整二叉樹的高度為 h（h >=1），那麼。

節點從上到下、從左到右編號，所有節點都可以對應於相同高度的完整二叉樹中的數字

下圖不是完整的二叉樹。

完整二叉樹的本質。

假設乙個完整的二叉樹的高度是 h（h >=1）。

乙個完整的二叉樹（n > 0），有 n 個節點，從上到下，從左到右編號，從 1 開始，到任意第 i 個節點

乙個完整的二叉樹（n > 0），有 n 個節點，從上到下，從左到右編號，從 0 開始，對於任何第 i 個節點

面試問題：如果一棵完整的二叉樹有768個節點，請找到葉節點的數量？

解決方案：384

假設葉節點數為 n0，度數為 1 的節點數為 n1，度數為 2 的節點數為 n2

彙總點數 n = n0 + n1 + n2，n0 = n2 + 1

所以：n = 2n0 + n1 1

完整二叉樹的 n1 為 0 或 1

當 n1 為 1 時，n = 2n0，n 必須為偶數。

葉節點數 n0 = n 2，非葉節點數 n1 + n2 = n 2

當 n1 為 0 時，n = 2n0 1，n 必須為奇數。

葉節點數 n0 = n + 1） 2，非葉節點數 n1 + n2 = n 1） 2

葉節點數 n0 = floor（ （ （ n + 1） 2 ） = ceiling（ n 2 ）

非葉節點數 n1 + n2 = floor（ n 2 ） ceiling（ （ n 1） 2 ）.

基本術語

路徑和路徑長度 樹中從乙個節點到另乙個節點的分支構成了兩個節點之間的路徑 路徑上的分支數稱為路徑長度 樹路徑的長度 從樹根到每個節點的路徑長度之和 樹的加權路徑長度 樹中所有葉節點的加權路徑長度之和表示為。

霍夫曼樹又稱最優二叉樹，是由n個樹葉節點組成的所有二叉樹中，加權路徑WPL長度最小的二叉樹。

構造霍夫曼樹

霍夫曼演算法 （ 根據給定的 n 個權重構造一組 n 個二叉樹 f= 其中每個二叉樹中只有乙個 wi 的根節點 ti 它的左右子樹是前所未有的安靜（ 在f中，選擇兩個根節點的權重作為保留最少的樹作為左右子樹，形成乙個新的二叉樹， 而新二叉樹的根節點的權重是左右子樹上根節點權重之和（ 刪除 f 中的兩棵樹，將新的二叉樹新增到 f （ ） 和 （ ） 直到 f 只包含一棵樹，該樹就是霍夫曼樹的儲存結構。

實現霍夫曼演算法。

lishixinzhi/article/program/sjjg/201311/22685