【正文】 當由葉子走到根結(jié)點時，完成一個葉子結(jié)點編碼的求取。 若 di≠d j(字符不同 )，則對應(yīng)的樹葉不同，因為從根到每個葉子的路徑是不同的，所以一條路徑不可能是另一條路徑的前部（前綴），因此哈夫曼編碼是前綴碼。 例：若要傳輸如下單詞 state, seat, act, tea, cat, set, a, eat 如何使所傳送的信息編碼長度最短？ 為保證信息編碼長度最短，先統(tǒng)計各字符出現(xiàn)的次數(shù)，然后以此作為權(quán)值 , 構(gòu)造哈夫曼樹。 三、 哈夫曼編碼 平均長度最短的編碼一般為不等長編碼，為使各編碼間無需加分界符即可識別，其編碼應(yīng)是 前綴碼。amp。 *s2=*s1。jpos。 ht[i].RChild=s2。 ht[i].weight=ht[s1].weight+ht[s2].weight。i=m。 ht[i].Parent=0。 } m=2*n1。i++) /*葉子結(jié)點初始化 */ { ht[i].weight=w[i]。 建哈夫曼樹的過程是：反復在數(shù)組中選雙親為 0(表示它們當前是樹根 )且權(quán)值最小的兩結(jié)點 , 將它們作為左右孩子掛在新的結(jié)點之下 , 新結(jié)點權(quán)值為左右孩子權(quán)值之和。 int parent， Lchild， Rchild 。 97 二、如何構(gòu)造最優(yōu)樹 （哈夫曼算法） Step 1: 根據(jù)給定的 n 個權(quán)值 {w1, w2, …, w n}， 構(gòu)造 一個具有 n 棵二叉樹的森林 F = {T1, T2, … , T n}， 其中每棵二叉樹中均 只含一個帶權(quán)值為 wi 的根結(jié)點 ，其左、右子樹為空樹； Step 2:在 F 中選取其 根結(jié)點的權(quán)值為最小和次小的兩棵二叉樹 ，分別作為左、右子樹構(gòu)造一棵新的二叉樹，并置這棵 新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和 ； Step 3: 從 F中刪去這兩棵樹 ,同時加入剛生成的新樹； Step 4: 重復 2 和 3 兩步 ,直至 F 中只含一棵樹為止。 94 例如下圖所示的三棵二叉樹 WPL(a)=7 2＋ 5 2＋ 2 2＋ 4 2＝ 36 其帶權(quán)路徑長度分別為： 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(b)=4 2＋ 7 3＋ 5 3＋ 2 1＝ 46 WPL(c)=7 1＋ 5 2＋ 2 3＋ 4 3＝ 35 95 什么樣的樹的帶權(quán)路徑長度 WPL最?。? 例如：給定一個權(quán)值序列 {2, 4, 5, 7}，可構(gòu)造多種二叉樹的形態(tài) : 問題： 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(a) ＝ 36 WPL(b) ＝ 46 WPL(c)＝ 35 其帶權(quán)路徑長度分別為： 96 在各種形態(tài)的含有 n個葉子結(jié)點的 二 叉樹中 , 必存在一棵 (幾棵 )其 帶權(quán)路徑長度值 WPL 最小 的樹，被稱為“ 最優(yōu)二叉樹 ” 。 樹的路徑長度： 樹中每個結(jié)點與根之間的路徑 長度之和 （ PL） 。這在通訊領(lǐng)域是極其有價值的。 還原 ：將各棵孤立的二叉樹按二叉樹還原為一般樹的方法還原為樹。 87 二叉樹 → 樹 舉例： A B E D H C F G 加線 ：若某結(jié)點 i是雙親結(jié)點的左孩子，則將該結(jié)點的右孩子以及當且僅當連續(xù)地沿著此右孩子的右鏈 不斷搜索到的所有右孩子都分別與結(jié)點 i的 雙親用虛線連起來 。 83 樹 → 二叉樹 舉例： A B C D G E F H A B E D H C F G 在同胞兄弟之間加 虛線 ； 保留結(jié)點與 左邊第一個 孩子之間的連線，去掉其余連線； 順時針旋轉(zhuǎn) 45度。 78 樹與二叉樹均可用 二叉鏈表 作為存儲結(jié)構(gòu)，則以二叉鏈表為媒介可導出樹與二叉樹之間的一個對應(yīng)關(guān)系 —— 即給定一棵樹，可以找到唯一一棵二叉樹與之對應(yīng) 。 二、孩子鏈表表示法 : 76 data firstchild A B C D E F G 6 4 5 1 2 3 0 A 1 B 2 C 3 D 4 E 5 F 6 G 孩子結(jié)點結(jié)構(gòu) : child nextchild 雙親結(jié)點結(jié)構(gòu)： data firstchild 77 typedef struct CSNode{ Elem data。 雙親表示法的缺點： 求某個結(jié)點的孩子時，需要遍歷整個表。但是，給定結(jié)點的遍歷序列，卻不能唯一確定一棵二叉樹！ ? 由遍歷序列確定二叉樹 二叉樹的先序序列 二叉樹的中序序列 左子樹 左子樹 右子樹 右子樹 根 根 那么，給定一棵二叉樹結(jié)點的先序序列和中序序列，能否唯一確定一棵二叉樹呢？ 66 二叉樹先序遍歷是先訪問根結(jié)點 D,即 第一結(jié)點必是根 ；另一方面，中序遍歷是先左子樹，其次是根，最后是右子樹，則 根結(jié)點 D將中序序列分割成兩部分 ： D之前是左子樹結(jié)點的中序序列，D之后是右子樹結(jié)點的中序序列。 pLChild=CreateBiTree()。 ch=getchar()。假如 在遍歷二叉樹時，我們使用某個特定的符號表示空子樹，則稱得到的序列為擴展的結(jié)點序列 。 depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight)。 首先分析 二叉樹的深度 和它的 左 、 右子樹深度 之間的關(guān)系。 LeafCount=L+R。amp。 } } 方法一：設(shè)全局變量 LeafCount計葉子結(jié)點數(shù)目， 調(diào)用前賦初值為 0 56 方法二：空樹：返回 0；葉子結(jié)點，返回 1； 否則為左右子樹的葉子結(jié)點數(shù)之和 。 leaf(rootRChild)。 /* 先序遍歷左子樹 */ PreOrder(root RChild)。 53 輸出二叉樹中的葉子結(jié)點 void PreOrder(BiTree root) /* 先序遍歷輸出二叉樹中葉結(jié)點 , root為二叉樹根結(jié)點的指針 */ { if (root!=NULL) {if (root LChild==NULL amp。 52 void Preorder (BiTree root) { if (root!=NULL) { printf(“%c”,rootdata)。 /*后序遍歷右子樹 */ Visit(root data)。 /*中序遍歷左子樹 */ Visit(root data)。 43 A B C D E F G H K 例如： 先序序列： 中序序列： 后序序列： A B C D E F G H K B D C A E H G K F D C B H K G F E A 44 a b c d e f g h i j 又如 : 先序遍歷 : a b d h i e j c f g 中序遍歷 : h d i b j e a f c g 后序遍歷 : h i d j e b f g c a 45 用二叉樹表示表達式 + / a * e f b c d 先序 : +a*bcd/ef 中序 : a+b*cde/f 后序 : abcd*+ef/ 三個序列恰好為它的 前綴、 中綴、 后綴 表示式 原式 :a+b*(cd)e/f 46 三、遍歷算法的遞歸描述 先序遍歷 void PreOrder(BiTree root) /*先序遍歷二叉樹 , root為二叉樹根結(jié)點的指針 */ { if (root!=NULL) {Visit(root data)。 一、遍歷的含義 非線性的樹 線性化的 結(jié)點訪問序列 遍歷 遍歷目的： 二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，遍歷時存在 如何遍歷 的問題，即按什么樣的 規(guī)律 (搜索路徑 )訪問結(jié)點 ? 37 對 “ 二叉樹 ” 而言 ， 可以有三條搜索路徑： ? 1． 先上后下 的按層次遍歷； ? 2． 先左 （ 子樹 ） 后右 （ 子樹 ） 的遍歷； ? 3． 先右 （ 子樹 ） 后左 （ 子樹 ） 的遍歷 。 struct Node *rchild。 lchild data rchild 結(jié)點結(jié)構(gòu) : C 語言的類型描述如下 : 33 root A D E B C F ? ? ? ? ? ? ? ? 2． 三叉鏈表 34