【正文】 (!visited[j])) DFS(j)。 /* 邊的始點(diǎn)域 */ int endvex。 /* 頂點(diǎn)類型 */ typedef int adjtype。 ?邏輯特征是：可以有任意個(gè)開始結(jié)點(diǎn)和任意個(gè)終端結(jié)點(diǎn)，其余各個(gè)結(jié)點(diǎn)可以有任意個(gè)前趨和任意個(gè)后繼。 decode(HufmTree tree[],CodeType code[]) { /* 已知哈夫曼樹和哈夫曼編碼，對輸入的 01碼進(jìn)行譯碼 */ int i=m,b。 CodeType code[N+1]。即將 tree[i].weight賦值為 tree[p1].weight和tree[p2].weight之和； tree[i]的左指針賦值為 p1； tree[i]的右指針賦值為 p2；同時(shí)將 tree[p1]和 tree [p2]的雙親域均賦值為 i，使其指向新結(jié)點(diǎn) tree[i]，即它們在當(dāng)前森林中已不再是根結(jié)點(diǎn)。 （ 1）將給定的 8個(gè)權(quán)值作為根結(jié)點(diǎn)，構(gòu)造具有 8棵樹的森林。 BED CAHF G0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 1 6 G 2 7 H 4 2. 孩子鏈表表示法 將結(jié)點(diǎn)的所有孩子用鏈接方式存儲在一個(gè)單鏈表中，沒有孩子的結(jié)點(diǎn)后面的單鏈表為空。pltag==1) p=plchild。由于前序遍歷的次序?yàn)楦Y(jié)點(diǎn)、左子樹、右子樹，所以利用中序線索找 *p結(jié)點(diǎn)前序遍歷下的后繼的方法為： （ 1）若 *p有左孩子，則左孩子為前序后繼； （ 2）若 *p無左孩子但有右孩子，則右孩子為前序后繼； （ 3）若 *p既無左孩子也無右孩子，則沿著 *p結(jié)點(diǎn)的右線索（ qrtag=1）一直向上走，直到找到 *q結(jié)點(diǎn)， qrchild不是線索是指針（ qrtag=0），此時(shí) *(qrchild）結(jié)點(diǎn)就是 *p的前序后繼。/* 設(shè)置前趨結(jié)點(diǎn) *pre的后繼 */ if(pltag==1) plchild=pre。 線索二叉鏈表存儲結(jié)構(gòu)的 C語言描述如下： typedef char DataType。 void InOrder(BiTree *p) { SeqStack *s。 G ){ i f ( t ) { I n o r d e r ( G l c h i l d ) 。 A ){ i f ( t ) { I n o r d e r ( A l c h i l d ) 。 （ 3）后序遍歷二叉樹 —LRD 若二叉樹非空，則： 1）后序遍歷左子樹； 2）后序遍歷右子樹； 3）訪問根結(jié)點(diǎn)。 } qrear++。Q。即帶著添加的虛點(diǎn)一起將完全二叉樹中的結(jié)點(diǎn)按層序排列，按照序號將所有結(jié)點(diǎn)依次存放在一維數(shù)組中，其中根結(jié)點(diǎn)的編號為 1。 在二叉樹中，每個(gè)結(jié)點(diǎn)左子樹的根為該結(jié)點(diǎn)的 左孩子 （ Left Child），右子樹的根為該結(jié)點(diǎn)的 右孩子 （ Right Child）。若樹中每個(gè)非終端結(jié)點(diǎn)的后繼剛好為一個(gè)時(shí)，就是線性表，線性結(jié)構(gòu)是樹形結(jié)構(gòu)的一種特殊形式。數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（ C語言版）中 第五章 樹 第六章 圖 第五章 樹 ?樹形結(jié)構(gòu)的邏輯特征是：有且僅有一個(gè)開始結(jié)點(diǎn)，可有若干個(gè)終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)，可以有若干個(gè)后繼結(jié)點(diǎn)，也就是說結(jié)構(gòu)中的數(shù)據(jù)元素間存在著一對多的層次關(guān)系。 樹的遞歸定義 樹是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，也可以用遞歸的形式來定義樹，樹的遞歸定義 如下： 樹是 n（ n＞ 0）個(gè)結(jié)點(diǎn)的有限集合（記作 T），它滿足兩個(gè)條件： （ 1）有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)； （ 2）其余的結(jié)點(diǎn)可分為 m（ m≥0）個(gè)互不相交的有限集合T1， T2， … ， Tm，其中每個(gè)集合又是一棵樹，并稱其為根的子樹 （ Subtree）。 二叉樹通常有五種基本形態(tài) : 二叉樹具有以下重要的性質(zhì)： 性質(zhì) 1 二叉樹第 i層上最多有 2i1（ i≥1）個(gè)結(jié)點(diǎn)。 AFDBCEAFDBCE16 7854321 11 09下標(biāo) 0 1 2 3 4 5 6 7 8 9 10 11 結(jié)點(diǎn) A B D C E F 2． 鏈接存儲 每個(gè)結(jié)點(diǎn)除了存儲本身的數(shù)據(jù)外 ， 需要附加兩個(gè)指針域分別指向該結(jié)點(diǎn)的左孩子和右孩子 ， 這就是 二叉鏈表 。 /* 隊(duì)列 */ BiTree *root,*s。 /* 隊(duì)尾指針后移 */ qdata[qrear]=s。 AEGFDBC前 序 遍 歷 序 列 ： A B C F G D E中 序 遍 歷 序 列 ： C B G F A D E后 序 遍 歷 序 列 ： C G F B E D A編寫遞歸算法需要把握兩個(gè)方面內(nèi)容：遞歸項(xiàng)和遞歸出口 （亦稱終止條件 ） 。 p r i n t f ( A ) 。 p r i n t f ( G ) 。 s= initSeqStack()。 typedef struct Node { DataType data。 /* 設(shè)置當(dāng)前結(jié)點(diǎn) *p的前趨 */ } pre=p。 同理，根據(jù)中序線索可以找到每個(gè)結(jié)點(diǎn)后序遍歷下的前趨，從而進(jìn)行后序遍歷。 if(p) p=plchild。樹中結(jié)點(diǎn)用順序方式存儲在一個(gè)長度為 n（ n為樹中結(jié)點(diǎn)數(shù)）的數(shù)組中，數(shù)組的每一個(gè)元素由兩個(gè)域組成，一個(gè)域用來存放結(jié)點(diǎn)信息，另一個(gè)用來存放該結(jié)點(diǎn)的孩子鏈表的頭指針。 （ 2）從森林中選取根點(diǎn)權(quán)值最小的兩棵二叉樹 5，分別作為左右子樹，構(gòu)造一棵新的二叉樹，新樹根點(diǎn)權(quán)值為 8，森林中減少一棵樹。 二、哈夫曼編碼及譯碼 在進(jìn)行文字傳輸時(shí)，數(shù)據(jù)通信的發(fā)送方需要將原文中的每一個(gè)文字轉(zhuǎn)換成對應(yīng)的二進(jìn)制 0、 1序列（編碼）進(jìn)行發(fā)送，接收方接收到二進(jìn)制的 0、 1串后再還原成原文（譯碼）。 /*字符編碼數(shù)組，下標(biāo)為 0的單元空出 */ huffmanCode(HufmTree tree[],CodeType code[]) /*利用哈夫曼樹求字符的哈夫曼編碼 */ { int i,c,p。 /* tree[m]中保存的是哈夫曼樹的根， i=m表示從根點(diǎn)出發(fā)進(jìn)行譯碼 */ int endflag=1。圖中的結(jié)點(diǎn)常稱為頂點(diǎn)。 /* 權(quán)值類型 */ typedef struct { vextype vertex[n+1]。 /* 邊的終點(diǎn)域 */ int weight。} v4v1v2v5v8v6v3v70 1 1 0 0 0 0 01 0 0 1 1 0 0 01 0 0 0 0 1 1 00 1 0 0 0 0 0 10 1 0 0 0 0 0 10 0 1 0 0 0 1 00 0 1 0 0 1 0 00 0 0 1 1 0 0 0void DFSL(int i) { edgenode *p。amp。 ?邊集數(shù)組 ?鄰接表法 (Adjacency List)是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu) 1 12 35 62 23 41 0 32 35 48 63 45 51 8 1 20 1 2 3 4 5 6 7 8起 點(diǎn)終 點(diǎn)權(quán) 值（ b ）v1v2v5v4v3（ a ）581 231 861 06typedef struct edge { int fromvex。 ?無向圖中頂點(diǎn) Vi的度是鄰接矩陣 A中第 i行元素之和 ?有向圖中， ?頂點(diǎn) Vi的出度是 A中第 i行元素之和 ?頂點(diǎn) Vi的入度是 A中第 i列元素之和 ?網(wǎng)的鄰接矩陣可定義為： Wi j : i ≠ j 且 vi, vj 或 ( vi, vj) 是 E 中 的 邊0 : i = j∞ : i ≠ j 且 vi, vj 或 ( vi, vj) 不 是 E 中 的 邊ai j = A3=03∞423065∞2∞310∞605345501例v1v5v4v3v212554363網(wǎng) 絡(luò) 及 其 鄰 接 矩 陣可以得到鄰接矩陣存儲結(jié)構(gòu) C語言描述如下： define n 5 /* 圖的頂點(diǎn)數(shù) */ define e 6 /* 圖的邊數(shù) */ define max 10000 /* 設(shè)置一個(gè)極大數(shù)無窮大 */ typedef char vextype。 圖的概念 ?圖 (Graph)——是一種結(jié)點(diǎn)之間為多對多關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 然后 ， 重新從根結(jié)點(diǎn)出發(fā)繼續(xù)譯碼 ， 直到二進(jìn)制電文結(jié)束 。 /*字符 */ }CodeType 。 2）將根為 tree[p1]和 tree[p2]的兩棵樹合并，使其成為新結(jié)點(diǎn) tree[i]的左、右孩子，得到一棵以新結(jié)點(diǎn) tree[i]為根的二叉樹。 例 假設(shè)樹中葉子結(jié)點(diǎn)的權(quán)值為 {5， 29， 7， 8， 14， 23，3， 11}，構(gòu)造一棵哈夫曼樹。 BEDCAHFGBED CAHF GKIJBEDCAHFGKIJKIJ三、樹的存儲 雙親表示法 用一組連續(xù)的存儲空間（一維數(shù)組）存儲樹中的各個(gè)結(jié)點(diǎn)，數(shù)組中的一個(gè)元素存儲樹中的一個(gè)結(jié)點(diǎn)，數(shù)組元素為結(jié)構(gòu)體類型，其中包括結(jié)點(diǎn)本身的信息以及結(jié)點(diǎn)的雙親在數(shù)組中的序號，樹的這種存儲方法稱為雙親表示法。amp。 如果可以利用中序線索找到每個(gè)結(jié)點(diǎn)在前序遍歷下的前趨或后繼，便可以進(jìn)行前序遍歷。 if(pre!=NULL) /* 當(dāng)前結(jié)點(diǎn) *p有前趨（只有中序遍歷的第一個(gè)結(jié)點(diǎn)無前趨） */ { if(prertag==1) prerchild=p。 對每個(gè)指針域再附加一個(gè)標(biāo)志，當(dāng)指針域中存放的是孩子指針時(shí)，標(biāo)志為 0；當(dāng)指針域中存放的是線索時(shí)，標(biāo)志為 1。 }SeqStack。 }}I n o r d e r ( t = ∧ ){ i f ( t ) / / t 為 空 ， 返 回 { }}I n o r d e r ( t = amp。 /* 訪問根結(jié)點(diǎn) */ } } 二叉樹的中序遍歷 遞歸算法的執(zhí)行過程： I n o r d e r ( t = amp。 （ 2）中序遍歷二叉樹 —LDR 若二叉樹非空，則： 1）中序遍歷左子樹； 2）訪問根結(jié)點(diǎn)； 3）中序遍歷右子樹。 srchild=NULL。 BiTree * createTree() { SeQueue Q,*q=amp。 AB CF16 785432ED GH下標(biāo) 0 1 2 3 4 5 6 7 8 結(jié)點(diǎn) A B C D E F G H （ 2）一般二叉樹的順序存儲 一般二叉樹與完全二叉樹對照，在空缺的位置處添加虛點(diǎn)（用特殊字符，如“ ”表示），從而將一般的二叉樹擴(kuò)充成完全二叉樹，然后將擴(kuò)充后的完全二叉樹順序存儲。 當(dāng) n＞ 0時(shí)，是由一個(gè) 根結(jié)點(diǎn) 和兩棵互不相交的分別稱作這個(gè)根的 左子樹 和 右子樹 的二叉樹組成。線性結(jié)構(gòu)中每個(gè)元素的后繼最多為一個(gè)，而樹形結(jié)構(gòu)的后繼可以為多個(gè)。 ?本章首先簡單介紹樹的基本概念，然后重點(diǎn)討論二叉樹的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其運(yùn)算，線索二叉樹和線索二叉鏈表以及如何利用線索來實(shí)現(xiàn)遍歷運(yùn)算，并分析樹、森林與二叉樹之間的相互轉(zhuǎn)換問題，最后介紹二叉樹和樹的典型應(yīng)用。 樹的表示方法 除了前面介紹的樹形表示法和二元組表示法外，還有其他三種常用的表示方法：凹入表表示法、嵌套集合表示法和廣義表表示法。 性質(zhì) 2 深度為 k的二叉樹最多有 2k1（ i≥1）個(gè)結(jié)點(diǎn)。 有時(shí)為了運(yùn)算方便 ， 每個(gè)結(jié)點(diǎn)再附加一個(gè)指針域存儲雙親結(jié)點(diǎn)的指針 ， 即帶父指針的二叉鏈表 ， 也稱為 三叉鏈表 。 char ch。 /* 新結(jié)