第5章-樹與二叉樹(java版)-資料下載頁

　　

【正文】 //用于記從 preStr中取字符的位置 char c=( index++ )。 if (c != 39。39。) { } else root = new BiTreeNode(c)。 //建立樹的根結點 (new BiTree(preStr).root)。 // 建立樹的左子樹 (new BiTree(preStr).root)。 // 建立樹的右子樹 root = null。 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 建立二叉樹 (二叉鏈式 存儲結構 ) 3. 由標明空子樹的先根遍歷序列建 二叉樹 1. 由先根和中根遍歷序列建二叉樹 2. 由后根和中根遍歷序列建二叉樹 4. 由完全二叉樹的順序存儲結構建 立二叉鏈式存儲結構 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 完全二叉樹： 其對應的順序存儲結構： AB CD E F G01 234 5 6H7A B C D E F G0 1 2 3 4 5 6E7右孩子的編號為 由二叉樹的性質 5可知， 結點編號規則： 根結點的編號為 ？ 0 編號為 i的結點其左孩子的編號為 ？ 2i+1 ？ 2i+2 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 public BiTreeNode createBiTree(String sqBiTree,int index) { } P173/Exam5_7中 BiTreeNode root=null。 if (indexsqBitree .length()) { } root = new BiTreeNode((index))。 (creatBiTree(sqBiTree,2*i+1))。 // 建立樹的左子樹 (creatBiTree(sqBiTree,2*i+2))。 // 建立樹的右子樹 return root。 算法： 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 作業 1： 習題五中的 三、 1， 2 附加題如下： 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 1. 已知一棵度為 m的樹中有 n1個度為 1 的結點，n2個度為 2的結點， … ， nm個度為 m的結點，問該樹中有多少片葉子？ 別畫出下圖所示的二叉樹的存儲結構。 B D G F H A E C 附加題： 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 附加題： 3. 分別寫出題 2中二叉樹的先根、中根和后序根遍歷序列。 4. 已知一棵樹二叉樹的后根遍歷和中根遍歷的序列分別為： A C D B G I H F E和 A B C D E F G H I，請畫出該二叉樹，并寫出它的先根遍歷的序列。 5. 已知一棵樹二叉樹的先根遍歷和中根遍歷的序列分別為： A B D G H C E F I和 G D H B A E C I F，請畫出此二叉樹，并寫出它的后根遍的序列。 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 m的樹中有 n1個度為 1的結點， n2個度結點， ? ， nm個度為 m的結點，問該樹中有多少片葉子？ 解：設樹的總結點個數為 n, 葉子結點的個數為n0， 則 n= n0 + n1 + n2 +?+ n m ??(1) 又因為樹的總分支數為 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 附加題解答： 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 別畫出下圖所示的二叉樹的存儲結構。 ^ D ^ C ^ B ^ H ^ ^ G ^ F ^ ^ E A T A B C D E F G H 0 1 2 3 4 5 6 7 8 9 10 11 12 13 二叉鏈式存儲結構： 順序存儲結構： 附加題解答： 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 2中二叉樹的先根、中根和后序根遍歷序列。 B D G F H A E C 前根序列： ABDEGCFH 中根序列： DBGEACHF 后根序列： DGEBHFCA 附加題解答： 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 4. 已知一棵樹二叉樹的后根遍歷和中根遍歷的序列分別為： A C D B G I H F E和 A B C D E F G H I，請畫出該二叉樹，并寫出它的先根遍歷的序列。 先根遍歷序列： EBADCFHGI I B A C H G E D F 構造的二叉樹如下： 附加題解答： 數據結構（ Java語言描述 ） 二叉樹的遍歷 作業布置 結束放映 章節目錄 5. 已知一棵樹二叉樹的先根遍歷和中根遍歷的序列分別為： A B D G H C E F I和 G D H B A E C I F，請畫出此二叉樹，并寫出它的后根遍的序列。 B D G F I A H C E 后根遍歷序列： GHDBEIFCA 構造的二叉樹如下： 附加題解答： 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹的基本概念 哈夫曼樹和哈夫曼編 碼的構造方法 構造哈夫曼樹和哈夫 曼編碼類的描述 哈夫曼樹及哈夫曼編碼 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹的基本概念 結點的路徑長度 ： 結點間的路徑 ： 從一個結點到另一個結點所經歷的結點和分支序列。 從根結點到該結點的路徑上分支的數目。 結點的權 ： 在實際應用中，人們往住會給樹中的每一個結點賦予一個具有某種實際意義的數值，這個數值被稱為該結點的權值。 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹的基本概念 樹的帶權路徑長度 ： 結點的帶權路徑長度 ： 結點的路徑長度與該結點的權值的乘積。 樹中所有葉結點的帶權路徑長度之和 。 假設樹上有 n 個葉結點，通常記作 : 其中 Li為帶權 wi的葉子結點的 帶權路徑長度 。 inii LWW P L ?? ?? 1iL數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹的基本概念 最優二叉樹 ： 給定 n個權值并作為 n個葉結點按一定規則構造一棵二叉樹，使其 帶權路徑長度達到最小值 ，則這棵二叉樹被稱為 最優二叉樹。也稱 哈夫曼樹。 iL 在所有含 n 個葉子結點、并帶相同權 值的 二叉樹中，必存在一棵其 帶權路徑 長度取最小值 的樹，這樹就是“ 最優樹 ” 。 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 2 7 5 4 9 WPL(T)= 7?2+5?2+2?3+4?3+9?2 =60 WPL(T)= 7?4+9?4+5?3+4?2+2?1 =89 7 9 2 5 4 對應權值 哈夫曼樹的基本概念 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 如何構造最優樹（哈夫曼樹）呢？ 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹的基本概念 哈夫曼樹和哈夫曼編 碼的構造方法 構造哈夫曼樹和哈夫 曼編碼類的描述 哈夫曼樹及哈夫曼編碼 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹及哈夫曼編碼的構造方法 (1) 根據給定的 n 個權值 {w1, w2, …, wn}， 構造 一個由 n 棵二叉樹所構成的集合 F = {T1, T2, … , T n}， 其中每棵二叉樹中均只含一個帶權值為 wi 的根結點，其左、右子樹為空樹； 赫夫曼算法的主要步驟（ P175） 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹及哈夫曼編碼的構造 赫夫曼算法的主要步驟（ P175） (2)在二叉樹森林 F中選取根結點的權值最小和次小的兩棵二叉樹，分別把它們作為左子樹和右子樹去構造一棵新二叉樹，新二叉樹的根結點權值為其左、右子樹根結點的權值之和。 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹及哈夫曼編碼的構造方法 赫夫曼算法的主要步驟（ P175） (3) 作為新二叉樹的左、右子樹的這兩棵二叉樹從森林 F中 刪除 ，同時 加入 剛生成的新二叉樹； (4) 重復 (2) 和 (3) 兩步，直至 F 中只 含一棵二叉樹為止，則這種棵二叉樹就是所構成的哈夫曼樹。 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹及哈夫曼編碼的構造方法 9 例如 : 已知權值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹及哈夫曼編碼的構造方法 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 0 0 0 0 1 1 1 1 00 01 10 110 111 哈夫曼碼 9 5 2 7 16 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹及哈夫曼編碼的構造方法 再例如 : 書 P177的 [例 ] (由學生完成） 已知在一個信息通信聯絡中使用了 8個字符： a、 b、 c、 d、 e、 f、 g和 h，每個字符的使用頻度分別為： 1 2 4和 12，試設計各個字符的哈夫曼編碼。 問： 一棵有 n個葉子結點的哈夫曼樹共有多 少個結點？ 2*n+1 個 數據結構（ Java語言描述 ） 哈夫曼樹及哈夫曼編碼 作業布置 結束放映 章節目錄 哈夫曼樹及哈夫曼編碼的構造方法 用哈夫曼樹進行譯碼 指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。