【正文】 //頂點(diǎn)數(shù)和邊數(shù)}AL。 //AdjList 是鄰接表類型typedef struct{data firstarc adjvex nextarcAdjList adjlist。 //頂點(diǎn)域ArcNode *firstarc。 //指向下一個(gè)鄰接點(diǎn)的指針域//若要表示邊上信息，則應(yīng)增加一個(gè)數(shù)據(jù)域 info}ArcNode。鄰接表表示的形式描述如下：＃define MAX_VERTEX_NUM 20 //最大頂點(diǎn)數(shù)為 20typedef struct ArcNode{ //邊表結(jié)點(diǎn)int adjvex。一種是頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域（ data）和指向第一條鄰接邊的指針域（ firstarc）構(gòu)成，另一種是邊表（即鄰接表）結(jié)點(diǎn)，它由鄰接點(diǎn)域(adjvex)和指向下一條鄰接邊的指針域(nextarc)構(gòu)成。就是對(duì)于圖 G 中的每個(gè)頂點(diǎn) vi，將所有鄰接于 vi 的頂點(diǎn) vj 鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn) vi 的鄰接表，再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。 //MGragh 是鄰接矩陣存儲(chǔ)的圖類型 鄰接表鄰接表(Adjacency List)是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。 //鄰接矩陣，即邊表int vexnum,arum。 //邊的權(quán)值設(shè)為整型typedef struct {VertexType vexs[MAX_VERTEX_NUM]。故可將其形式描述如下：define MAX_VERTEX_NUM 20 //最大頂點(diǎn)數(shù)設(shè)為 20typedef char VertexType。（ 4）用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測(cè)，所花費(fèi)的時(shí)間代價(jià)很大，這是用鄰接矩陣存儲(chǔ)圖的局限性。（ 2）對(duì)于無(wú)向圖，鄰接矩陣的第 i 行（或第 i 列）非零元素（或非∞元素）的個(gè)數(shù)正好是第 i 個(gè)頂點(diǎn)的度 TD(vi)。從圖的鄰接矩陣存儲(chǔ)方法容易看出，這種表示具有以下特點(diǎn)：（ 1）無(wú)向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。這些連通分量的生成樹(shù)就組成了一個(gè)非連通圖的生成森林。若生成樹(shù)中減少任意一條邊，則必然成為非連通的。它必定包含且僅包含 G 的 n1 條邊。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。無(wú)向圖的極大連通子圖稱為連通分量。（ 11）連通圖、連通分量：在無(wú)向圖中，如果從一個(gè)頂點(diǎn) vi 到另一個(gè)頂點(diǎn) vj(i≠j)有路徑，則稱頂點(diǎn) vi 和 vj 是連通的。除第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)之外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路，或者簡(jiǎn)單環(huán)。路徑上邊的數(shù)目稱為路徑長(zhǎng)度。（ 8）路徑、路徑長(zhǎng)度：頂點(diǎn) vp 到頂點(diǎn) vq 之間的路徑（ path）是指頂點(diǎn)序列 vp,vi1,vi2, …,vim,vq.。邊上帶權(quán)的圖稱為網(wǎng)圖或網(wǎng)絡(luò)（ network）。（ 7）邊的權(quán)、網(wǎng)圖：與邊有關(guān)的數(shù)據(jù)信息稱為權(quán)（ weight）。頂點(diǎn) v 的入度是指以頂點(diǎn)為終點(diǎn)的弧的數(shù)目，記為 ID (v)；頂點(diǎn) v 出度是指以頂點(diǎn) v 為始點(diǎn)的弧的數(shù)目，記為 OD (v)。（ 6）頂點(diǎn)的度、入度、出度：頂點(diǎn)的度（ degree）是指依附于某頂點(diǎn) v 的邊數(shù)，通常記為 TD (v)。在一個(gè)含有 n 個(gè)頂點(diǎn)的有向完全圖中，有 n(n1)條邊。在一個(gè)含有 n 個(gè)頂點(diǎn)的無(wú)向完全圖中，有 n(n1)/2 條邊。（ 2）有向圖：在一個(gè)圖中，如果任意兩個(gè)頂點(diǎn)構(gòu)成的偶對(duì)（ v,w）∈E 是有序的，即頂點(diǎn)之間的連線是有方向的，則稱該圖為有向圖。第四章 圖 圖的概念1．圖的定義圖是由一個(gè)頂點(diǎn)集 V 和一個(gè)弧集 R 構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。因?yàn)?，在哈夫曼?shù)中，每個(gè)字符結(jié)點(diǎn)都是葉結(jié)點(diǎn)，它們不可能在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的哈夫曼編碼不可能是另一個(gè)字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。在哈夫曼編碼樹(shù)中，樹(shù)的帶權(quán)路徑長(zhǎng)度的含義是各個(gè)字符的碼長(zhǎng)與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長(zhǎng)，所以采用哈夫曼樹(shù)構(gòu)造的編碼是一種能使電文代碼總長(zhǎng)最短的不等長(zhǎng)編碼。哈夫曼（ Haffman）依據(jù)這一特點(diǎn)提出了一種方法，這種方法的基本思想是：（ 1）由給定的 n 個(gè)權(quán)值{W1， W2， …， Wn}構(gòu)造 n 棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)的集合 F＝{T1， T2， …， Tn}；（ 2）在 F 中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和；（ 3）在集合 F 中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù)加入到集合 F 中；（ 4）重復(fù)（ 2）（ 3）兩步，當(dāng) F 中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是所要建立的哈夫曼樹(shù)。最優(yōu)二叉樹(shù)，也稱哈夫曼（ Haffman）樹(shù)，是指對(duì)于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)。設(shè)二叉樹(shù)具有 n 個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，記為：WPL＝ Wk 哈夫曼（ Huffman）樹(shù)和哈夫曼編碼1．哈夫曼樹(shù)的基本概念二叉樹(shù)的路徑長(zhǎng)度是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和。（ 2）中序遍歷中序遍歷的定義為：①中序遍歷第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)；②訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)；③中序遍歷去掉第一棵樹(shù)后的子森林。因此樹(shù)的遍歷算法是可以采用相應(yīng)二叉樹(shù)的遍歷算法來(lái)實(shí)現(xiàn)的。（ 2）后根遍歷后根遍歷的定義為：①按照從左到右的順序后根遍歷根結(jié)點(diǎn)的每一棵子樹(shù)。 森林和二叉樹(shù)的轉(zhuǎn)換從樹(shù)的孩子兄弟表示法可以看到，如果設(shè)定一定規(guī)則，就可用二叉樹(shù)結(jié)構(gòu)表示樹(shù)和森林，這樣，對(duì)樹(shù)的操作實(shí)現(xiàn)就可以借助二叉樹(shù)存儲(chǔ)，利用二叉樹(shù)上的操作來(lái)實(shí)現(xiàn)。struct TreeNode *next。在這種存儲(chǔ)結(jié)構(gòu)下，樹(shù)中結(jié)點(diǎn)的存儲(chǔ)表示可描述為：typedef struct TreeNode {TElemType data。3．孩子兄弟表示法這是一種常用的存儲(chǔ)結(jié)構(gòu)。}NodeType。}typedef struct {TElemType data。這種存儲(chǔ)表示可描述為：define MAXNODE 100 //樹(shù)中結(jié)點(diǎn)的最大個(gè)數(shù)typedef struct ChildNode{int childcode。2．孩子鏈表表示法孩子鏈表法主體是一個(gè)與結(jié)點(diǎn)個(gè)數(shù)一樣大小的一維數(shù)組，數(shù)組的每一個(gè)元素有兩個(gè)域組成，一個(gè)域用來(lái)存放結(jié)點(diǎn)信息，另一個(gè)用來(lái)存放指針，該指針指向由該結(jié)點(diǎn)孩子組成的單鏈表的首位置。}NodeType。其存儲(chǔ)表示可描述為：define MAXNODE 100 // 樹(shù)中結(jié)點(diǎn)的最大個(gè)數(shù)typedef struct {TElemType data。下面介紹幾種基本的樹(shù)的存儲(chǔ)方式。在此就不再討論了。}以上給出的僅是在中序線索二叉樹(shù)中尋找某結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的算法。if (prtag!=1)while (postrtag==0) post=postlchild。BiThrTree InPostNode（ BiThrTree p） {BiThrTree post。return(pre)。pre=plchild。 //右子樹(shù)線索化}}（ 2）在中序線索二叉樹(shù)上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)對(duì)于中序線索二叉樹(shù)上的任一結(jié)點(diǎn)，尋找其中序的前驅(qū)結(jié)點(diǎn)，有以下兩種情況：①如果該結(jié)點(diǎn)的左標(biāo)志為 1，那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn)；②如果該結(jié)點(diǎn)的左標(biāo)志為 0，表明該結(jié)點(diǎn)有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子為根結(jié)點(diǎn)的子樹(shù)的最右結(jié)點(diǎn)，即沿著其左子樹(shù)的右指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的右標(biāo)志為 1 時(shí)，它就是所要找的前驅(qū)結(jié)點(diǎn)。}pre=p。}if (!prerchild) { //后繼線索preRTag=1。 //左子樹(shù)線索化if (!plchild) { //前驅(qū)線索pLTag=1。}return OK。preRTag=1。InThreading(T)。 //若二叉樹(shù)為空，則左指針回指else{headlchild=T。 //建立頭結(jié)點(diǎn)headrchild=head。headLTag=0。head,BiThrTree T) {//中序遍歷二叉樹(shù) T，將其中序線索化， head 指向頭結(jié)點(diǎn)，其中 pre 為全局變量。另外，在對(duì)一棵二叉樹(shù)加線索時(shí)，必須首先申請(qǐng)一個(gè)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹(shù)的根結(jié)點(diǎn)的指向關(guān)系，對(duì)二叉樹(shù)線索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索。在遍歷過(guò)程中， Visit 操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。而原二叉樹(shù)在某序遍歷下的第一個(gè)結(jié)點(diǎn)的前驅(qū)線索和最后一個(gè)結(jié)點(diǎn)的后繼線索都指向該頭結(jié)點(diǎn)。那么，在存儲(chǔ)中，如何區(qū)別某結(jié)點(diǎn)的指針域內(nèi)存放的是指針還是線索？通常為每個(gè)結(jié)點(diǎn)增設(shè)兩個(gè)標(biāo)志位域 ltag 和 rtag，令：每個(gè)標(biāo)志位令其只占一個(gè) bit，這樣就只需增加很少的存儲(chǔ)空間。由于序列可由不同的遍歷方法得到，因此，線索樹(shù)有先序線索二叉樹(shù)、中序線索二叉樹(shù)和后序線索二叉樹(shù)三種。因此，可以利用某結(jié)點(diǎn)空的左指針域（ lchild）指出該結(jié)點(diǎn)在某種遍歷序列中的直接前驅(qū)結(jié)點(diǎn)的存儲(chǔ)地址，利用結(jié)點(diǎn)空的右指針域（ rchild）指出該結(jié)點(diǎn)在某種遍歷序列中的直接后繼結(jié)點(diǎn)的存儲(chǔ)地址；對(duì)于那些非空的指針域，則仍然存放指向該結(jié)點(diǎn)左、右孩子的指針。線索二叉樹(shù)將為二叉樹(shù)的遍歷提供許多便利，遍歷時(shí)可不需要棧，也不需要遞歸了。 線索二叉樹(shù)按照某種遍歷方式對(duì)二叉樹(shù)進(jìn)行遍歷，可把二叉樹(shù)中所有結(jié)點(diǎn)排列為一個(gè)線性序列，二叉樹(shù)中每個(gè)結(jié)點(diǎn)在這個(gè)序列中的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)中并沒(méi)有反映出來(lái)，只能在對(duì)二叉樹(shù)遍歷的動(dòng)態(tài)過(guò)程中得到這些信息。 //從棧中彈出棧頂元素p=prchild。else {printf(“棧溢出”)；return；}p=plchild； //指針指向 p 的左孩子結(jié)點(diǎn)}if (top=0) return。top==0)) {while(p!=NULL) {Visit(pdata)。while(!(p==NULLamp。if (b==NULL) return。void NRPreOrder（ BiTree b） { //非遞歸先序遍歷二叉樹(shù)BiTree Stack[MAX_TREE_SIZE],p。其過(guò)程如下：在沿左子樹(shù)深入時(shí)，深入一個(gè)結(jié)點(diǎn)入棧一個(gè)結(jié)點(diǎn)，若為先序遍歷，則在入棧之前訪問(wèn)之；當(dāng)沿左分支深入不下去時(shí)，則返回，即從堆棧中彈出前面壓入的結(jié)點(diǎn)，若為中序遍歷，則此時(shí)訪問(wèn)該結(jié)點(diǎn)，然后從該結(jié)點(diǎn)的右子樹(shù)繼續(xù)深入；若為后序遍歷，則將此結(jié)點(diǎn)再次入棧，然后從該結(jié)點(diǎn)的右子樹(shù)繼續(xù)深入，與前面類同，仍為深入一個(gè)結(jié)點(diǎn)入棧一個(gè)結(jié)點(diǎn)，深入不下去再返回，直到第二次從棧里彈出該結(jié)點(diǎn)，才訪問(wèn)之。在這一過(guò)程中，返回結(jié)點(diǎn)的順序與深入結(jié)點(diǎn)的順序相反，即后深入先返回，正好符合棧結(jié)構(gòu)后進(jìn)先出的特點(diǎn)。三種遍歷路線正是從根結(jié)點(diǎn)開(kāi)始沿左子樹(shù)深入下去，當(dāng)深入到最左端，無(wú)法再深入下去時(shí)，則返回，再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹(shù)，再進(jìn)行如此的深入和返回，直到最后從根結(jié)點(diǎn)的右子樹(shù)返回到根結(jié)點(diǎn)為止。因此，就存在如何把一個(gè)遞歸算法轉(zhuǎn)化為非遞歸算法的問(wèn)題。當(dāng)給出二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以后，用具有遞歸功能的程序設(shè)計(jì)語(yǔ)言很方便就能實(shí)現(xiàn)上述算法。if (Queue[front]rchild!=NULL) //將隊(duì)首結(jié)點(diǎn)的右孩子結(jié)點(diǎn)入隊(duì)列Queue[++rear]= Queue[front]rchild。while(front!=rear) {Visit(Queue[++front]data)。rear=0。if (b==NULL) return。void LevelOrder（ BiTree b） {BiTree Queue[MAX_TREE_SIZE]。此過(guò)程不斷進(jìn)行，當(dāng)隊(duì)列為空時(shí)，二叉樹(shù)的層次遍歷結(jié)束。由層次遍歷的定義可以推知，在進(jìn)行層次遍歷時(shí)，對(duì)一層結(jié)點(diǎn)訪問(wèn)完后，再按照它們的訪問(wèn)次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左孩子和右孩子順序訪問(wèn)，這樣一層一層進(jìn)行，先遇到的結(jié)點(diǎn)先訪問(wèn)，這與隊(duì)列的操作原則比較吻合。否則，（ 1）后序遍歷根結(jié)點(diǎn)的左子樹(shù)；（ 2）后序遍歷根結(jié)點(diǎn)的右子樹(shù)。否則，（ 1）中序遍歷根結(jié)點(diǎn)的左子樹(shù)；（ 2）訪問(wèn)根結(jié)點(diǎn)；（ 3）中序遍歷根結(jié)點(diǎn)的右子樹(shù)。 //先序遞歸遍歷 b 的左子樹(shù)lchild data rchildlchild data rchild parentPreOrder（ brchild） 。void PreOrder（ BiTree b） {if (b!=NULL){Visit（ bdata） 。1．先序遍歷先序遍歷的遞歸過(guò)程為：若二叉樹(shù)為空，遍歷結(jié)束。通過(guò)一次完整的遍歷，可使二叉樹(shù)中結(jié)點(diǎn)信息由非線性排列變?yōu)槟撤N意義上的線性序列。遍歷是二叉樹(shù)中經(jīng)常要用到的一種操作。盡管在二叉鏈表中無(wú)法由結(jié)點(diǎn)直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，因此，二叉鏈表是最常用的二叉樹(shù)存儲(chǔ)方式，本書后面所涉及到的二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不加特別說(shuō)明的都是指二叉鏈表結(jié)構(gòu)。（ 2）三叉鏈表每個(gè)結(jié)點(diǎn)由四個(gè)域組成，結(jié)點(diǎn)的存儲(chǔ)的結(jié)構(gòu)為：其中， data、 lchild 以及 rchild 三個(gè)域的意義與二叉鏈表結(jié)構(gòu)相同； parent 域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。 //左右孩子指針}BiTNode,*BiTree。struct BiTNode *lchild。結(jié)點(diǎn)的存儲(chǔ)的結(jié)構(gòu)為：其中， data 域存放某結(jié)點(diǎn)的數(shù)據(jù)信息；