【正文】 return OK。 //左子樹線索化 if (!plchild){ pLTag=Thread。} //前驅(qū)線索 if (!prerchild){ preRTag=Thread。} //后繼線索 pre=p。 //右子樹線索化 } }//InThreading 第二節(jié) 線索二叉樹 第六章 樹和二叉樹 樹和森林 一、雙親表示法（順序存儲） R A D E F C B G K H R 1 A 0 B 0 C 0 D 1 E 1 F 3 G 6 H 6 K 6 0 1 2 3 4 5 6 7 8 9 數(shù)組下標(biāo) : * 便于涉及雙親的操作； * 求結(jié)點的孩子時需要遍歷整棵樹。 int parent。 typedef struct{ PTNode nodes[MAX_TREE_SIZE]。 //根的位置和結(jié)點數(shù) }PTree。 R 1 A 4 B 0 C 6 D 0 E 0 F 7 G 0 H 0 K 0 2 3 5 0 0 0 0 0 0 0 0 0 8 9 0 0 0 0 0 0 第一節(jié) 樹的存儲結(jié)構(gòu) 二、孩子表示法（順序存儲） 二、孩子表示法（順序存儲） define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data。 //第 1個孩子 位置域 int child2。 //第 d個孩子 位置域 }PTNode。 int n。 第一節(jié) 樹的存儲結(jié)構(gòu) 孩子鏈表存儲表示 R A D E F C B G K H 0 1 2 3 4 5 6 7 8 9 數(shù)組下標(biāo) : * 便于涉及孩子的操作； * 求結(jié)點的雙親時不方便。 =10。 第一節(jié) 樹的存儲結(jié)構(gòu) 孩子鏈表存儲表示（鏈式存儲） typedef struct CTNode{ //孩子結(jié)點 int child。 } *ChildPtr。 ChildPtr firstchild。 typedef struct { CTBox nodes[MAX_TREE_SIZE]。 //結(jié)點數(shù)和根的位置 }CTree。 struct CSNode *firstchild,*nextsibling。 第一節(jié) 樹的存儲結(jié)構(gòu) R A D E F C B G K H R / A / D E / / C / H / F / G / B / K / / 孩子兄弟表示法示例 ： 第一節(jié) 樹的存儲結(jié)構(gòu) 森林（ Forest）： 是 m（ m≥ 0）棵互 不相交的樹的集合 B C D E F G H I J M K L B / E F / D / J / H I / C M / / K / L / / G / / / 一、森林轉(zhuǎn)換成二叉樹 ? 如果 F={T1,T2, … ,Tm}是森林 ,則可按如下規(guī)則轉(zhuǎn)換成一棵二叉樹 B=(root,LB,RB)。 ? 其右子對 RB是從森林 F39。 ? F中除 T1之外其余樹組成的森林 F39。 第二節(jié) 森林與二叉樹的轉(zhuǎn)換 ? 樹的兩種遍歷方法： 一 、 先根遍歷： （ 1） 訪問樹的根結(jié)點； （ 2） 依次先根遍歷每棵子樹 。 （ 2）訪問樹的根結(jié)點； D E A B G H K F C R R A D E F C B G K H 第三節(jié) 樹和森林的遍歷 森林的兩種遍歷方法： 一 、 先序遍歷森林： 若森林非空 ， 則 （ 1） 訪問森林中第一棵樹的根結(jié)點； （ 2） 先序遍歷第一棵樹的根結(jié)點的子樹森林； （ 3） 先序遍歷除去第一棵樹之后的森林 。 第三節(jié) 樹和森林的遍歷 第六章 樹和二叉樹 樹的應(yīng)用 最優(yōu)二叉樹 (赫夫曼樹 ) ? 路徑長度 : 從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑 ， 路徑上的分支數(shù)目稱做路徑長度 。 第一節(jié) 赫夫曼樹及其應(yīng)用 e b a f g c d ? 樹的帶權(quán)路徑長度 : 樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點 (k)的帶權(quán)路徑長度 ωkιk之和 , ? 通常記作： n WPL= ∑ωkιk。 ? (2) 在 F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹 ,且置新的二叉樹的根結(jié)點的權(quán)值為其左 、 右子樹根結(jié)點的權(quán)值之和 。 ? (4) 重復(fù) (2)和 (3),直到 F只含一棵樹為止 。 第一節(jié) 赫夫曼樹及其應(yīng)用 構(gòu)造赫夫曼樹舉例 c d a b 7 5 2 4 a b c 2 d 4 5 7 a b c 6 d 5 7 a b c d 11 7 第一節(jié) 赫夫曼樹及其應(yīng)用 例題： 第一節(jié) 赫夫曼樹及其應(yīng)用 a b c 2 d 9 6 5 e 7 構(gòu)造赫夫曼樹 c a 5 2 7 9 6 b d e 7 b c 7 6 13 9 d c a 5 2 7 9 d c a 5 2 7 16 b c 7 6 13 9 d c a 5 2 7 16 b c 7 6 13 26 在電文傳輸中，需要將電文中出現(xiàn)的每個字符進行二 進制編碼。下面我們介紹兩種編碼的方式。 設(shè)字符集只含有 4個字符 A， B， C， D，用兩位二進制表示的編碼分別為 00， 01， 10， 11。當(dāng)接收方接收到這段電文后，將按兩位一段進行譯碼。 第二節(jié) 赫夫曼編碼 不等長編碼 在傳送電文時，為了使其二進制位數(shù)盡可能地少，可以將每個字符的編碼設(shè)計為不等長的。 第二節(jié) 赫夫曼編碼 例如，可以為 A、 B、 C、 D四個字符分別分配 0， 00， 1， 01，并可將上述電文用二進制序列： 000011010發(fā) 送，其長度只有 9個二進制位。 第二節(jié) 赫夫曼編碼 ABACCDA 不等長編碼 利用赫夫曼樹可以構(gòu)造一種不等長的二進制編碼，并且構(gòu)造所得的 赫夫曼編碼 是一種 最優(yōu)前綴編碼 ， 即使所傳 電文的總長度最短 。 赫夫曼編碼 第二節(jié) 赫夫曼編碼 （ 1）利用字符集中每個字符的使用頻率作為權(quán)值構(gòu)造一個赫夫曼樹； （ 2）從根結(jié)點開始，為到每個葉子結(jié)點路徑上的左分支賦予 0，右分支賦予 1，并從根到葉子方向形成該葉子結(jié)點的編碼。 為方便計算，將所有字符的頻度乘以 100，使 其轉(zhuǎn)換成整型數(shù)值集合，得到 {5,29,7,8,14,23, 3,11}； 赫夫曼編碼設(shè)計如下圖： 第二節(jié) 赫夫曼編碼 11 5 29 7 8 14 23 3 100 0 1 15 58 29 0 0 0 1 1 1 8 42 19 0 0 0 1 1 1 00 010 0110 0111 1110 1111 110 10 赫夫曼樹的存儲結(jié)構(gòu) 用一個大小為 2n1的向量來存儲赫夫曼樹中的結(jié)點， 其存儲結(jié)構(gòu)為： typedef struct { //結(jié)點類型 int weight； //權(quán)值，不妨設(shè)權(quán)值均大于零 int lchild， rchild， parent； //左右孩子及雙親指針 }HTNode， *HuffmanTree。 。HT/*HF樹 */, int n /*n個字符 */ HuffmanCode amp。 m=2*n1 /*HF樹所需空間總數(shù) */ 。 for(p=HT+1,i=1。++i,++p,++w) *p={*w,0,0,0} //初始化 HF樹 ,并填入初始值 for(。++i,++p) *p={0,0,0,0} //將葉子結(jié)點以外的結(jié)點初始化為 0 for(i=n+1； i=m； i++){ //建立 HF樹 SelectMin(HT， i1， s1， s2)； //選出權(quán)值最小的兩個結(jié)點 s1,s2 HT[s1].parent=i。 cd=(char *)malloc(n*sizeof(char *))。i=n。f!=0。 else cd[start]=“1”。 strcpy(Hc[i]， amp。 }//Huffmancoding 求赫夫曼編碼的算法 : 小 結(jié) 1. 熟練掌握 二叉樹的結(jié)構(gòu)特性 ，了解相應(yīng)的證明方法。 3. 遍歷二叉樹 是二叉樹各種操作的基礎(chǔ)。掌握各種遍歷策略的 遞歸算法 ， 靈活運用遍歷算法 實現(xiàn)二叉樹的其它操作。 小 結(jié) 4. 理解二叉樹 線索化的實質(zhì) 是建立結(jié)點與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的 線索化過程 以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。 小 結(jié) 5. 熟悉 樹的 各種 存儲結(jié)構(gòu) 及其特點，掌握 樹和森林與二叉樹的轉(zhuǎn)換 方法。 6. 學(xué)會編寫 實現(xiàn)樹的各種操作 的算法。 謝 謝！