資料結構二叉樹問題的解決，資料結構樹和二叉樹的一些問題

根據您在二叉樹中要求的屬性，例如，如果它是二叉排序樹，那麼插入的邏輯應該是：

insert（node* root， node* elem）if （root == null） { 如果為空，則 elem 應該是根。

root = elem；

root->left = null;

root->right = null;

return ;

if(elem->data <= root->data) {insert(root->left, elem);插入左側子樹。

else {

insert（root->right,elem);插入右側子樹。

分類： 計算機網路 >> 程式設計 >>其他程式語言.

問題描述： 具體來說，解體過程：

1.具有 10 個節點的二叉樹具有 （b） 度為 2 的節點。

如果是5000個節點，如何解決？

2.設給定權重的總數為n，山禪霍夫曼樹的節點總數為：（）我忘記了答案，看完就編了。

a.不確定。

3.如果二叉樹採用二叉漫畫光束塵埃鍊表儲存結構，並且要交換分支節點左右的位置，最合適的答案是用（）遍歷方法回去補足。

a.序言 b中階 c後記 D按級別。

4.為什麼每個節點最多有兩個子樹的有序樹不是二叉樹？

請具體說明。

5.左子樹為空的二叉樹中空鏈場的個數為（d）在前一行的渣線連線後

a.不確定。

6.左子樹和右子樹都不是空的二叉樹是 （c） 在預購線索之後

a.不確定。

7.線索二叉樹是 （c） 結構。

a.邏輯 b邏輯和儲存 c物理D線性。

我想是一對夫婦認為我錯了，所以我會告訴你。

8.以下哪乙個二叉樹滿足該屬性：從任一節點到根的路徑上的節點序列按其關鍵字 （d） 排序。

a.二元排序樹 b霍夫曼樹 D堆。

就算是淘汰，D怎麼對呢？

分析：這是我以前學到的，但我有點忘記了我要給你寫我理解的答案。

第乙個應該是b，第二個是n-1，第三個忘了，上面有人說d，可以參考一下。

第四個似乎是二叉樹的定義，第5個或第6個應該是c，因為每個二叉樹都有乙個空的鏈場，第7個是c，第8個b應該不對，因為霍夫曼樹的公式是2/2（n-1）。

如果有錯誤，請包括在內，畢竟我已經很久沒有做過了，詳情可以問老師

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

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

淋巴結度：此節點的子樹數。 在上圖中，節點 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 （n 0） 個節點的有限集合。 n=0 稱為空樹。 在任何非空樹中：

二叉樹是一組 n 個節點，這些節點要麼是空樹 （n=0），要麼是非空樹，對於非空樹 t：

二叉樹和樹之間的區別：

二叉樹每個節點最多有兩個子樹。

二叉樹的子樹分為左樹和右樹，順序不能任意顛倒。

2.鏈式儲存結構：節點包含三個域：資料域和左右指標。

遍歷二叉樹意味著樹中的每個節點都由搜尋路徑訪問，因此每個節點被訪問一次，並且只訪問一次。 遍歷的本質是線性化二叉樹的過程。

rtag：0->rchild 字段指示節點的正確子節點。

1-> rchild 字段表示節點的後繼節點。

由於線索的二叉樹結構的本質是將二叉鍊表中的空指標指向前體或後續線索，而前體或後繼者的資訊只能在遍歷過程中獲得，因此線索的過程就是在遍歷過程中修改空指標的過程。

由於根節點沒有父節點，我們同意，如果根節點的位置字段設定為 -1，則每個節點都有其父節點的位置。

基本術語

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

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

構造霍夫曼樹

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

實現霍夫曼演算法。

lishixinzhi/article/program/sjjg/201311/22685