數(shù)據(jù)結(jié)構(gòu)實用教程（C語言版）（第二版）05第五章 樹

第五章樹5．1樹的定義5．2二叉樹二叉樹的定義及性質(zhì)二叉樹的存儲二叉樹的遍歷及實現(xiàn)算法5．3線索二叉樹中序線索二叉樹的定義 中序線索二叉樹上遍歷的實現(xiàn) 利用中序線索實現(xiàn)前序遍歷和后序遍歷5．4樹和森林5．5哈夫曼樹樹形結(jié)構(gòu)的邏輯特征是：有且僅有一個開始結(jié)點(diǎn)，可有若干個終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個前趨結(jié)點(diǎn)，可以有若干個后繼結(jié)點(diǎn)，也就是說結(jié)構(gòu)中的數(shù)據(jù)元素間存在著一對多的層次關(guān)系。本章首先簡單介紹樹的基本概念，然后重點(diǎn)討論二叉樹的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其運(yùn)算，線索二叉樹和線索二叉鏈表以及如何利用線索來實現(xiàn)遍歷運(yùn)算，并分析樹、森林與二叉樹之間的相互轉(zhuǎn)換問題，最后介紹二叉樹和樹的典型應(yīng)用。5．1樹的定義一、樹的定義1、樹的二元組定義：設(shè)tree=（D，S），其中D是數(shù)據(jù)元素的集合，S是D中數(shù)據(jù)元素之間關(guān)系的集合。設(shè)關(guān)系r∈S，相對r，滿足下列條件：（1）D中有且僅有一個開始結(jié)點(diǎn)，該結(jié)點(diǎn)被稱為樹的根；（2）除根外，D中其余的結(jié)點(diǎn)有且僅有一個前趨結(jié)點(diǎn)；（3）從根到其余結(jié)點(diǎn)都有路徑。則稱tree是相對r的樹形結(jié)構(gòu)。如圖所示的樹：該樹采用二元組表示如下：設(shè)tree=（D,S）,r∈SD={A,B,C,

D,E,F,G,H,I}r={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<D,G>,<G,H>,<G,I>}其中A是開始結(jié)點(diǎn)，即樹的根；除根A外，其余的結(jié)點(diǎn)有且僅有一個前趨結(jié)點(diǎn)，但對于后繼結(jié)點(diǎn)卻沒有限制，A有三個后繼結(jié)點(diǎn)B、C和D，B和G分別有兩個后繼結(jié)點(diǎn)，D只有一個后繼結(jié)點(diǎn)，剩下的結(jié)點(diǎn)E、F、C、H、I都沒有后繼，屬于終端結(jié)點(diǎn)。樹形結(jié)構(gòu)與線性結(jié)構(gòu)比較：在線性結(jié)構(gòu)中，有且僅有一個開始結(jié)點(diǎn)和一個終端結(jié)點(diǎn)，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個前趨和一個后繼。在樹形結(jié)構(gòu)中也是有且僅有一個開始結(jié)點(diǎn)（稱為根），但終端結(jié)點(diǎn)（稱為葉子）可以為任意多個，其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個前趨，但可以有任意多個后繼。樹形結(jié)構(gòu)中放寬了對結(jié)點(diǎn)的后繼的限制。線性結(jié)構(gòu)中每個元素的后繼最多為一個，而樹形結(jié)構(gòu)的后繼可以為多個。若樹中每個非終端結(jié)點(diǎn)的后繼剛好為一個時，就是線性表，線性結(jié)構(gòu)是樹形結(jié)構(gòu)的一種特殊形式。2、樹的遞歸定義樹是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，也可以用遞歸的形式來定義樹，樹的遞歸定義如下：樹是n（n＞0）個結(jié)點(diǎn)的有限集合（記作T），它滿足兩個條件：（1）有且僅有一個特定的稱為根的結(jié)點(diǎn)；（2）其余的結(jié)點(diǎn)可分為m（m≥0）個互不相交的有限集合T1，T2，…，Tm，其中每個集合又是一棵樹，并稱其為根的子樹。

3、樹的表示方法除了前面介紹的樹形表示法和二元組表示法外，還有其他三種常用的表示方法：凹入表表示法、嵌套集合表示法和廣義表表示法。其中，樹形表示法是最常用的表示方法，本書主要采用樹形表示法（由于連線的箭頭全部向下，所以省略箭頭）。4、樹中常用的一些基本術(shù)語（1）與層次相關(guān)的術(shù)語：在樹中，有且僅有一個開始結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，在樹中處于最上層；除根結(jié)點(diǎn)外的其余所有結(jié)點(diǎn)都有且僅有一個前趨，每個結(jié)點(diǎn)的前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的父（雙親）結(jié)點(diǎn)，在樹中處于該結(jié)點(diǎn)的上一層；樹中的每個結(jié)點(diǎn)都可以有若干個后繼結(jié)點(diǎn)，每個結(jié)點(diǎn)的后繼點(diǎn)稱為該結(jié)點(diǎn)的子（孩子或子女）結(jié)點(diǎn)，在樹中處于該結(jié)點(diǎn)的下一層，它們是該結(jié)點(diǎn)的子樹的根。沒有后繼的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，葉子結(jié)點(diǎn)是樹的終端結(jié)點(diǎn)，可以為多個。雙親相同的結(jié)點(diǎn)互稱為兄弟，在樹中處于同一層。（2）樹中結(jié)點(diǎn)之間具有分支關(guān)系一個結(jié)點(diǎn)的子樹的個數(shù)，稱為該結(jié)點(diǎn)的度，樹中度最大的結(jié)點(diǎn)的度數(shù)稱為該樹的度。（3）路徑：是樹中結(jié)點(diǎn)的序列，設(shè)結(jié)點(diǎn)序列為b1，b2，……，bj，若序列中任意兩個相鄰結(jié)點(diǎn)都滿足bi是bi+1的雙親，1≤i≤j-1則稱該結(jié)點(diǎn)序列為從b1到bj的路徑。路徑長度為序列中結(jié)點(diǎn)總數(shù)減1，即所經(jīng)過的邊的數(shù)目。若樹中存在一條從b到bj的路徑則稱b是bj的祖先，而bj是b的子孫。（4）如果樹中所有子樹都看成是從左到右的次序排列（子樹不能互換），則稱此樹為有序樹。而不考慮子樹排列順序的樹稱為無序樹。（5）森林：是m（m≥0）棵互不相交的樹的集合。5．2二叉樹一、二叉樹的定義及性質(zhì)

1、二叉樹是n（n≥0）個結(jié)點(diǎn)的有限集合，滿足：（1）當(dāng)n=0時，為空二叉樹。（2）當(dāng)n＞0時，是由一個根結(jié)點(diǎn)和兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。在二叉樹中，每個結(jié)點(diǎn)左子樹的根為該結(jié)點(diǎn)的左孩子，右子樹的根為該結(jié)點(diǎn)的右孩子。2、二叉樹通常有五種基本形態(tài):3、二叉樹具有以下重要的性質(zhì)：性質(zhì)1

二叉樹第i層上最多有2i-1（i≥1）個結(jié)點(diǎn)。性質(zhì)2

深度為k的二叉樹最多有2k-1（i≥1）個結(jié)點(diǎn)。性質(zhì)3

在任意一棵二叉樹中，若葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。兩種特殊的二叉樹：滿二叉樹和完全二叉樹每層結(jié)點(diǎn)數(shù)都達(dá)到最大值的二叉樹稱為滿二叉樹。除最下面一層外其余各層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下一層上的結(jié)點(diǎn)都集中在最左邊的若干位置上，則此二叉樹為完全二叉樹。

（a）滿二叉樹（b）完全二叉樹（c）類似完全二叉樹顯然，滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹。如果將滿二叉樹的最下層上結(jié)點(diǎn)從最右邊開始連續(xù)刪去若干個，就可以得到一棵完全二叉樹。性質(zhì)4具有n個結(jié)點(diǎn)的完全二叉樹的深度為或。性質(zhì)5對一棵具有n個結(jié)點(diǎn)的完全二叉樹，按照層次從上到下、每一層從左到右的次序（亦稱二叉樹的層次次序）將所有結(jié)點(diǎn)依次排列，可得到結(jié)點(diǎn)的層序序列，其中根結(jié)點(diǎn)的序號為1，其余結(jié)點(diǎn)的序號連續(xù)排列。對任一序號為i的結(jié)點(diǎn)（稱結(jié)點(diǎn)i）：（1）若結(jié)點(diǎn)i有雙親（即i>1），則雙親的序號為i/2。（2）若結(jié)點(diǎn)i有左孩子（即2i≤n時），則左孩子為2i，即任意結(jié)點(diǎn)左孩子的序號一定為偶數(shù)。（3）若結(jié)點(diǎn)i有右孩子（即2i+1≤n時），則右孩子為2i+1，即任意結(jié)點(diǎn)右孩子的序號一定為奇數(shù)。（4）當(dāng)i為偶數(shù)且i≠n時，它有右兄弟，右兄弟為i+1；當(dāng)i為奇數(shù)且i≠1時，它有左兄弟，左兄弟為i-1。二、二叉樹的存儲1．順序存儲（1）完全二叉樹的順序存儲對一棵具有N個結(jié)點(diǎn)的完全二叉樹，將所有結(jié)點(diǎn)按照從上到下、從左到右的次序依次排列，得到完全二叉樹中結(jié)點(diǎn)的層序序列，其中根結(jié)點(diǎn)的序號為1，然后將這個序列依次存儲在長度為N+1的數(shù)組bt中（為了保持序號和下標(biāo)一致，下標(biāo)為0的單元不用），完全二叉樹及其順序存儲結(jié)構(gòu)如圖所示。下標(biāo)012345678結(jié)點(diǎn)ABCDEFGH（2）一般二叉樹的順序存儲一般二叉樹與完全二叉樹對照，在空缺的位置處添加虛點(diǎn)（用特殊字符，如“#”表示），從而將一般的二叉樹擴(kuò)充成完全二叉樹，然后將擴(kuò)充后的完全二叉樹順序存儲。即帶著添加的虛點(diǎn)一起將完全二叉樹中的結(jié)點(diǎn)按層序排列，按照序號將所有結(jié)點(diǎn)依次存放在一維數(shù)組中，其中根結(jié)點(diǎn)的編號為1。

下標(biāo)01234567891011結(jié)點(diǎn)ABDCE#####F2．鏈接存儲每個結(jié)點(diǎn)除了存儲本身的數(shù)據(jù)外，需要附加兩個指針域分別指向該結(jié)點(diǎn)的左孩子和右孩子，這就是二叉鏈表。有時為了運(yùn)算方便，每個結(jié)點(diǎn)再附加一個指針域存儲雙親結(jié)點(diǎn)的指針，即帶父指針的二叉鏈表，也稱為三叉鏈表。二叉鏈表是二叉樹的鏈接存儲結(jié)構(gòu)中為最常用的一種，其中l(wèi)child和rchild分別表示指向結(jié)點(diǎn)左、右孩子的指針。lchilddatarchild二叉鏈表存儲結(jié)構(gòu)的C語言描述為：typedefcharDataType;typedefstructNode{ DataTypedata; structNode*lchild,*rchild;}BiTree;BiTree*root;/*根結(jié)點(diǎn)的指針*/二叉樹中的每個結(jié)點(diǎn)都為BiTree類型，它們之間通過lchild指針和rchild指針聯(lián)系在一起，可以通過保存根結(jié)點(diǎn)的指針root來唯一標(biāo)識一棵二叉樹。3、二叉鏈表的建立算法的實現(xiàn)步驟如下：（1）初始化隊列和二叉鏈表；（2）讀取用戶輸入的結(jié)點(diǎn)信息，若不是虛點(diǎn)，則建立一個新結(jié)點(diǎn)，同時將結(jié)點(diǎn)的地址入隊； （3）新結(jié)點(diǎn)若為第一個結(jié)點(diǎn)，則將此結(jié)點(diǎn)的地址存入根指針中；否則，從隊頭中取出雙親結(jié)點(diǎn)的指針，將此結(jié)點(diǎn)作為左孩子（或右孩子）鏈接到雙親結(jié)點(diǎn)上，若此結(jié)點(diǎn)的編號為偶數(shù)則為左孩子，否則為右孩子。當(dāng)一個結(jié)點(diǎn)的兩個孩子都已鏈接完畢，即結(jié)點(diǎn)編號為奇數(shù)時，隊頭元素出隊，此時的隊頭元素必定是下一個新結(jié)點(diǎn)的雙親結(jié)點(diǎn)；（4）重復(fù)步驟2~3，直到遇到結(jié)束標(biāo)志符@。#defineMAXSIZE100typedefstruct /*順序隊列的定義*/{BiTree*data[MAXSIZE];intfront,rear;}SeQueue;BiTree*createTree(){SeQueueQ,*q=&Q; /*隊列*/BiTree*root,*s;charch;root=NULL; /*置空二叉樹*/q->front=1;q->rear=0; /*置空隊列，隊尾保存新創(chuàng)建結(jié)點(diǎn)的指針，隊頭保存新結(jié)點(diǎn)的雙親的指針*/ch=getchar(); /*輸入一個字符*/while(ch!='@') /*若輸入字符不是結(jié)束符@，則反復(fù)處理*/{ s=NULL; if(ch!='#') /*不是虛點(diǎn)，則創(chuàng)建新結(jié)點(diǎn)，若是虛點(diǎn)，s=NULL*/ { s=(BiTree*)malloc(sizeof(BiTree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } q->rear++; /*隊尾指針后移*/ q->data[q->rear]=s; /*新結(jié)點(diǎn)地址或虛點(diǎn)地址（NULL）入隊*/ if(root==NULL)root=s; /*若新結(jié)點(diǎn)為第一個結(jié)點(diǎn)，則保存此結(jié)點(diǎn)為根結(jié)點(diǎn)*/ else { if(q->data[q->front]!=NULL)/*雙親不是虛點(diǎn)時，將新結(jié)點(diǎn)鏈接在雙親上*/ { if(q->rear%2==0)q->data[q->front]->lchild=s;/*新結(jié)點(diǎn)為左孩子*/ elseq->data[q->front]->rchild=s;/*新結(jié)點(diǎn)為右孩子*/ } if(q->rear%2==1)q->front++; /*左右孩子處理完畢后，出隊*/ } ch=getchar(); /*輸入下一個字符*/}returnroot;}三、二叉樹的遍歷及實現(xiàn)算法二叉樹的遍歷（Traversal）是指沿著某條搜索路徑訪問二叉樹中的每個結(jié)點(diǎn)，且每個結(jié)點(diǎn)僅訪問一次。“訪問”是指對結(jié)點(diǎn)的操作，其含義可以很廣，如可以是輸出結(jié)點(diǎn)的信息、修改結(jié)點(diǎn)數(shù)據(jù)等。二叉樹由根結(jié)點(diǎn)、左子樹、右子樹三個基本部分組成，遍歷一棵非空二叉樹的問題可分解為：訪問根結(jié)點(diǎn)、遍歷左子樹和遍歷右子樹。若分別用L、D、R分別表示上述三個子問題，則可有6種不同的遍歷次序：DLR、LDR、LRD、DRL、RDL、RLD。約定左子樹的訪問在右子樹之前，則討論三種遍歷方法：DLR：前序遍歷（PreOrder）LDR：中序遍歷（InOrder）LRD：后序遍歷（PostOrder）。二叉樹是遞歸的數(shù)據(jù)結(jié)構(gòu)，因為它的左、右子樹也是二叉樹因此對左、右子樹的遍歷仍然是遍歷二叉樹的問題，要用相同的次序來完成。所以，可以用遞歸的方法來定義二叉樹的遍歷運(yùn)算：（1）前序遍歷二叉樹—DLR

若二叉樹非空，則：

1）訪問根結(jié)點(diǎn)；

2）前序遍歷左子樹；

3）前序遍歷右子樹。（2）中序遍歷二叉樹—LDR

若二叉樹非空，則：

1）中序遍歷左子樹；

2）訪問根結(jié)點(diǎn)；

3）中序遍歷右子樹。（3）后序遍歷二叉樹—LRD

若二叉樹非空，則：

1）后序遍歷左子樹；

2）后序遍歷右子樹；

3）訪問根結(jié)點(diǎn)。編寫遞歸算法需要把握兩個方面內(nèi)容：遞歸調(diào)用和遞歸出口（亦稱終止條件）。這里的遞歸調(diào)用比較明顯，由于對左、右子樹的遍歷就是對二叉樹的遍歷，則遍歷左子樹和遍歷右子樹都為遞歸調(diào)用。另外，只要二叉樹不為空，就可以將其分成根左子樹、右子樹三個部分，分別進(jìn)行訪問。但若二叉樹為空樹遍歷運(yùn)算就結(jié)束了，所以遞歸出口是二叉樹為空。由此，可以得出二叉樹前序遍歷的遞歸算法。voidPreOrder(BiTree*T) /*前序遍歷二叉樹*/{ if(T) /*當(dāng)二叉樹非空，進(jìn)入遞歸過程；否則，遍歷運(yùn)算結(jié)束*/{printf("%c",T->data); /*訪問根結(jié)點(diǎn)*/PreOrder(T->lchild);/*前序遍歷左子樹*/PreOrder(T->rchild);/*前序遍歷右子樹*/}}同樣的思路可以得到中序和后序遍歷的遞歸算法：voidInOrder(BiTree*T) /*中序遍歷二叉樹*/{ if(T){InOrder(T->lchild); /*中序遍歷左子樹*/printf("%c",T->data); /*訪問根結(jié)點(diǎn)*/InOrder(T->rchild); /*中序遍歷右子樹*/}}voidPostOrder(BiTree*T) /*后序遍歷二叉樹*/{ if(T){PostOrder(T->lchild); /*后序遍歷左子樹*/PostOrder(T->rchild); /*后序遍歷右子樹*/printf("%c",T->data); /*訪問根結(jié)點(diǎn)*/}}

二叉樹的中序遍歷遞歸算法的執(zhí)行過程：中遍歷算法執(zhí)行時的系統(tǒng)棧變化：仿照系統(tǒng)棧在實現(xiàn)遞歸過程中的作用，自己定義一個棧可以將遞歸算法轉(zhuǎn)化為非遞歸的算法。下面以中序遍歷為例，給出非遞歸算法的C函數(shù)如下：#defineMAXSIZE100typedefBiTree*SElemType;typedefstruct{SElemTypedata[MAXSIZE]; /*順序棧中保存的是結(jié)點(diǎn)指針*/inttop;}SeqStack;voidInOrder(BiTree*p){ SeqStack*s; s=initSeqStack(); while(1) {while(p){push(s,p);p=p->lchild;} if(empty(s))break; p=top(s); pop(s);printf(“%c”,p->data);p=p->rchild; }}5．3線索二叉樹當(dāng)結(jié)點(diǎn)的左指針域為空（無左孩子）時，用它的左指針域存放該點(diǎn)在某種遍歷次序下的前趨結(jié)點(diǎn)的指針，當(dāng)結(jié)點(diǎn)的右指針域為空（無右孩子）時，用它的右指針域存放該點(diǎn)在某種遍歷次序下的后繼結(jié)點(diǎn)的指針。簡單地說：左空指前趨，右空指后繼。以這種結(jié)點(diǎn)構(gòu)成的二叉鏈表稱為線索二叉鏈表。指向前趨或后繼的指針稱為線索（Thread）。加上線索的二叉樹稱為線索二叉樹。以某種次序遍歷，使二叉樹變?yōu)榫€索二叉樹的過程稱作線索化。對每個指針域再附加一個標(biāo)志，當(dāng)指針域中存放的是孩子指針時，標(biāo)志為0；當(dāng)指針域中存放的是線索時，標(biāo)志為1。線索二叉鏈表存儲結(jié)構(gòu)的C語言描述如下：typedefcharDataType;typedefstructNode{ DataTypedata; structNode*lchild,*rchild; intltag,rtag;}BiThrTree;lchildltagdatartagrchild一、中序線索二叉樹的定義若線索二叉樹的線索中保存的是結(jié)點(diǎn)在前序遍歷下的前趨和后繼的指針，則這種線索稱為前序線索；同理，若保存的是中序遍歷下的前趨和后繼的指針，稱為中序線索；若保存的是后序遍歷下的前趨和后繼的指針，稱為后序線索。對應(yīng)的線索二叉樹有前序線索二叉樹、中序線索二叉樹和后序線索二叉樹，線索鏈表有前序線索鏈表、中序線索鏈表和后序線索鏈表。

若要實現(xiàn)中序線索化的運(yùn)算，在內(nèi)存中建立中序線索二叉鏈表，需要先按照線索樹中的結(jié)點(diǎn)結(jié)構(gòu)建立二叉鏈表存儲結(jié)構(gòu)，即每個結(jié)點(diǎn)的左、右標(biāo)志域均為0。在這樣的存儲結(jié)構(gòu)上進(jìn)行中序線索化，只要按中序遍歷二叉鏈表，在遍歷過程中用線索取代空指針即可。設(shè)兩個指針，一個指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，一個指針p指向當(dāng)前正在訪問的結(jié)點(diǎn)。具體方法是：（1）若結(jié)點(diǎn)*p有空指針域，則將相應(yīng)的標(biāo)志域置為1；（2）若結(jié)點(diǎn)*p有中序前趨結(jié)點(diǎn)*pre（pre！=NULL）則：

1）若結(jié)點(diǎn)*pre的右標(biāo)志為1（pre->rtag==1），則令pre->rchild為指向其中序后繼結(jié)點(diǎn)*p的指針（右線索），即pre->rchild=p；

2）若結(jié)點(diǎn)*p的左標(biāo)志為1（p->ltag==1），則令p->lchild為指向其中序前趨結(jié)點(diǎn)*pre的指針（左線索），即p->lchild=pre；（3）將pre指向剛剛訪問過的結(jié)點(diǎn)*p，即pre=p，保留前趨結(jié)點(diǎn)指針。中序線索化算法的C函數(shù)：BiThrTree*pre=NULL; /*全局變量，前趨指針*/voidinthreaded(BiThrTree*p) /*中序線索化*/{ if(p){ inthreaded(p->lchild); /*線索化左子樹*/if(p->lchild==NULL)p->ltag=1; /*結(jié)點(diǎn)*p的左標(biāo)志域*/if(p->rchild==NULL)p->rtag=1;/*結(jié)點(diǎn)*p的右標(biāo)志域*/if(pre!=NULL)/*當(dāng)前結(jié)點(diǎn)*p有前趨*/{if(pre->rtag==1)pre->rchild=p;/*置前趨結(jié)點(diǎn)*pre的右線索*/if(p->ltag==1)p->lchild=pre; /*置當(dāng)前結(jié)點(diǎn)*p的左線索*/}pre=p; /*保存剛剛訪問的結(jié)點(diǎn)指針*/inthreaded(p->rchild); /*線索化右子樹*/}}二、中序線索二叉樹上遍歷的實現(xiàn)首先要找到中序遍歷的第一個結(jié)點(diǎn)（二叉樹中最左下點(diǎn)，其左線索為空），然后依次找到該結(jié)點(diǎn)的中序后繼，直到中序遍歷的最后一個結(jié)點(diǎn)（其右線索為空），算法結(jié)束。同理，可從中序遍歷的最后一個結(jié)點(diǎn)出發(fā)，依次找該結(jié)點(diǎn)的中序前趨，直到中序遍歷的第一個結(jié)點(diǎn)，算法結(jié)束。在中序線索下查找*p結(jié)點(diǎn)的中序后繼有兩種情況：（1）若*p的右標(biāo)志為1（p->rtag==1，右子樹為空），則p->lchild為右線索，指向*p結(jié)點(diǎn)的中序后繼；（2）若*p的右標(biāo)志為0（p->rtag==0，右子樹非空），則*p的中序后繼為右子樹的最左下結(jié)點(diǎn)。也就是從*p的右孩子開始沿左指針往下找，直到找到一個沒有左孩子的結(jié)點(diǎn)*q（q->ltag==1），則*q就是*p的中序后繼。中序遍歷算法的C函數(shù)如下：voidInOrderThread(BiThrTree*root) /*中序線索下的中序遍歷*/{ BiThrTree*p;p=root;while(p->ltag==0)p=p->lchild; /*找中序遍歷的第一個結(jié)點(diǎn)

*while(p){ printf(“%c”,p->data);/*輸出結(jié)點(diǎn)*/if(p->rtag==1)p=p->rchild; /*分兩種情況查找結(jié)點(diǎn)后繼*/else{p=p->rchild;while(p->ltag==0)p=p->lchild;}}}三、利用中序線索實現(xiàn)前序遍歷和后序遍歷利用中序線索不但能方便地進(jìn)行中序遍歷，還可以方便地進(jìn)行前序和后序遍歷。如果可以利用中序線索找到每個結(jié)點(diǎn)在前序遍歷下的前趨或后繼，便可以進(jìn)行前序遍歷。由于前序遍歷的次序為根結(jié)點(diǎn)、左子樹、右子樹，所以利用中序線索找*p結(jié)點(diǎn)前序遍歷下的后繼的方法為：（1）若*p有左孩子，則左孩子為前序后繼；（2）若*p無左孩子但有右孩子，則右孩子為前序后繼；（3）若*p既無左孩子也無右孩子，則沿著*p結(jié)點(diǎn)的右線索（q->rtag=1）一直向上走，直到找到*q結(jié)點(diǎn)，q->rchild不是線索是指針（q->rtag=0），此時*(q->rchild）結(jié)點(diǎn)就是*p的前序后繼。同理，根據(jù)中序線索可以找到每個結(jié)點(diǎn)后序遍歷下的前趨，從而進(jìn)行后序遍歷。利用中序線索進(jìn)行前序遍歷算法的C函數(shù)如下：

voidPreOrderThread(BiThrTree*root)/*中序線索下的前序遍歷*/{BiThrTree*p;p=root; /*查找前序序遍歷的第一個結(jié)點(diǎn)，根結(jié)點(diǎn)*/while(p) /*不斷找前序后繼*/{ printf("%c",p->data); /*輸出結(jié)點(diǎn)*/if(p->ltag==0)p=p->lchild; /*查找結(jié)點(diǎn)前序后繼*/else{while(p&&p->rtag==1)p=p->rchild;if(p)p=p->rchild;}}}利用中序線索進(jìn)行后序遍歷算法的C函數(shù)如下：voidPostOrderThread(BiThrTree*root)/*中序線索下的后序遍歷*/{ BiThrTree*p;p=root; /*查找后序遍歷的最后一個結(jié)點(diǎn)，根結(jié)點(diǎn)*/while(p) /*不斷找后序前趨*/{printf(“%c”,p->data); if(p->rtag==0)p=p->rchild;/*查找結(jié)點(diǎn)前趨*/else{ while(p&&p->ltag==1)p=p->lchild;if(p) p=p->lchild;}}}5．4樹和森林一、樹和森林的遍歷

樹的先根遍歷定義為：若樹非空，先訪問根結(jié)點(diǎn)，然后從左到右依次先根遍歷每棵子樹。樹的后根遍歷定義為：若樹非空，先從左到右依次后根遍歷每棵子樹，最后訪問根結(jié)點(diǎn)。顯然，樹的先根遍歷和后根遍歷過程都是遞歸過程。圖中樹的先根遍歷序列為：A，B，F(xiàn)，D，C，G，E，H。后根遍歷序列為：F，B，D，G，H，E，C，A。先根遍歷森林定義為：若森林非空，則首先先根遍歷森林中的第一棵樹，然后從左到右依次先根遍歷除第一棵樹外其它樹組成的森林。后根遍歷森林定義為：若森林非空，則首先后根遍歷森林中的第一棵樹，然后從左到右依次后根遍歷除第一棵樹外其它樹組成的森林。同樣，森林的先根遍歷和后根遍歷過程也都是遞歸過程。先根序列：A，B，F(xiàn)，D，C，G，E，H，I，J，K，L，M，N，O后根序列：F，B，D，G，H，E，C，A，J，L，K，I，O，N，二、森林與二叉樹的轉(zhuǎn)換森林轉(zhuǎn)化為二叉樹的定義為：（1）若森林為空，則二叉樹為空；（2）若森林不空，則二叉樹的根為森林中第一棵樹的根；二叉樹的左子樹為第一棵樹去掉根之后的子樹森林轉(zhuǎn)換成的二叉樹；二叉樹的右子樹為森林除去第一棵樹后剩下的樹組成的森林轉(zhuǎn)化成的二叉樹。

》》簡單的轉(zhuǎn)換規(guī)則：（1）在森林中的所有兄弟之間添加一條連線，所有的根結(jié)點(diǎn)認(rèn)為是兄弟；（2）保留父點(diǎn)與第一個孩子之間的連線，去掉父點(diǎn)與其他孩子之間的連線；（3）將此時樹中的水平連線和垂直連線順時針旋轉(zhuǎn)45°，整理成二叉樹中的左右子女。二叉樹也可以轉(zhuǎn)化為森林。其轉(zhuǎn)換規(guī)則為：（1）若二叉樹為空，則對應(yīng)的森林為空；（2）若二叉樹不空，則森林中第一棵樹的根即為二叉樹的根，第一棵樹根的各個子樹為二叉樹的左子樹對應(yīng)的森林；森林中其余的樹為二叉樹的右子樹對應(yīng)的森林。三、樹的存儲1、雙親表示法用一組連續(xù)的存儲空間（一維數(shù)組）存儲樹中的各個結(jié)點(diǎn)，數(shù)組中的一個元素存儲樹中的一個結(jié)點(diǎn)，數(shù)組元素為結(jié)構(gòu)體類型，其中包括結(jié)點(diǎn)本身的信息以及結(jié)點(diǎn)的雙親在數(shù)組中的序號樹的這種存儲方法稱為雙親表示法。

0A-11B02C03D04E25F16G27H42.孩子鏈表表示法將結(jié)點(diǎn)的所有孩子用鏈接方式存儲在一個單鏈表中，沒有孩子的結(jié)點(diǎn)后面的單鏈表為空。樹中結(jié)點(diǎn)用順序方式存儲在一個長度為n（n為樹中結(jié)點(diǎn)數(shù)）的數(shù)組中，數(shù)組的每一個元素由兩個域組成，一個域用來存放結(jié)點(diǎn)信息，另一個用來存放該結(jié)點(diǎn)的孩子鏈表的頭指針。單鏈表的結(jié)構(gòu)也由兩個域組成，一個存放孩子結(jié)點(diǎn)在一維數(shù)組中的序號，另一個是指針域，指向下一個孩子結(jié)點(diǎn)。3.樹的二叉鏈表（孩子——兄弟鏈）表示法實際上就是將樹轉(zhuǎn)換為對應(yīng)的二叉樹，然后再采用二叉鏈表存儲結(jié)構(gòu)。將樹轉(zhuǎn)換為對應(yīng)的二叉樹后，樹中每個結(jié)點(diǎn)的第一個孩子是對應(yīng)二叉樹中該結(jié)點(diǎn)的左孩子，而每個結(jié)點(diǎn)的右兄弟對應(yīng)二叉樹中該結(jié)點(diǎn)的右孩子，所以該方法又稱孩子—兄弟鏈表示法。每個結(jié)點(diǎn)除其信息域外，再增加兩個指針域，分別指向該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)和下一個兄弟結(jié)點(diǎn)。5．5哈夫曼樹一、哈夫曼樹的定義及建立結(jié)點(diǎn)的路徑長度就是從根結(jié)點(diǎn)到每個結(jié)點(diǎn)的路徑長度，其值為路經(jīng)上的結(jié)點(diǎn)數(shù)減1。賦予了權(quán)值的結(jié)點(diǎn)的路徑長度與該結(jié)點(diǎn)權(quán)值的乘積即為結(jié)點(diǎn)的帶權(quán)路徑長度（WeightedPathLengthofNode）。樹的帶權(quán)路徑長度（WeightedPathLengthofTree，縮寫為WPL）定義為：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為：其中n表示葉子結(jié)點(diǎn)數(shù)，wi表示第i個葉子結(jié)點(diǎn)的權(quán)值，li代表第i個葉子結(jié)點(diǎn)的路徑長度。WPLa=2×2+3×2+6×2+8×2=38WPLb=8×1+6×2+2×3+3×3=35WPLc=2×1+6×3+8×3+3×2=50WPLd=8×1+2×3+3×3+6×2=35哈夫曼樹（HuffmanTree）又稱最優(yōu)二叉樹，是在含有n個葉子結(jié)點(diǎn)，權(quán)值分別為w1，w2，……，wn的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹。哈夫曼（D.A.Huffman）在上世紀(jì)五十年代初便提出了一個非常簡單的算法來建立哈夫曼樹，其算法描述如下：（1）將給定的n個權(quán)值{w1，w2，...，wn}作為n個根結(jié)點(diǎn)的權(quán)值，構(gòu)造一個具有n棵二叉樹的森林{T1，T2，...，Tn}，其中每棵二叉樹只有一個根結(jié)點(diǎn)；（2）在森林中選取兩棵根點(diǎn)權(quán)值最小的二叉樹分別作為左、右子樹，增加一個新結(jié)點(diǎn)作為根，從而將兩棵樹合并成一棵樹，新根結(jié)點(diǎn)的權(quán)值為左右子樹根結(jié)點(diǎn)權(quán)值之和。森林中因此也減少了一棵樹；（3）重復(fù)上面步驟（2）的處理過程，直到森林中只有一棵二叉樹為止，這棵二叉樹就是哈夫曼樹。從哈夫曼樹構(gòu)造過程和生成結(jié)果可知，哈夫曼樹具有以下特點(diǎn)：（1）哈夫曼樹不唯一。（2）哈夫曼樹中只包含度為0和度為2的結(jié)點(diǎn)。（3）樹中權(quán)值越大的葉子結(jié)點(diǎn)離根結(jié)點(diǎn)越近。例5.1

假設(shè)樹中葉子結(jié)點(diǎn)的權(quán)值為{5,29,7,8,14,23,3,11}，構(gòu)造一棵哈夫曼樹。（1）將給定的8個權(quán)值作為根結(jié)點(diǎn)，構(gòu)造具有8棵樹的森林（2）從森林中選取根點(diǎn)權(quán)值最小的兩棵二叉樹3、5，分別作為左右子樹，構(gòu)造一棵新的二叉樹，新樹根點(diǎn)權(quán)值為8，森林中減少一棵樹。（3）重復(fù)步驟（2），直到森林中只剩一棵二叉樹為止。為方便查找雙親，將哈夫曼樹的存儲結(jié)構(gòu)設(shè)計為三叉鏈表。每個結(jié)點(diǎn)包含四個域：weight為結(jié)點(diǎn)的權(quán)值，lchild、rchild、parent分別為左、右孩子和雙親結(jié)點(diǎn)的指針。含有N個葉子結(jié)點(diǎn)的哈夫曼樹共有2N-1個結(jié)點(diǎn)，由此可定義一個長度為2N-1的數(shù)組tree來存儲哈夫曼樹，下標(biāo)從1開始，0代表指針空（NULL）。存儲結(jié)構(gòu)用C語言描述為：#defineN7 /*葉子結(jié)點(diǎn)數(shù)*/#defineM2*N-1 /*總結(jié)點(diǎn)數(shù)*/typedefstruct /*哈夫曼樹結(jié)點(diǎn)的存儲結(jié)構(gòu)*/{ floatweight; /*結(jié)點(diǎn)的權(quán)值*/ intparent; /*雙親在數(shù)組中的下標(biāo)*/intlchild,rchild; /*左、右孩子在數(shù)組中的下標(biāo)，

葉結(jié)點(diǎn)的這兩個指針值為0*/}HufmTree;HufmTreetree[M+1];/*哈夫曼樹為靜態(tài)鏈表，下標(biāo)為0的單元空出*/

weightparentlchildrchild在上述存儲結(jié)構(gòu)上實現(xiàn)哈夫曼算法的過程如下：（1）將哈夫曼樹數(shù)組tree中的2N-1個結(jié)點(diǎn)初始化：即將各結(jié)點(diǎn)的權(quán)值、雙親、左孩子、右孩子均置為0。（2）讀入N個葉子結(jié)點(diǎn)的權(quán)值，分別存入數(shù)組tree[i]（1≤i≤N）的權(quán)值域中，構(gòu)造包含N棵樹的初始森林，森林中的每棵樹只有一個根結(jié)點(diǎn)。（3）循環(huán)N-1次，對森林中的樹進(jìn)行N-1次合并，產(chǎn)生N-1個新結(jié)點(diǎn)，依次放入數(shù)組tree[i]中（N+1≤i≤2N-1）。每次合并的步驟是：1）在當(dāng)前森林的所有結(jié)點(diǎn)tree[j]（1≤j≤i-1）中，選取具有最小權(quán)值和次小權(quán)值的兩個根結(jié)點(diǎn)（parent域為0的結(jié)點(diǎn)），分別用p1和p2記住這兩個根結(jié)點(diǎn)在數(shù)組tree中的下標(biāo)。2）將根為tree[p1]和tree[p2]的兩棵樹合并，使其成為新結(jié)點(diǎn)tree[i]的左、右孩子，得到一棵以新結(jié)點(diǎn)tree[i]為根的二叉樹即將tree[i].weight賦值為tree[p1].weight和tree[p2].weight之和tree[i]的左指針賦值為p1；tree[i]的右指針賦值為p2；同時將tree[p1]和tree[p2]的雙親域均賦值為i，使其指向新結(jié)點(diǎn)tree[i]即它們在當(dāng)前森林中已不再是根結(jié)點(diǎn)。

二、哈夫曼編碼及譯碼在進(jìn)行文字傳輸時，數(shù)據(jù)通信的發(fā)送方需要將原文中的每一個文字轉(zhuǎn)換成對應(yīng)的二進(jìn)制0、1序列（編碼）進(jìn)行發(fā)送，接收方接收到二進(jìn)制的0、1串后再還原成原文（譯碼）。其編碼和譯碼的過程如下所示：原文

電文（二進(jìn)制的0、1序列）

原文常用的編碼方式有兩種：等長編碼和不等長編碼。等長編碼：ASCⅡ碼，其特點(diǎn)是每個字符的編碼長度相同。編碼簡單且具有唯一性，當(dāng)字符集中的字符在電文中出現(xiàn)的頻度相等時，它是最優(yōu)的編碼。不等長編碼：字符的編碼長度不等，因此稱這種編碼方式為不等長編碼。為了使譯碼唯一，則要求字符集中任一字符的編碼都不是其他字符編碼的前面一部分，這種編碼叫做前綴（編）碼。利用二叉樹來對葉子結(jié)點(diǎn)進(jìn)行編碼，所得的編碼一定為前綴碼。若要使報文總長最短，則利用哈夫曼樹對葉子結(jié)點(diǎn)進(jìn)行編碼一定是最優(yōu)的編碼。哈夫曼編碼的實現(xiàn)方法如下：（1）利用字符集中每個字符的使用頻度作為權(quán)值構(gòu)造一個哈夫曼樹；（2）從根結(jié)點(diǎn)開始，與左孩子的連線標(biāo)上0，與右孩子的連線標(biāo)上1；（3）由根到某葉子結(jié)點(diǎn)的路經(jīng)上的0、1序列組成該葉子結(jié)點(diǎn)的編碼。例5.2

假設(shè)有一個字