【正文】 后繼 線索： 在這種存儲結構中，指向前驅(qū)和后繼結點的指針叫做 線索 。 2. 二叉樹的線索化 【 算法思想 】 （ 1）中序線索化采用中序遞歸遍歷算法框架。 /* 線索化左子樹 */ if (rootLChild==NULL) {rootLtag=1。 preRChild==NULL) /* 置后繼線索 */ { pre RChild=root。 /*直接利用線索 */ else { /* 在 p的左子樹中查找 “ 最右下端 ” 結點 */ for(q= pLChild。 } return(pre)。 /*直接利用線索 */ else { /*在 p的右子樹中查找 “ 最左下端 ” 結點 */ for(q= pRChild。 } return(Next) } (1)在中序線索樹上求中序遍歷的第一個結點 【 算法描述 】 BiTNode * InFirst(BiTree Bt) { BiTNode *p=Bt。 } (2)遍歷中序二叉線索樹 【 算法描述 】 void TInOrder(BiTree Bt) { BITNode *p。所以在線索二叉樹中插入或刪除結點的難點在于：插入一個結點后，仍要保持正確的線索。 InsNode(BiTNode * p, BiTNode * r)表示在線索二叉樹中插入 r所指向的結點，做 p所指結點的右孩子。 p r p r 結點的右孩子為空時的插入過程為： 插入前 插入后 ② 若 p的右孩子不為空，則插入后， p的右孩子變?yōu)閞的右孩子結點， p變?yōu)?r的前驅(qū)結點， r變?yōu)?p的右孩子結點。 pRChild=r。 while(sLtag==0) s=sLChild。 /* p變?yōu)?r的前驅(qū) */ rLtag=1。 在中序線索二叉樹中刪除結點 r的過程為： r p (b) 刪除后 p r (a) )刪除前 由遍歷序列確定二叉樹 由定義，二叉樹的前序遍歷是先訪問根結點 D，其次遍歷左子樹 L，最后遍歷右子樹 R。 例：已知結點的前序序列和中序序列分別為： 前序序列： 18 14 7 3 11 22 35 27 中序序列： 3 7 11 14 18 22 27 35 則可按上述分解求得整棵二叉樹。 int parent。 /*結點數(shù) */ }ParentTree。 /* 該孩子結點在線性表中的位置 */ struct ChildNode * next。 /* 指向孩子鏈表的頭指針 */ }DataNode。 3. 孩子兄弟表示法（二叉鏈表表示法）： 鏈表中每個結點設有兩個鏈域，分別指向該結點的第一個孩子結點和下一個兄弟（右兄弟）結點。 優(yōu)點： 便于實現(xiàn)樹的各種操作。 ⑶ 以樹的根結點為軸心，將整棵樹順時針旋轉(zhuǎn)一定的角度，使之結構層次分明。由于樹的根結點沒有兄弟，所以變換后的二叉樹的根結點的右孩子必然為空。 （ 2） 若 N0， 二叉樹 B（ F） 的根為森林中第一棵樹 T1的根； B（ F） 的左子樹為 B（ {T11， … ， T1m}） ， 其中 {T11， … ， T1m}是 T1的子樹森林；B（ F） 的右子樹是 B（ {T2， … ， TN}） 。 （ 3） 整理由（ 1）、（ 2）兩步所得到的樹或森林，使之結構層次分明。 ②從左到右，依次 先根遍歷根結點的每一棵子樹。 如圖中樹的后根遍歷序列為： EBHFGCDA。 /* 訪問以 p為根的子樹 */ p = p Nextsibling。 /*先根遍歷兄弟樹 */ } } 方法二 3. 森林的遍歷 森林的遍歷方法主要有以下三種： (1)先序遍歷 若森林非空，則遍歷方法為： ① 訪問森林中第一棵樹的根結點。 ②訪問 第一棵樹的根結點。 ③訪問第一棵樹的根結點。 帶權路徑長度 ：在樹形結構中，我們把從樹根到某一結點的路徑長度與該結點的權的乘積，叫做該結點的 帶權路徑長度 。 例如：下列不同形狀的二叉樹具有最小的路徑長度 A B C D E PL=0+1+1+2+2=6 A B D C E PL=0+1+1+2+2=6 問題 2：什么樣的帶權樹路徑長度最??？ 例如：給定一個權值序列 {2,3,4,7}，可構造的多種二叉樹的形態(tài)。 (3)從 F中刪除被選中的那兩棵二叉樹，同時把新構成的二叉樹加入到森林F中。 (1)存儲結構 哈夫曼樹是一種二叉樹 ,由于哈夫曼樹中沒有度為 1的結點，則一棵有n個葉子的哈夫曼樹共有 2 n－ 1個結點，可以用一個大小為 2 n－ 1 的一維數(shù)組存放哈夫曼樹的各個結點。 */ define M 2*N1 /* 所有結點的最大值 */ typedef struct { int weight 。 /* 右孩子結點的下標 */ } HTNode, HuffmanTree[M+1]。i=n。i=m。 i++) /*創(chuàng)建非葉結點 ， 建哈夫曼樹 */ { select(ht, i1, s1, s2)。 ht [i].LChild=s1。 0 1 字符 s t a e c 字符出現(xiàn)的次數(shù) 3 8 7 5 2 按權構造哈夫曼樹的過程 如下圖： 按照創(chuàng)建哈夫曼樹的算法，對上圖建立哈夫曼樹的結果如下表： 哈夫曼編碼 哈夫曼樹最典型的應用是在編碼技術上的應用。例如，名字中的鄭霞、鄭霞錦就不是前綴碼。而哈夫曼編碼都對應終點為葉子的路徑，所以，任一哈夫曼碼都不會與任意其他哈夫曼編碼的前部分完全重疊，因此哈夫曼編碼是前綴碼。 。 即對于 n個字符，分別以它們的使用頻度為葉子權，構造哈夫曼樹，則該樹對應的哈夫曼編碼，能使各種報文（由這 n種字符構成的文本）對應的二進制串的平均長度最短。 定理 61 哈夫曼編碼是前綴碼。 例如：設有一臺模型機，共有 7種不同的指令，其使用頻率為： 指 令 I1 I2 I3 I4 I5 I6 I7 編 碼 0 1 00 01 000 001 010 指 令 I1 I2 I3 I4 I5 I6 I7 使用頻率（ pi） 變長編碼為： (1)前綴碼： 如果在一個編碼系統(tǒng)中，任一個編碼都不是其他任何編碼的前綴（最左子串），則稱該編碼系統(tǒng)中的編碼是前綴碼。 } /*哈夫曼樹建立完畢 */ } 例：傳送數(shù)據(jù)中的二進制編碼。 ht [s1].parent=i。 /*————————————初始化完畢 ！ 對應算法步驟 1—————————*/ for(i=n+1。 /* 1 ~ n號單元存放葉子結點 ， 初始化 */ m=2*n1。 */ 4. 哈夫曼樹的算法實現(xiàn) 【 算法描述 】 void CrtHuffmanTree(HuffmanTree ht, int w[ ], int n) { /*構造哈夫曼樹 ht[M+1]， w[ ]存放 n個權值 。 /* 雙親的下標 */ int LChild 。 靜態(tài)三叉鏈表中：每個結點的結構為 : 權值 雙親序號 左孩子序號 右孩子序號 各結點存儲在一維數(shù)組中， 0號單元不使用，從 1號位置開始使用。 直觀地看，在哈夫曼樹中權越大的葉子離根越近，則其具有最小帶權路徑長度。 構造哈夫曼算法的步驟如下： (1)用給定的 n個權值 {w1,w2, … ,wn}對應的 n個結點構成 n棵二叉樹的森林F={T1,T2, … ,Tn}，其中每一棵二叉樹 Ti (1≤i≤n) 都只有一個權值為 wi的根結點，其左、右子樹為空。 WPL=?wi li i=1 n 例如下圖所示的具有不同帶權路徑長度的二叉樹 WPL(a)=7 2＋ 5 2＋ 2 2＋ 4 2＝ 36 WPL(b)=4 2＋ 7 3＋ 5 3＋ 2 1＝ 46 WPL(c)=7 1＋ 5 2＋ 2 3＋ 4 3＝ 35 A B C D 7 5 2 4 (a)權為 36 C B D A 7 5 2 4 (b)權為 46 A B C D 7 5 2 4 (c)權為 35 問題 1：什么樣的二叉樹的路徑長度 PL最?。? 一棵樹的路徑長度為 0結點至多只有 1個 （ 根 ） ； 路徑長度為 1結點至多只有 2個 （ 兩個孩子 ） ； 路徑長度為 2結點至多只有 4個； 依此類推：路徑長度為 K結點至多只有 2k個 ， 所以 n個結點二叉樹其路徑長度至少等于如下序列的前 n項之和 。 路徑長度 ：指從一個結點到另一個結點所經(jīng)過的分支數(shù)目。 (3)后序遍歷 若森林非空，則遍歷方法為： ① 后序 遍歷森林中第一棵樹的根結點的子樹森林。 ③先序遍歷除去第一棵樹之后剩余的樹構成的森林。 /*訪問根結點 */ RootFirst (rootFirstChild)。 /* 訪問根結點 */ p= root FirstChild。 (2)后根遍歷 若樹非空，則遍歷方法為： ① 從左到右，依次后根遍歷根結點的每一棵子樹。 （ 2） B非空，則 F（ B）中第一棵樹 T1的根為二叉樹B的根 T； T1中根結點的子樹森林由 B的左子樹 L轉(zhuǎn)換而成，即 F（ L） ={T11,… ,T1m}； B的右子樹 R轉(zhuǎn)換為 F（ B）中其余樹組成的森林，即 F(R)＝ { T2, T3, … ,Tn}。 用遞歸的方法描述上述轉(zhuǎn)換過程： 3. 二叉樹還原為樹或森林 一棵二叉樹還原為樹或森林，具體方法為： （ 1） 若某結點是其雙親的左孩子，則把該結點的右孩子、右孩子的右孩子、 …… 都與該結點的雙親結點用線連起來。 （ 2）第一棵二叉樹不動， 從第二棵二叉樹開始，依次把后一棵二叉樹的根結點作為前一棵二叉樹根結點的右孩子，當所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。樹中某結點的第一個孩子在二叉樹中是相應結點的左孩子，樹中某結點的右兄弟結點在二叉樹中是相應結點的右孩子。 例如：右圖的樹 A B E C D F G H 將一棵樹轉(zhuǎn)換為二叉樹的方法： ⑴ 樹中所有相鄰兄弟之間加一條連線 。 /*結點信息 */ Struct CSNode *FirstChild, *Nextsibling。 /* 順序表 */ int root,num。 typedef struct /* 順序表結點的結構定義 */ { DataType data。 n個結點共有 n個孩子鏈表（葉結點的孩子鏈表為空表），而 n個結點的數(shù)據(jù)和 n個孩子鏈表的頭指針又組成一個順序表。 一棵樹可以定義為： typedef struct { TNode tree[MAX]。 雙親表示法的缺點： 在求某個結點的孩子時，需要遍歷整個向量。反過來，根據(jù)左子樹的中序序列中結點個數(shù)，又可將前序序列除根以外分成左子樹的前序序列和右子樹的前序序列兩個部分。 /* r變?yōu)?p的右孩子 */ sLChild=r。 /* p的右孩子變?yōu)?r的右孩子 */ rRtag=0。 /* p變?yōu)?r的前驅(qū) */ rLtag=1。插入過程為： p r p r 插入前 插入后 p r void InsNode(BiTNode * p , BiTNode * r) { if (pRtag==1) /* p無右孩子 */ { rRChild=pRChild。原來 p的后繼變?yōu)?r的后繼，結點 p變?yōu)?r的前驅(qū)，結點 r成為 p的右孩子。 （ 1）插入結點運算 在中序線索二叉樹中插入結點可分為兩種情況： 第一種：將 新的結點插入到二叉樹中，作某結點的左孩子； 第二種： 將新的結點插入到二叉樹中，作某結點的右孩子。 While(p) { Visit(p)。 while(pLTag==0) p=pLchild。q=qLChild )。 NULL (a)二叉樹