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

第五章樹5．1樹的定義5．2二叉樹二叉樹的定義及性質二叉樹的存儲二叉樹的遍歷及實現(xiàn)算法5．3線索二叉樹中序線索二叉樹的定義 中序線索二叉樹上遍歷的實現(xiàn) 利用中序線索實現(xiàn)前序遍歷和后序遍歷5．4樹和森林5．5哈夫曼樹樹形結構的邏輯特征是：有且僅有一個開始結點，可有若干個終端結點，其余的內部結點都有且僅有一個前趨結點，可以有若干個后繼結點，也就是說結構中的數(shù)據(jù)元素間存在著一對多的層次關系。本章首先簡單介紹樹的基本概念，然后重點討論二叉樹的邏輯結構、存儲結構及其運算，線索二叉樹和線索二叉鏈表以及如何利用線索來實現(xiàn)遍歷運算，并分析樹、森林與二叉樹之間的相互轉換問題，最后介紹二叉樹和樹的典型應用。5．1樹的定義一、樹的定義1、樹的二元組定義：設tree=（D，S），其中D是數(shù)據(jù)元素的集合，S是D中數(shù)據(jù)元素之間關系的集合。設關系r∈S，相對r，滿足下列條件：（1）D中有且僅有一個開始結點，該結點被稱為樹的根；（2）除根外，D中其余的結點有且僅有一個前趨結點；（3）從根到其余結點都有路徑。則稱tree是相對r的樹形結構。如圖所示的樹：該樹采用二元組表示如下：設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是開始結點，即樹的根；除根A外，其余的結點有且僅有一個前趨結點，但對于后繼結點卻沒有限制，A有三個后繼結點B、C和D，B和G分別有兩個后繼結點，D只有一個后繼結點，剩下的結點E、F、C、H、I都沒有后繼，屬于終端結點。樹形結構與線性結構比較：在線性結構中，有且僅有一個開始結點和一個終端結點，其余的內部結點都有且僅有一個前趨和一個后繼。在樹形結構中也是有且僅有一個開始結點（稱為根），但終端結點（稱為葉子）可以為任意多個，其余的內部結點都有且僅有一個前趨，但可以有任意多個后繼。樹形結構中放寬了對結點的后繼的限制。線性結構中每個元素的后繼最多為一個，而樹形結構的后繼可以為多個。若樹中每個非終端結點的后繼剛好為一個時，就是線性表，線性結構是樹形結構的一種特殊形式。2、樹的遞歸定義樹是一種遞歸的數(shù)據(jù)結構，也可以用遞歸的形式來定義樹，樹的遞歸定義如下：樹是n（n＞0）個結點的有限集合（記作T），它滿足兩個條件：（1）有且僅有一個特定的稱為根的結點；（2）其余的結點可分為m（m≥0）個互不相交的有限集合T1，T2，…，Tm，其中每個集合又是一棵樹，并稱其為根的子樹。

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

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

二叉樹第i層上最多有2i-1（i≥1）個結點。性質2

深度為k的二叉樹最多有2k-1（i≥1）個結點。性質3

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

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

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

若二叉樹非空，則：

1）訪問根結點；

2）前序遍歷左子樹；

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

若二叉樹非空，則：

1）中序遍歷左子樹；

2）訪問根結點；

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

若二叉樹非空，則：

1）后序遍歷左子樹；

2）后序遍歷右子樹；

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

二叉樹的中序遍歷遞歸算法的執(zhí)行過程：中遍歷算法執(zhí)行時的系統(tǒng)棧變化：仿照系統(tǒng)棧在實現(xiàn)遞歸過程中的作用，自己定義一個?？梢詫⑦f歸算法轉化為非遞歸的算法。下面以中序遍歷為例，給出非遞歸算法的C函數(shù)如下：#defineMAXSIZE100typedefBiTree*SElemType;typedefstruct{SElemTypedata[MAXSIZE]; /*順序棧中保存的是結點指針*/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線索二叉樹當結點的左指針域為空（無左孩子）時，用它的左指針域存放該點在某種遍歷次序下的前趨結點的指針，當結點的右指針域為空（無右孩子）時，用它的右指針域存放該點在某種遍歷次序下的后繼結點的指針。簡單地說：左空指前趨，右空指后繼。以這種結點構成的二叉鏈表稱為線索二叉鏈表。指向前趨或后繼的指針稱為線索（Thread）。加上線索的二叉樹稱為線索二叉樹。以某種次序遍歷，使二叉樹變?yōu)榫€索二叉樹的過程稱作線索化。對每個指針域再附加一個標志，當指針域中存放的是孩子指針時，標志為0；當指針域中存放的是線索時，標志為1。線索二叉鏈表存儲結構的C語言描述如下：typedefcharDataType;typedefstructNode{ DataTypedata; structNode*lchild,*rchild; intltag,rtag;}BiThrTree;lchildltagdatartagrchild一、中序線索二叉樹的定義若線索二叉樹的線索中保存的是結點在前序遍歷下的前趨和后繼的指針，則這種線索稱為前序線索；同理，若保存的是中序遍歷下的前趨和后繼的指針，稱為中序線索；若保存的是后序遍歷下的前趨和后繼的指針，稱為后序線索。對應的線索二叉樹有前序線索二叉樹、中序線索二叉樹和后序線索二叉樹，線索鏈表有前序線索鏈表、中序線索鏈表和后序線索鏈表。

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

1）若結點*pre的右標志為1（pre->rtag==1），則令pre->rchild為指向其中序后繼結點*p的指針（右線索），即pre->rchild=p；

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

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

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

樹的先根遍歷定義為：若樹非空，先訪問根結點，然后從左到右依次先根遍歷每棵子樹。樹的后根遍歷定義為：若樹非空，先從左到右依次后根遍歷每棵子樹，最后訪問根結點。顯然，樹的先根遍歷和后根遍歷過程都是遞歸過程。圖中樹的先根遍歷序列為：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，二、森林與二叉樹的轉換森林轉化為二叉樹的定義為：（1）若森林為空，則二叉樹為空；（2）若森林不空，則二叉樹的根為森林中第一棵樹的根；二叉樹的左子樹為第一棵樹去掉根之后的子樹森林轉換成的二叉樹；二叉樹的右子樹為森林除去第一棵樹后剩下的樹組成的森林轉化成的二叉樹。

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

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

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

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

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

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

電文（二進制的0、1序列）

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

假設有一個字