【正文】 是它的后繼結(jié)點(diǎn)；②如果該結(jié)點(diǎn)的右標(biāo)志為 0，表明該結(jié)點(diǎn)有右孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)的子樹的最左結(jié)點(diǎn)，即沿著其右子樹的左指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的左標(biāo)志為 1 時(shí)，它就是所要找的后繼結(jié)點(diǎn)。BiThrTree InPostNode（ BiThrTree p） {BiThrTree post。post=prchild。if (prtag!=1)while (postrtag==0) post=postlchild。return(post)。}以上給出的僅是在中序線索二叉樹中尋找某結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的算法。在前序線索二叉樹中尋找結(jié)點(diǎn)的后繼結(jié)點(diǎn)以及在后序線索二叉樹中尋找結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)可以采用同樣的方法分析和實(shí)現(xiàn)。在此就不再討論了。 樹和森林 樹的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，樹的存儲(chǔ)有多種方式，既可以采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，但無論采用何種存儲(chǔ)方式，都要求存儲(chǔ)結(jié)構(gòu)不但能存儲(chǔ)各結(jié)點(diǎn)本身的數(shù)據(jù)信息，還要能唯一地反映樹中各結(jié)點(diǎn)之間的邏輯關(guān)系。下面介紹幾種基本的樹的存儲(chǔ)方式。1．雙親表示法由樹的定義可以知道，樹中的每個(gè)結(jié)點(diǎn)都有唯一的一個(gè)雙親結(jié)點(diǎn)，根據(jù)這一特性，可用一組連續(xù)的存儲(chǔ)空間（一維數(shù)組）存儲(chǔ)樹中的各個(gè)結(jié)點(diǎn)，數(shù)組中的一個(gè)元素表示樹中的一個(gè)結(jié)點(diǎn)，數(shù)組元素為結(jié)構(gòu)體類型，其中包括結(jié)點(diǎn)本身的信息以及結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的序號，樹的這種存儲(chǔ)方法稱為雙親表示法。其存儲(chǔ)表示可描述為：define MAXNODE 100 // 樹中結(jié)點(diǎn)的最大個(gè)數(shù)typedef struct {TElemType data。int parent。}NodeType。NodeType t[MAXNODE]。2．孩子鏈表表示法孩子鏈表法主體是一個(gè)與結(jié)點(diǎn)個(gè)數(shù)一樣大小的一維數(shù)組，數(shù)組的每一個(gè)元素有兩個(gè)域組成，一個(gè)域用來存放結(jié)點(diǎn)信息，另一個(gè)用來存放指針，該指針指向由該結(jié)點(diǎn)孩子組成的單鏈表的首位置。單鏈表的結(jié)構(gòu)也由兩個(gè)域組成，一個(gè)存放孩子結(jié)點(diǎn)在一維數(shù)組中的序號，另一個(gè)是指針域，指向下一個(gè)孩子。這種存儲(chǔ)表示可描述為：define MAXNODE 100 //樹中結(jié)點(diǎn)的最大個(gè)數(shù)typedef struct ChildNode{int childcode。struct ChildNode *nextchild。}typedef struct {TElemType data。struct ChildNode *firstchild。}NodeType。NodeType t[MAXNODE]。3．孩子兄弟表示法這是一種常用的存儲(chǔ)結(jié)構(gòu)。在樹中，每個(gè)結(jié)點(diǎn)除其信息域外，再增加兩個(gè)分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)的指針。在這種存儲(chǔ)結(jié)構(gòu)下，樹中結(jié)點(diǎn)的存儲(chǔ)表示可描述為：typedef struct TreeNode {TElemType data。struct TreeNode *son。struct TreeNode *next。}NodeType。 森林和二叉樹的轉(zhuǎn)換從樹的孩子兄弟表示法可以看到，如果設(shè)定一定規(guī)則，就可用二叉樹結(jié)構(gòu)表示樹和森林，這樣，對樹的操作實(shí)現(xiàn)就可以借助二叉樹存儲(chǔ)，利用二叉樹上的操作來實(shí)現(xiàn)。 樹和森林的遍歷1．樹的遍歷（ 1）先根遍歷先根遍歷的定義為：①訪問根結(jié)點(diǎn)；②按照從左到右的順序先根遍歷根結(jié)點(diǎn)的每一棵子樹。（ 2）后根遍歷后根遍歷的定義為：①按照從左到右的順序后根遍歷根結(jié)點(diǎn)的每一棵子樹。②訪問根結(jié)點(diǎn)；根據(jù)樹與二叉樹的轉(zhuǎn)換關(guān)系以及樹和二叉樹的遍歷定義可以推知，樹的先根遍歷與其轉(zhuǎn)換的相應(yīng)二叉樹的先序遍歷的結(jié)果序列相同；樹的后根遍歷與其轉(zhuǎn)換的相應(yīng)二叉樹的中序遍歷的結(jié)果序列相同。因此樹的遍歷算法是可以采用相應(yīng)二叉樹的遍歷算法來實(shí)現(xiàn)的。（ 1）前序遍歷前序遍歷的定義為：①訪問森林中第一棵樹的根結(jié)點(diǎn)；②前序遍歷第一棵樹的根結(jié)點(diǎn)的子樹；③前序遍歷去掉第一棵樹后的子森林。（ 2）中序遍歷中序遍歷的定義為：①中序遍歷第一棵樹的根結(jié)點(diǎn)的子樹；②訪問森林中第一棵樹的根結(jié)點(diǎn)；③中序遍歷去掉第一棵樹后的子森林。根據(jù)森林與二叉樹的轉(zhuǎn)換關(guān)系以及森林和二叉樹的遍歷定義可以推知，森林的前序遍歷和中序遍歷與所轉(zhuǎn)換的二叉樹的先序遍歷和中序遍歷的結(jié)果序列相同。 哈夫曼（ Huffman）樹和哈夫曼編碼1．哈夫曼樹的基本概念二叉樹的路徑長度是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長度之和。如果二叉樹中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可將這一概念加以推廣。設(shè)二叉樹具有 n 個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度，記為：WPL＝ WkLk其中 Wk 為第 k 個(gè)葉結(jié)點(diǎn)的權(quán)值， Lk 為第 k 個(gè)葉結(jié)點(diǎn)的路徑長度。最優(yōu)二叉樹，也稱哈夫曼（ Haffman）樹，是指對于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹。由相同權(quán)值的一組葉子結(jié)點(diǎn)所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長度，那么如何找到帶權(quán)路徑長度最小的二叉樹（即哈夫曼樹）呢？根據(jù)哈夫曼樹的定義，一棵二叉樹要使其 WPL 值最小，必須使權(quán)值越大的葉結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。哈夫曼（ Haffman）依據(jù)這一特點(diǎn)提出了一種方法，這種方法的基本思想是：（ 1）由給定的 n 個(gè)權(quán)值{W1， W2， …， Wn}構(gòu)造 n 棵只有一個(gè)葉結(jié)點(diǎn)的二叉樹，從而得到一個(gè)二叉樹的集合 F＝{T1， T2， …， Tn}；（ 2）在 F 中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新的二叉樹根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和；（ 3）在集合 F 中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合 F 中；（ 4）重復(fù)（ 2）（ 3）兩步，當(dāng) F 中只剩下一棵二叉樹時(shí)，這棵二叉樹便是所要建立的哈夫曼樹。在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符 0， 1 組成的二進(jìn)制串，稱之為編碼。在哈夫曼編碼樹中，樹的帶權(quán)路徑長度的含義是各個(gè)字符的碼長與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長，所以采用哈夫曼樹構(gòu)造的編碼是一種能使電文代碼總長最短的不等長編碼。然而，采用哈夫曼樹進(jìn)行編碼，則不會(huì)產(chǎn)生上述二義性問題。因?yàn)?，在哈夫曼樹中，每個(gè)字符結(jié)點(diǎn)都是葉結(jié)點(diǎn)，它們不可能在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的哈夫曼編碼不可能是另一個(gè)字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。求哈夫曼編碼，實(shí)質(zhì)上就是在已建立的哈夫曼樹中，從葉結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步，就走過了哈夫曼樹的一個(gè)分支，從而得到一位哈夫曼碼值，由于一個(gè)字符的哈夫曼編碼是從根結(jié)點(diǎn)到相應(yīng)葉結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的 0， 1 序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。第四章 圖 圖的概念1．圖的定義圖是由一個(gè)頂點(diǎn)集 V 和一個(gè)弧集 R 構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。；（ 1）無向圖：在一個(gè)圖中，如果任意兩個(gè)頂點(diǎn)構(gòu)成的偶對（ v,w）∈E 是無序的，即頂點(diǎn)之間的連線是沒有方向的，則稱該圖為無向圖。（ 2）有向圖：在一個(gè)圖中，如果任意兩個(gè)頂點(diǎn)構(gòu)成的偶對（ v,w）∈E 是有序的，即頂點(diǎn)之間的連線是有方向的，則稱該圖為有向圖。（ 3）無向完全圖：在一個(gè)無向圖中，如果任意兩頂點(diǎn)都有一條直接邊相連接，則稱該圖為無向完全圖。在一個(gè)含有 n 個(gè)頂點(diǎn)的無向完全圖中，有 n(n1)/2 條邊。（ 4）有向完全圖：在一個(gè)有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個(gè)含有 n 個(gè)頂點(diǎn)的有向完全圖中，有 n(n1)條邊。（ 5）稠密圖、稀疏圖：若一個(gè)圖接近完全圖，稱為稠密圖；稱邊數(shù)很少（ enlogn）的圖為稀疏圖。（ 6）頂點(diǎn)的度、入度、出度：頂點(diǎn)的度（ degree）是指依附于某頂點(diǎn) v 的邊數(shù)，通常記為 TD (v)。在有向圖中，要區(qū)別頂點(diǎn)的入度與出度的概念。頂點(diǎn) v 的入度是指以頂點(diǎn)為終點(diǎn)的弧的數(shù)目，記為 ID (v)；頂點(diǎn) v 出度是指以頂點(diǎn) v 為始點(diǎn)的弧的數(shù)目，記為 OD (v)。TD (v)=ID (v)＋OD (v)。（ 7）邊的權(quán)、網(wǎng)圖：與邊有關(guān)的數(shù)據(jù)信息稱為權(quán)（ weight）。在實(shí)際應(yīng)用中，權(quán)值可以有某種含義。邊上帶權(quán)的圖稱為網(wǎng)圖或網(wǎng)絡(luò)（ network）。如果邊是有方向的帶權(quán)圖，則就是一個(gè)有向網(wǎng)圖。（ 8）路徑、路徑長度：頂點(diǎn) vp 到頂點(diǎn) vq 之間的路徑（ path）是指頂點(diǎn)序列 vp,vi1,vi2, …,vim,vq.。其中，（ vp,vi1）， (vi1,vi2)， …,(vim,.vq)分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長度。（ 9）簡單路徑、簡單回路：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡單路徑。除第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)之外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡單回路，或者簡單環(huán)。（ 10）子圖：對于圖 G=（ V， E）， G’=（ V’， E’），若存在 V’是 V 的子集 ， E’是 E 的子集，則稱圖 G’是 G 的一個(gè)子圖。（ 11）連通圖、連通分量：在無向圖中，如果從一個(gè)頂點(diǎn) vi 到另一個(gè)頂點(diǎn) vj(i≠j)有路徑，則稱頂點(diǎn) vi 和 vj 是連通的。如果圖中任意兩頂點(diǎn)都是連通的，則稱該圖是連通圖。無向圖的極大連通子圖稱為連通分量。（ 12）強(qiáng)連通圖、強(qiáng)連通分量：對于有向圖來說，若圖中任意一對頂點(diǎn) vi 和 vj(i≠j)均有從一個(gè)頂點(diǎn) vi 到另一個(gè)頂點(diǎn) vj 有路徑，也有從 vj 到 vi 的路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。（ 13）生成樹：所謂連通圖 G 的生成樹，是 G 的包含其全部 n 個(gè)頂點(diǎn)的一個(gè)極小連通子圖。它必定包含且僅包含 G 的 n1 條邊。在生成樹中添加任意一條屬于原圖中的邊必定會(huì)產(chǎn)生回路，因?yàn)樾绿砑拥倪吺蛊渌栏降膬蓚€(gè)頂點(diǎn)之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。（ 14）生成森林：在非連通圖中，由每個(gè)連通分量都可得到一個(gè)極小連通子圖，即一棵生成樹。這些連通分量的生成樹就組成了一個(gè)非連通圖的生成森林。 圖的存儲(chǔ)及基本操作 鄰接矩陣所謂鄰接矩陣存儲(chǔ)結(jié)構(gòu)，就是用一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，用矩陣表示圖中各頂點(diǎn)之間的鄰接關(guān)系。從圖的鄰接矩陣存儲(chǔ)方法容易看出，這種表示具有以下特點(diǎn)：（ 1）無向圖的鄰接矩陣一定是一個(gè)對稱矩陣。因此，在具體存放鄰接矩陣時(shí)只需存放上（或下）三角矩陣的元素即可。（ 2）對于無向圖，鄰接矩陣的第 i 行（或第 i 列）非零元素（或非∞元素）的個(gè)數(shù)正好是第 i 個(gè)頂點(diǎn)的度 TD(vi)。（ 3）對于有向圖，鄰接矩陣的第 i 行（或第 i 列）非零元素（或非∞元素）的個(gè)數(shù)正好是第 i 個(gè)頂點(diǎn)的出度 OD(vi)（或入度 ID(vi)）。（ 4）用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對每個(gè)元素進(jìn)行檢測，所花費(fèi)的時(shí)間代價(jià)很大，這是用鄰接矩陣存儲(chǔ)圖的局限性。在用鄰接矩陣存儲(chǔ)圖時(shí)，除了用一個(gè)二維數(shù)組存儲(chǔ)用于表示頂點(diǎn)間相鄰關(guān)系的鄰接矩陣外，還需用一個(gè)一維數(shù)組來存儲(chǔ)頂點(diǎn)信息，另外還有圖的頂點(diǎn)數(shù)和邊數(shù)。故可將其形式描述如下：define MAX_VERTEX_NUM 20 //最大頂點(diǎn)數(shù)設(shè)為 20typedef char VertexType。 //頂點(diǎn)類型設(shè)為字符型typedef int VRType。 //邊的權(quán)值設(shè)為整型typedef struct {VertexType vexs[MAX_VERTEX_NUM]。 //頂點(diǎn)表VRType edges[MAX_VERTEX_NUM][ MAX_VERTEX_NUM]。 //鄰接矩陣，即邊表int vexnum,arum。 //頂點(diǎn)數(shù)和邊數(shù)}MGragh。 //MGragh 是鄰接矩陣存儲(chǔ)的圖類型 鄰接表鄰接表(Adjacency List)是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖 G 中的每個(gè)頂點(diǎn) vi，將所有鄰接于 vi 的頂點(diǎn) vj 鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn) vi 的鄰接表，再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)，如圖所示。一種是頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域（ data）和指向第一條鄰接邊的指針域（ firstarc）構(gòu)成，另一種是邊表（即鄰接表）結(jié)點(diǎn)，它由鄰接點(diǎn)域(adjvex)和指向下一條鄰接邊的指針域(nextarc)構(gòu)成。對于網(wǎng)圖的邊表需再增設(shè)一個(gè)存儲(chǔ)邊上信息（如權(quán)值等）的域（ info）。鄰接表表示的形式描述如下：＃define MAX_VERTEX_NUM 20 //最大頂點(diǎn)數(shù)為 20typedef struct ArcNode{ //邊表結(jié)點(diǎn)int adjvex。 //鄰接點(diǎn)域struct ArcNode *nextarc。 //指向下一個(gè)鄰接點(diǎn)的指針域//若要表示邊上信息，則應(yīng)增加一個(gè)數(shù)據(jù)域 info}ArcNode。typedef struct VNode{ //頂點(diǎn)表結(jié)點(diǎn)VertexType data。 //頂點(diǎn)域ArcNode *firstarc。 //邊表頭指針}VNode, AdjList[MAX_VERTEX_NUM]。 //AdjList 是鄰接表類型typedef struct{data firstarc adjvex nextarcAdjList adjlist。 //鄰接表int vexnum,arum。 //頂點(diǎn)數(shù)和邊數(shù)}AL