【正文】 這棵樹便是赫夫曼樹。 補充 1： 構(gòu)造 Huffman樹的過程描述 補充 2： 對 Huffman編碼器程序的解釋 94 怎樣生成 Huffman樹？ 步驟如下： (1) 由給定的 n 個權(quán)值 {w1, w2, …, wn}構(gòu)成 n棵二叉樹的集合（即森林） F = { T1, T2, …, Tn }，其中每棵二叉樹 Ti 中 只有一個帶權(quán)為 wi 的根結(jié)點，其左右子樹均空。 將結(jié)點的 編碼 存儲在 HC[1..n]中。 權(quán)值集合 w={7, 19, 2, 6, 32, 3, 21, 10}， 按哈夫曼樹構(gòu)造規(guī)則（合并、刪除、替換），可得到哈夫曼樹。 如果用 0～ 7的二進制編碼方案又如何？ 霍夫曼 編碼的基本思想是： 概率大的字符用短碼，概率小的用長碼 。 取 d=00， i=01， a=10， n=11 怎樣實現(xiàn) Huffman編碼？ 法 2： 不等長編碼 ，例如用哈夫曼編碼來實現(xiàn)。 ③ 把新的二叉樹加入 F。 WPL最小 Weighted Path Length 84 (1) 由給定的 n 個權(quán)值 {w0, w1, w2, …, wn1}，構(gòu)造具有 n 棵擴充二叉樹的 森林 F = { T0, T1, T2, …, Tn1 }，其中每一棵擴充二叉樹 Ti 只有一個帶有權(quán)值 wi 的根結(jié)點，其左、右子樹均為空。 81 第 6章 樹和二叉樹（ Tree amp。 樹沒有中序遍歷（因子樹不分左右） 遍歷 深度遍歷（先序、中序、后序） 廣度遍歷（層次） 78 討論：若采用 “ 先轉(zhuǎn)換，后遍歷 ” 方式，結(jié)果是否一樣？ a b d e c 先序遍歷： 后序遍歷： 中序遍歷： d e c b a a b d e c a b c d e b d c e a 1. 樹的先序遍歷二法相同； 2. 樹的 后序 遍歷相當于對應二叉樹的 中序 遍歷； 3. 樹沒有中序遍歷，因為子樹無左右之分。 左指針指向該結(jié)點的第一個孩子； 右指針指向該結(jié)點的下一個兄弟結(jié)點。 討論 3：森林如何轉(zhuǎn)為二叉樹？ 法二： 森林直接變兄弟，再轉(zhuǎn)為二叉樹 （參見教材 P138圖 ） 即 F={T1, T2, … ,Tm} B={root, LB, RB} 68 A B C D E F G H J I A B C D E F G H J I A B C D E F G H J I 森林轉(zhuǎn)二叉樹舉例： （法二） 兄弟相連 長兄為父 孩子靠左 頭根為根 69 討論 4：二叉樹如何還原為森林？ 要點： 把最右邊的子樹變?yōu)樯?，其余右子樹變?yōu)樾值? A B C D E F G H J I A B C D E F G H J I E F A B C D G H J I 即 B={root, LB, RB} F={T1, T2, … ,Tm} 70 樹和森林 1. 樹和森林與二叉樹的轉(zhuǎn)換 2. 樹和森林的存儲方式 3. 樹和森林的遍歷 71 2. 樹和森林的存儲方式 樹有三種常用存儲方式： ①雙親表示法 ②孩子表示法 ③孩子兄弟表示法 用雙親表示法來存儲 思路： 用一組 連續(xù)空間 來存儲樹的結(jié)點，同時在每個結(jié)點中 附設一個指示器 ，指示其雙親結(jié)點在鏈表中的位置。 61 二叉樹小結(jié) 定義和性質(zhì) 存儲結(jié)構(gòu) 遍歷 線索化 ：線索樹 順序結(jié)構(gòu) 鏈式結(jié)構(gòu) 二叉鏈表 三叉鏈表 先序線索樹 中序線索樹 后序線索樹 樹 二叉樹 森林 中序遍歷 后序遍歷 先序遍歷 霍夫曼樹 霍夫曼編碼 62 第 6章 樹和二叉樹（ Tree amp。prchild!=T p=prchild。 p!=T pLTag==0 p=plchild。 //當前結(jié)點右域不空 或 已經(jīng)找好了后繼 ，則一律從結(jié)點的右子樹開始重復 { }的全部過程。 //先找到中序遍歷起點 if(!visit(pdata)) return ERROR。} //p存入其前驅(qū)結(jié)點 pre的右空域 57 3. 線索二叉樹的遍歷 理論上，只要找到序列中的 第一個結(jié)點 ，然后 依次訪問結(jié)點的后繼 直到后繼為空時結(jié)束。 若 plchild＝ NULL,則 {pLtag=1。其編號之后的全部結(jié)點都是葉子了！ 故， n0=nn/2或 n(n1)/2= ?n/2? 56 線索二叉樹的生成算法 （算法 , 見教材 P134） 目的： 在 依某種順序遍歷 二叉樹時修改空指針，添加前驅(qū)或后繼。 先計算樹的深度 k=?log2n?＋ 1 =10。 52 A B C G E I D H F root 懸空？ 懸空？ 解： 該二叉樹中序遍歷結(jié)果為 : H, D, I, B, E, A, F, C, G 所以添加線索應當按如下路徑進行： 例 2： 畫出以下二叉樹對應的 中序 線索二叉樹。 兩種解決方法 增加兩個域： fwd和 bwd； 利用空鏈域（ n+1個空鏈域） 存放前驅(qū)指針 存放后繼指針 如何預存這類信息？ 例如中序遍歷結(jié)果： B D C E A F H G，實際上 已將二叉樹轉(zhuǎn)為線性排列，顯然具有唯一前驅(qū)和唯一后繼！ 可能是根、或最左（右）葉子 49 規(guī) 定： 1）若結(jié)點有左子樹，則 lchild指向其左孩子； 否則， lchild指向其直接前驅(qū) (即線索 )； 2）若結(jié)點有右子樹，則 rchild指向其右孩子； 否則， rchild指向其直接后繼 (即線索 ) 。 思考： 二叉鏈表空間效率這么低，能否利用這些空閑區(qū)存放有用的信息或線索？ ——我們可以用它來存放當前結(jié)點的直接前驅(qū)和后繼等線索，以加快查找速度。 例： 已知一棵二叉樹的 中序序列 和 后序序列 分別是 BDCEAFHG 和 DECBHGFA，請畫出這棵二叉樹。 （即順序二叉樹）。 技巧： 當根結(jié)點入隊后 ， 令其左 、 右孩子結(jié)點入隊 ， 而左孩子出隊時又令它的左右孩子結(jié)點入隊 ， …… 由此便可產(chǎn)生按層次輸出的效果 。 } 建樹 ——見教材 P131程序 42 習題討論： 1. 求二叉樹深度，或從 x結(jié)點開始的子樹深度。 Tdata=ch。T){ scanf(“%c”,amp。} DLR(rootlchild)。 DLR(Node *root) //采用中序遍歷的遞歸算法 { if ( root!=NULL ) //非空二叉樹條件 ， 還可寫成 if(root) {if(!rootlchildamp。 39 對遍歷的分析： 1. 從前面的三種遍歷算法可以知道：如果將 printf語句抹去，從遞歸的角度看，這三種算法是完全相同的，或者說這三種遍歷算法的 訪問路徑是相同的，只是訪問結(jié)點的時機不同 。 printf(“%d”,rootdata)。 LDR(rootrchild)。 //遞歸遍歷左子樹 DLR(rootrchild)。 遍歷方法 ——牢記一種約定，對每個結(jié)點的查看都是“ 先左后右 ” 。 （相應地，訪問樹中結(jié)點時也只能從根開始） 注： 如果需要倒查某結(jié)點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。 typedef struct node { int data。 而且有規(guī)律：下標值為 i的雙親，其左孩子的下標值必為2i，其右孩子的下標值必為 2i＋ 1（即性質(zhì) 5） 例如，對應 [2]的兩個孩子必為 [4]和 [5],即 B的左孩子必是 D,右孩子必為 E。 Ａ ) 高度 Ｂ ) 層次 Ｃ ) 深度 Ｄ ) 度 課堂討論： 滿二叉樹和完全二叉樹有什么區(qū)別 ？ 答： 滿二叉樹是葉子一個也不少的樹 ， 而完全二叉樹雖然前 n1層是滿的 ，但最底層卻允許在右邊缺少連續(xù)若干個結(jié)點 。 這其實是 順序 二叉樹 的含義。 2i1個 提問：第 i層上至少有 個結(jié)點？ 1 討論 2：深度為 k的二叉樹，至多有多少個結(jié)點？ （利用二進制性質(zhì)可輕松求出） 2k1 提問：深度為 k時至少有 個結(jié)點？ k 23 討論 3：二叉樹的葉子數(shù)和度為 2的結(jié)點數(shù)之間有關(guān)系嗎？ 性質(zhì) 3: 對于任何一棵二叉樹，若 2度的結(jié)點數(shù)有 n2個，則葉子數(shù)（ n0） 必定為 n2＋ 1 （即 n0=n2+1） 證明： ∵ 二叉樹中全部結(jié)點數(shù) n＝ n0+n1+n2(葉子數(shù)＋ 1度結(jié)點數(shù)＋ 2度結(jié)點數(shù) ) 又 ∵ 二叉樹中全部結(jié)點數(shù) n＝ B+1 ( 總分支數(shù)＋根結(jié)點 ) （ 除根結(jié)點外 ， 每個結(jié)點必有一個直接前趨 ， 即一個分支 ） 而 總分支數(shù) B= n