【正文】 問： 一棵有 n個葉子結(jié)點的哈夫曼樹共有多 少個結(jié)點？ 2*n+1 個 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業(yè)布置 結(jié)束放映 章節(jié)目錄 哈夫曼樹及哈夫曼編碼的構(gòu)造方法 用哈夫曼樹進行譯碼 指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。 iL 在所有含 n 個葉子結(jié)點、并帶相同權(quán) 值的 二叉樹中，必存在一棵其 帶權(quán)路徑 長度取最小值 的樹，這樹就是“ 最優(yōu)樹 ” 。 樹中所有葉結(jié)點的帶權(quán)路徑長度之和 。 B D G F I A H C E 后根遍歷序列： GHDBEIFCA 構(gòu)造的二叉樹如下： 附加題解答： 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業(yè)布置 結(jié)束放映 章節(jié)目錄 哈夫曼樹的基本概念 哈夫曼樹和哈夫曼編 碼的構(gòu)造方法 構(gòu)造哈夫曼樹和哈夫 曼編碼類的描述 哈夫曼樹及哈夫曼編碼 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業(yè)布置 結(jié)束放映 章節(jié)目錄 哈夫曼樹的基本概念 結(jié)點的路徑長度 ： 結(jié)點間的路徑 ： 從一個結(jié)點到另一個結(jié)點所經(jīng)歷的結(jié)點和分支序列。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 m的樹中有 n1個度為 1的結(jié)點， n2個度結(jié)點， ? ， nm個度為 m的結(jié)點，問該樹中有多少片葉子？ 解：設樹的總結(jié)點個數(shù)為 n, 葉子結(jié)點的個數(shù)為n0， 則 n= n0 + n1 + n2 +?+ n m ??(1) 又因為樹的總分支數(shù)為 n1,且 n1= n1 + n2 *2+ n3 *3+?+ n m*m ??(2) (1)(2)得 1= n0– n1 2 n2 ? （ m1) nm 則： n0 = 1 + n2+2 n3+?+(m 1) nm 附加題解答： 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 別畫出下圖所示的二叉樹的存儲結(jié)構(gòu)。 算法： 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 作業(yè) 1： 習題五中的 三、 1， 2 附加題如下： 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 1. 已知一棵度為 m的樹中有 n1個度為 1 的結(jié)點，n2個度為 2的結(jié)點， … ， nm個度為 m的結(jié)點，問該樹中有多少片葉子？ 別畫出下圖所示的二叉樹的存儲結(jié)構(gòu)。 if (indexsqBitree .length()) { } root = new BiTreeNode((index))。 //建立樹的根結(jié)點 (new BiTree(preStr).root)。 //用于記從 preStr中取字符的位置 char c=( index++ )。 ( new BiTree (preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count i 1) .root )。 i count。 count表示樹中結(jié)點的個數(shù)。T2!=null) if (isEqual((),()) if (().equals(()) if (isEqual((),() return true。amp。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 實現(xiàn)步驟 :(以中根遍歷為例 ) 1)若兩棵二叉樹 都為空 ，則兩棵二叉樹相等，返回 true。 3. 求二叉樹的深度 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷應用舉例 1. 在二叉樹上的查找某個結(jié)點 2. 計算二叉樹中結(jié)點的個數(shù) 3. 求二叉樹的深度 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 要求： 實現(xiàn)方法 : 判斷根結(jié)點為 T T2的兩棵二叉樹是否相等，若相等，則返回 true；否則，返回 false。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 實現(xiàn)算法 (書 P168算法 )： public int getDepth(BiTreeNode T){ } if (T! =null) { } return 0。 return count。 ① 統(tǒng)計根結(jié)點的左子樹的結(jié)點個 數(shù)，并加入到 count變量中； ② count值加 1； ③ 統(tǒng)計根結(jié)點的 右 子樹的結(jié)點個 數(shù)，并加入到 count變量中； 2. 計算二叉樹中結(jié)點的個數(shù) 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 實現(xiàn)算法 (參看書 P167算法 )： public int countNode(BiTreeNode T){ } if (T! =null) { } count+=countNode(())。 return lresult!=null?lresult:searchNOde((),x)。 可在 先根 遍歷過程中進行查找，并將先根遍歷算法中的“ 訪問結(jié)點 ”的操作改為： 將根結(jié)點的值與 x進行比較 的操作 。 (())。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 層次遍歷的非遞歸算法 (書 P166算法 ) public void levelTraverse() { BiTreeNode T=root。 while( !()) { } T=(BiTreeNode)()。 在遍歷開始時，首先將根結(jié)點入隊，然后每次從隊列中取出隊首元素進行處理，每處理一個結(jié)點，都是先訪問該結(jié)點，再按從左到右的順序把它的孩子結(jié)點依次入隊 。 while( !()) { ② while( !()) { ③ if (!flag) break。 p=T。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 ③ 若棧非空，查看棧頂結(jié)點，若棧頂結(jié)點的右孩子為空，或者與 p相等，則將棧頂結(jié)點彈出棧并訪問它，同時使 p指向該結(jié)點，并置 flag值為 true；否則，將棧頂結(jié)點的右孩子壓入棧，并置 flag值為 false。 while( ()!=null ) { } (T)。 時間復雜度： O(n) 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 3 . 后根遍歷操作的非遞歸實現(xiàn) 方法： 借助一個棧 來記載遍歷截長過程中所經(jīng)歷的而未被訪問的所有結(jié)點 。 ()。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 中根遍歷的非遞歸算法 (書 P162算法 ) LinkStack S=new LinkStack()。 //空結(jié)點出棧 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 2 . 中根遍歷操作的非遞歸實現(xiàn) 基本步驟： ③ 棧頂結(jié)點出棧并訪問非空棧頂 結(jié)點， 再 使該棧頂結(jié)點的非空右孩子結(jié)點入棧； ④ 重復執(zhí)行步驟②和③，直到棧為空為止。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 2 . 中根遍歷操作的非遞歸實現(xiàn) 基本步驟： ① 創(chuàng)建一個棧對象，根結(jié)點入棧； ② 若棧 頂結(jié)點 非空，則將棧頂結(jié)點的非空左孩子相繼進棧； LinkStack S=new LinkStack()。 if (()!=null) (()。 T=(BiTreeNode)()。 While(T!=null) { } if (()!=null) (()。 T=(BiTreeNode)()。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 一、問題的提出 二、二叉樹遍歷方法及其遞歸實現(xiàn) 三、二叉樹遍歷方法的非遞歸實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 1 . 先根遍歷操作的非遞歸實現(xiàn) 方法： 借助一個棧 來記載當前被訪問結(jié)點的右孩子 結(jié)點。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) (序 )遍歷 (LRD)定義及遞歸實現(xiàn) 若二叉樹為空樹，則空操作；否則， （ 1）后根遍歷左子樹； （ 2）后根遍歷右子樹； （ 3）訪問根結(jié)點。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) (序 )遍歷 (LDR)定義及遞歸實現(xiàn) 若二叉樹為空樹，則空操作；否則， （ 1）中根遍歷左子樹； （ 2）訪問根結(jié)點； （ 3）中根遍歷右子樹。 A B C D E F H G K 層次遍歷序列： ABECFDGHK 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) (序 )遍歷 (DLR)定義及遞歸實現(xiàn) 若二叉樹為空樹，則空操作；否則， （ 1）訪問根結(jié)點； （ 2）先根遍歷左子樹； （ 3）先根遍歷右子樹。 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 一、問題的提出 二、二叉樹遍歷方法及其遞歸實現(xiàn) 三、二叉樹遍歷方法的非遞歸實現(xiàn) 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的遍歷 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的遍歷方法及其實現(xiàn) 二、二叉樹的遍歷方法及遞歸實現(xiàn) 對 “ 二叉樹 ” 而言 ， 可以有 三條 搜索路徑： 1． 先上后下 的遍歷； 2． 先左后右 的遍歷； 3． 先右后左 的遍歷 。 一、問題的提出 “訪問 ” 的含義可以很廣，如：輸出結(jié)點的信息等。 } …… …… 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的基本概念 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的存儲結(jié)構(gòu) — 二叉鏈表 二叉鏈表存儲結(jié)構(gòu)下二叉樹類的描述 (書中 P158) public class BiTree { } // 構(gòu)造一棵空樹 public BiTree () { =null。 // 結(jié)點的數(shù)據(jù)域 private BiTreeNode lchild, rchild。 對于完全二叉樹： 數(shù)據(jù)結(jié)構(gòu)（ Java語言描述 ） 二叉樹的基本概念 作業(yè)布置 結(jié)束放映 章節(jié)目錄 二叉樹的存儲結(jié)構(gòu) — 順序存儲 例如 (完全二叉樹）： 0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j a b c d