數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語(yǔ)言版） 董鳳服及算法 第5章 樹(shù)新

數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語(yǔ)言版）

中國(guó)水利水電出版社1/12/20231第5章樹(shù)本章中主要介紹下列內(nèi)容：樹(shù)的邏輯定義和存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的邏輯定義、存儲(chǔ)結(jié)構(gòu)二叉樹(shù)的基本操作算法樹(shù)和二叉樹(shù)的轉(zhuǎn)換哈夫曼樹(shù)及其應(yīng)用本章目錄5.1樹(shù)15.2二叉樹(shù)25.3二叉樹(shù)的建立和遍歷35.4樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換45.5哈夫曼樹(shù)55.6本章小結(jié)6結(jié)束5.1樹(shù)5.1.1樹(shù)的定義5.1.2樹(shù)的表示方法5.1.3樹(shù)的基本術(shù)語(yǔ)5.1.4樹(shù)的存儲(chǔ)結(jié)構(gòu)返回到總目錄5.1.1樹(shù)的定義樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)稱(chēng)為空樹(shù)。當(dāng)n>0時(shí)，是非空樹(shù)，它滿(mǎn)足以下兩個(gè)條件：（1）有且僅有一個(gè)稱(chēng)為根的結(jié)點(diǎn)；（2）其余結(jié)點(diǎn)分為m（m≥0）個(gè)互不相交的非空集合T1，T2，…，Tm，其中每個(gè)集合本身又是一棵樹(shù)，稱(chēng)為根的子樹(shù)。返回到本節(jié)目錄樹(shù)的二元組表示法樹(shù)可用二元組來(lái)表示。其中，D為結(jié)點(diǎn)集合，R為邊的集合。一棵樹(shù)T如圖5-1所示，則它的二元組表示方法為：T=（D,R）D={A,B,C,D,E,F,G,H}R={<A,B>,<A,C>,<A,D>,<B,E>,<C,F>,<C,G>,<D,H>,<F,I>}圖5-1樹(shù)的邏輯結(jié)構(gòu)圖返回到本節(jié)目錄樹(shù)的表示方法樹(shù)的邏輯結(jié)構(gòu)表示有樹(shù)形表示法，文氏圖表示法，凹入表示法和廣義表表示法等。1．樹(shù)形表示法這是樹(shù)的最基本的表示，使用一棵倒置的樹(shù)表示樹(shù)結(jié)構(gòu)。圖5-1就是采用這種方法。2．文氏表示法使用集合以及集合的包含關(guān)系描述樹(shù)結(jié)構(gòu)。圖5-2（a）就是圖5-1的樹(shù)的文氏圖表示法。3．凹入表示法使用線(xiàn)段的伸縮關(guān)系描述樹(shù)的結(jié)構(gòu)。圖5-2（b）就是圖5-1的樹(shù)的凹入表示法。4．廣義表表示法將樹(shù)的根結(jié)點(diǎn)寫(xiě)在括號(hào)的左邊，除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)寫(xiě)在括號(hào)內(nèi)并用逗號(hào)間隔來(lái)描述樹(shù)的結(jié)構(gòu)。圖5-2（c）就是圖5-1的樹(shù)的廣義表表示法。返回到本節(jié)目錄樹(shù)的三種表示方法(a)文氏圖表示法(b)凹入圖表示法(c)廣義表表示法圖5-2樹(shù)的其它表示方法返回到本節(jié)目錄樹(shù)的基本術(shù)語(yǔ)1．結(jié)點(diǎn)樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。2．結(jié)點(diǎn)的度結(jié)點(diǎn)所擁有的分支數(shù)目或后繼結(jié)點(diǎn)個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度（Degree）。例如圖5-1所示的樹(shù)中結(jié)點(diǎn)A的度為3，結(jié)點(diǎn)C的度為2，結(jié)點(diǎn)E的度為0。3．樹(shù)的度樹(shù)中各結(jié)點(diǎn)度的最大值稱(chēng)為該樹(shù)的度。例如圖5-1所示的樹(shù)的度為3。4．葉子（終端結(jié)點(diǎn)）度為零的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。例如圖5-1所示的樹(shù)中結(jié)點(diǎn)E、G、H、I為葉子結(jié)點(diǎn)。返回到本節(jié)目錄樹(shù)的基本術(shù)語(yǔ)5．分支結(jié)點(diǎn)度不為零的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)。例如圖5-1所示的樹(shù)中的A、B、C、D、F都是分支結(jié)點(diǎn)。6．孩子結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的后繼稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。例如圖5-1所示的樹(shù)中A的孩子結(jié)點(diǎn)為B、C、D。7．雙親結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)稱(chēng)其為其后繼結(jié)點(diǎn)的雙親結(jié)點(diǎn)。例如圖5-1所示的樹(shù)中A是B、C、D的雙親結(jié)點(diǎn)，C是F、G的雙親。8．兄弟結(jié)點(diǎn)同一雙親結(jié)點(diǎn)下的孩子結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn)。例如圖5-1所示的樹(shù)中B、C、D互為兄弟結(jié)點(diǎn)，F(xiàn)、G互為兄弟結(jié)點(diǎn)，但不同雙親的兩個(gè)同層結(jié)點(diǎn)不互為兄弟結(jié)點(diǎn)，如G和H不互為兄弟結(jié)點(diǎn)。返回到本節(jié)目錄樹(shù)的基本術(shù)語(yǔ)9．堂兄弟雙親互為兄弟的兩個(gè)結(jié)點(diǎn)互稱(chēng)為堂兄弟。例如圖5-1所示的樹(shù)中G和H就互為堂兄弟。10．子孫結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的所有子樹(shù)中的結(jié)點(diǎn)稱(chēng)之為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。例如圖5-1所示的樹(shù)中A的子孫為B、C、D、E、F、G、H、I。11．祖先結(jié)點(diǎn)從樹(shù)根結(jié)點(diǎn)到達(dá)一個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。例如圖5-1所示的樹(shù)中E的祖先結(jié)點(diǎn)為A和B（包括其雙親結(jié)點(diǎn)B）。返回到本節(jié)目錄樹(shù)的基本術(shù)語(yǔ)12．層數(shù)樹(shù)的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它雙親結(jié)點(diǎn)的層數(shù)加1。例如圖5-1所示的樹(shù)中A的層數(shù)為1，B、C、D的層數(shù)為2，E、F、G、H的層數(shù)為3，I的層數(shù)為4。13．樹(shù)的深度樹(shù)中結(jié)點(diǎn)的最大層數(shù)稱(chēng)為樹(shù)的深度（或高度）。例如圖5-1所示的樹(shù)中的深度為4。14．有序樹(shù)和無(wú)序樹(shù)如果一棵樹(shù)中的結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，即若交換了某結(jié)點(diǎn)各子樹(shù)的相對(duì)位置，則構(gòu)成了不同的樹(shù)，稱(chēng)這樣的樹(shù)為有序樹(shù)，反之，則為無(wú)序樹(shù)。15．森林m（m≥0）棵互不相交樹(shù)的集合稱(chēng)為森林。返回到本節(jié)目錄5.1.4樹(shù)的存儲(chǔ)結(jié)構(gòu)1.雙親表示法用一個(gè)一維數(shù)組存儲(chǔ)樹(shù)中的各個(gè)結(jié)點(diǎn)，數(shù)組元素是一個(gè)結(jié)構(gòu)體型數(shù)據(jù)，包含兩個(gè)域：data域和parent域，分別表示結(jié)點(diǎn)的數(shù)據(jù)值和其雙親結(jié)點(diǎn)在數(shù)組中的下標(biāo)。其類(lèi)型定義如下：typedefstruct{ElemTypedata;/*結(jié)點(diǎn)的數(shù)據(jù)域，ElemType可以是任意類(lèi)型*/intparent;/*結(jié)點(diǎn)存儲(chǔ)其雙親的數(shù)組下標(biāo)值*/}ParType[MaxSize];返回到本節(jié)目錄1.雙親表示法示例圖5-1中給出的樹(shù)，可以用圖5-3來(lái)存儲(chǔ)表示。其中，規(guī)定數(shù)組下標(biāo)為0的位置存儲(chǔ)的是根結(jié)點(diǎn)，設(shè)根結(jié)點(diǎn)的parent域?yàn)?1。圖5-3圖5-1中樹(shù)的雙親表示法返回到本節(jié)目錄5.1.4樹(shù)的存儲(chǔ)結(jié)構(gòu)2.孩子表示法將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)構(gòu)成一個(gè)單鏈表，稱(chēng)之為孩子鏈表。n個(gè)結(jié)點(diǎn)的樹(shù)有n個(gè)這樣的孩子鏈表。為了方便起見(jiàn)，我們將每個(gè)結(jié)點(diǎn)存放在一個(gè)順序表中，順序表的每個(gè)元素有兩個(gè)域：一個(gè)是存放該結(jié)點(diǎn)的數(shù)據(jù)值；另一個(gè)是存放該結(jié)點(diǎn)的第一個(gè)孩子的地址。孩子結(jié)點(diǎn)也有兩個(gè)域：一個(gè)域是存放該孩子結(jié)點(diǎn)在順序表中的位置（數(shù)組下標(biāo)），另一個(gè)域是存放下一個(gè)孩子的地址。返回到本節(jié)目錄2.孩子表示法舉例圖5-4是圖5-1所示樹(shù)的孩子表示法。其中，規(guī)定表頭下標(biāo)為0的位置存放根結(jié)點(diǎn)。圖5-4圖5-1樹(shù)的孩子表示法返回到本節(jié)目錄5.1.4樹(shù)的存儲(chǔ)結(jié)構(gòu)3.孩子兄弟法孩子兄弟法存儲(chǔ)結(jié)構(gòu)是一種二叉鏈表，鏈表中每個(gè)結(jié)點(diǎn)包括三個(gè)域：數(shù)據(jù)值和兩個(gè)指針，其中一個(gè)指針指向該結(jié)點(diǎn)的最左邊第一個(gè)孩子，而另一個(gè)指針則指向該結(jié)點(diǎn)的下一個(gè)兄弟。每個(gè)結(jié)點(diǎn)的類(lèi)型定義如下：typedefstructnode2{ElemTypedata;/*數(shù)據(jù)域*/Structnode2*child,*brother;/*其第一個(gè)孩子和其右邊兄弟的地址*/}CBNodeType;/*孩子兄弟結(jié)點(diǎn)類(lèi)型*/返回到本節(jié)目錄圖5-5是圖5-1所示樹(shù)的孩子兄弟表示法的存儲(chǔ)結(jié)構(gòu)。其中T指向樹(shù)的根結(jié)點(diǎn)。圖5-5圖5-1樹(shù)的孩子兄弟表示法返回到本節(jié)目錄5.2二叉樹(shù)5.2.1二叉樹(shù)的定義5.2.2二叉樹(shù)的性質(zhì)5.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)5.2.4二叉樹(shù)的基本運(yùn)算返回到總目錄5.2.1二叉樹(shù)的定義

1．二叉樹(shù)的定義二叉樹(shù)（BinaryTree）是有n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。（1）該集合或者為空（n=0）；（2）或者由一個(gè)根結(jié)點(diǎn)及兩個(gè)不相交的分別稱(chēng)為左子樹(shù)和右子樹(shù)組成的非空樹(shù)；（3）左子樹(shù)和右子樹(shù)同樣又都是二叉樹(shù)。返回到本節(jié)目錄5.2.1二叉樹(shù)的定義2．二叉樹(shù)的形態(tài)二叉樹(shù)歸納起來(lái)有五種形態(tài)，如圖5-7所示。(a)空二叉樹(shù)(b)只有一個(gè)根結(jié)點(diǎn)(c)右子樹(shù)為空(d)左子樹(shù)為空(e)左、右子樹(shù)非空?qǐng)D5-7二叉樹(shù)的五種形態(tài)返回到本節(jié)目錄5.2.2二叉樹(shù)的性質(zhì)性質(zhì)1：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。性質(zhì)2：深度為k的二叉樹(shù)中至多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：對(duì)任意一棵二叉樹(shù)T，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則有n0=n2+1。返回到本節(jié)目錄5.2.2二叉樹(shù)的性質(zhì)下面介紹兩種特殊的二叉樹(shù)。（1）滿(mǎn)二叉樹(shù)一棵深度為k，且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)。圖5-9（a）所示是一棵深度為4的滿(mǎn)二叉樹(shù)，其特點(diǎn)是每一層上的結(jié)點(diǎn)都具有最大的結(jié)點(diǎn)數(shù)。（2）完全二叉樹(shù)在一棵二叉樹(shù)中，除最后一層外，若其它層都是滿(mǎn)的，并且最后一層或者是滿(mǎn)的，或者是在右邊缺少連續(xù)的若干個(gè)結(jié)點(diǎn)，則稱(chēng)此二叉樹(shù)為完全二叉樹(shù)。據(jù)此得知滿(mǎn)二叉樹(shù)是完全二叉樹(shù)的特例。圖5-9（b）是一棵深度為4的完全二叉樹(shù)。返回到本節(jié)目錄滿(mǎn)二叉樹(shù)和完全二叉樹(shù)示例(a)一棵滿(mǎn)二叉樹(shù)(b)一棵完全二叉樹(shù)圖5-9一棵滿(mǎn)二叉樹(shù)和一棵完全二叉樹(shù)示意圖返回到本節(jié)目錄5.2.2二叉樹(shù)的性質(zhì)性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。性質(zhì)5：如果一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為）的結(jié)點(diǎn)按層次（從第1層到第層，每層從左到右。則對(duì)任一結(jié)點(diǎn)i(1≤i≤n)有：（1）如果i=1，結(jié)點(diǎn)i是根結(jié)點(diǎn)，無(wú)雙親；如果i>1，則其雙親結(jié)點(diǎn)是結(jié)點(diǎn)i/2。（2）如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子，該結(jié)點(diǎn)為葉子結(jié)點(diǎn)；否則其左孩子是結(jié)點(diǎn)2i。（3）如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子，該結(jié)點(diǎn)為葉子結(jié)點(diǎn)；否則其左孩子是結(jié)點(diǎn)2i+1。返回到本節(jié)目錄5.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1．順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)一棵二叉樹(shù)時(shí)，先對(duì)該二叉樹(shù)中的各結(jié)點(diǎn)進(jìn)行編號(hào)，然后以各結(jié)點(diǎn)的編號(hào)為下標(biāo)，把各結(jié)點(diǎn)的值存到一維數(shù)組中。其編號(hào)過(guò)程為：首先，把樹(shù)的根結(jié)點(diǎn)的編號(hào)定為1，然后按照層次從上到下，從左到右的順序?qū)γ恳唤Y(jié)點(diǎn)進(jìn)行編號(hào)。當(dāng)一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為i時(shí)，若它是左孩子，則編號(hào)為2i，若它是右孩子，則編號(hào)為2i+1。如圖5-10(a)所示的二叉樹(shù)（各結(jié)點(diǎn)上方的數(shù)字就是該結(jié)點(diǎn)的編號(hào)）對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)為圖5-10(b)所示。返回到本節(jié)目錄順序存儲(chǔ)的二叉樹(shù)示例一棵帶編號(hào)的二叉樹(shù)(b)對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)圖5-10一棵二叉樹(shù)及其順序存儲(chǔ)結(jié)構(gòu)返回到本節(jié)目錄5.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)2．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)于一般的二叉樹(shù)，通常采用二叉鏈表示。鏈表中的每個(gè)結(jié)點(diǎn)包含兩個(gè)指針，分別指向該結(jié)點(diǎn)的左孩子和右孩子。在二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)的類(lèi)型定義如下：Typedefstructtnode{ElemTypedata;/*數(shù)據(jù)域*/structtnode*lchild,*rchild;/*左、右孩子指針域*/}BTNode;/*二叉樹(shù)結(jié)點(diǎn)存儲(chǔ)類(lèi)型*/

其中，data域中存入結(jié)點(diǎn)的數(shù)據(jù)值，lchild和rchild分別表示左指針域和右指針域，分別存儲(chǔ)其左、右孩子結(jié)點(diǎn)的地址。返回到本節(jié)目錄圖5-11二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖5-10的二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖5-11所示。返回到本節(jié)目錄5.2.4二叉樹(shù)的基本運(yùn)算二叉樹(shù)的常用運(yùn)算有以下幾種：（1）bt=CreateBTree(str):根據(jù)二叉樹(shù)的廣義表表示法str建立二叉樹(shù)bt。（2）BTHeight(bt)：求一棵二叉樹(shù)bt的高度。（3）NodeCount(bt)：求一棵二叉樹(shù)bt的結(jié)點(diǎn)個(gè)數(shù)。（4）LeafCount(bt):求一棵二叉樹(shù)bt的葉子結(jié)點(diǎn)個(gè)數(shù)。（5）DispBTree(bt):以廣義表表示法輸出一棵二叉樹(shù)bt。返回到本節(jié)目錄5.3二叉樹(shù)的建立和遍歷5.3.1二叉樹(shù)的建立和輸出5.3.2二叉樹(shù)的遍歷5.3.3由遍歷序列恢復(fù)二叉樹(shù)返回到總目錄5.3.1二叉樹(shù)的建立和輸出1．二叉樹(shù)的建立二叉樹(shù)的建立是二叉樹(shù)的重要運(yùn)算之一，我們介紹的方法是：用字符ch掃描用廣義表表示法輸入的二叉樹(shù)的字符串str。分以下幾種情況：（1）若ch='('，則將前面剛創(chuàng)建的結(jié)點(diǎn)作為雙親結(jié)點(diǎn)進(jìn)棧，并置k=1，表示其后創(chuàng)建的結(jié)點(diǎn)將作為這個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)。（2）若ch=')'，表示棧中結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)處理完畢，退棧。（3）若ch=','，表示要?jiǎng)?chuàng)建一個(gè)結(jié)點(diǎn)，并根據(jù)k值建立它與棧中結(jié)點(diǎn)之間的聯(lián)系，當(dāng)k=1時(shí)，表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的左孩子結(jié)點(diǎn)，當(dāng)k=2時(shí)，表示這個(gè)結(jié)點(diǎn)作為棧中結(jié)點(diǎn)的右孩子結(jié)點(diǎn)。如此循環(huán)直到str處理完畢。算法中使用一個(gè)棧st保存雙親結(jié)點(diǎn)，top為其棧頂指針，k指定其后處理的結(jié)點(diǎn)是雙親結(jié)點(diǎn)（保存在棧中）的左孩子結(jié)點(diǎn)（k=1）還是右孩子結(jié)點(diǎn)（k=2）。返回到本節(jié)目錄1．二叉樹(shù)的建立（1）二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及相關(guān)類(lèi)型的定義如下：#defineNULL0/*定義空指針為0*/#defineMaxSize100/*樹(shù)的最大元素個(gè)數(shù)為100*/typedefcharElemType;/*重定義char為ElemType類(lèi)型*/typedefstructtnode{ElemTypedata;/*數(shù)據(jù)域*/structtnode*lchild,*rchild;/*左、右孩子指針*/}BTNode;/*二叉樹(shù)結(jié)點(diǎn)類(lèi)型*/返回到本節(jié)目錄1．二叉樹(shù)的建立算法（2）二叉樹(shù)的建立對(duì)應(yīng)的算法如算法所示。算法BTNode*CreateBTree(char*str){BTNode*bt,*st[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;bt=NULL;ch=str[j];while(ch!='\0'){switch(ch){case'(':top++;/*若是左括號(hào)，則先入棧*/st[top]=p;k=1;break;case')':top--;break;/*若是右括號(hào)，則出棧*/返回到本節(jié)目錄1．二叉樹(shù)的建立算法case',':k=2;break;/*若是逗號(hào)，則有右子樹(shù)*/default:/*若是其它字符，則生成新的二叉樹(shù)結(jié)點(diǎn)*/p=(BTNode*)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL; if(bt==NULL)bt=p;else{switch(k){case1:st[top]->lchild=p;break; case2:st[top]->rchild=p;break;}}}j++;ch=str[j];}return(bt);}返回到本節(jié)目錄5.3.1二叉樹(shù)的建立和輸出2．用廣義表表示法輸出二叉樹(shù)其過(guò)程是：對(duì)于非空二叉樹(shù)bt，先輸出其元素值，當(dāng)存在左孩子結(jié)點(diǎn)或右孩子結(jié)點(diǎn)時(shí)，輸出一個(gè)'('符號(hào)，然后遞歸處理左子樹(shù)，輸出一個(gè)','符號(hào)，遞歸處理右子樹(shù)，最后輸出一個(gè)')'。對(duì)應(yīng)的算法如算法。返回到本節(jié)目錄2．用廣義表表示法輸出二叉樹(shù)算法voidDispBTree(BTNode*bt){if(bt!=NULL){printf("%c",bt->data);if(bt->lchild!=NULL){printf("(");DispBTree(bt->lchild);if(bt->rchild!=NULL){printf(",");DispBTree(bt->rchild);}printf(")");}}}返回到本節(jié)目錄5.3.2二叉樹(shù)的遍歷一棵二叉樹(shù)由根結(jié)點(diǎn)（D）、根結(jié)點(diǎn)的左子樹(shù)（L）和根結(jié)點(diǎn)的右子樹(shù)（R）三部分組成。一般限定先左后右的次序，那么只有三種遍歷：DLR（根左右）、LDR（左根右）、LRD（左右根）。我們將這三種遍歷方法稱(chēng)作前（根）序遍歷，中（根）遍歷和后（根）序遍歷。也可以對(duì)二叉樹(shù)的每個(gè)層次的各結(jié)點(diǎn)按從左至右進(jìn)行遍歷（按層次遍歷），下面我們分別介紹這幾種遍歷方法。返回到本節(jié)目錄1.前（根）序遍歷二叉樹(shù)（DLR）有些教材稱(chēng)為先（根）序遍歷。若二叉樹(shù)為空，遍歷結(jié)束。否則依次執(zhí)行以下操作：

（1）訪(fǎng)問(wèn)根結(jié)點(diǎn)；

（2）前序遍歷根結(jié)點(diǎn)的左子樹(shù)；

（3）前序遍歷根結(jié)點(diǎn)的右子樹(shù)。前序遍歷的遞歸算法如算法所示。以圖5-10為例，進(jìn)行前序遍歷的輸出序列為：ABDCEGF。返回到本節(jié)目錄前序遍歷的遞歸算法算法voidPreOrder(BTNode*bt)/*前序遍歷二叉樹(shù)BT*/{if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/else{printf("%c",bt->data);/*輸出結(jié)點(diǎn)的數(shù)據(jù)域*/PreOrder(bt->lchild);/*前序遞歸遍歷左子樹(shù)*/PreOrder(bt->rchild);/*前序遞歸遍歷右子樹(shù)*/}}返回到本節(jié)目錄2.中（根）序遍歷二叉樹(shù)（LDR）若二叉樹(shù)為空，遍歷結(jié)束。否則依次執(zhí)行以下操作：

（1）中序遍歷根結(jié)點(diǎn)的左子樹(shù)；

（2）訪(fǎng)問(wèn)根結(jié)點(diǎn)；

（3）中序遍歷根結(jié)點(diǎn)的右子樹(shù)。中序遍歷的遞歸算法如算法所示。以圖5-10為例，進(jìn)行中序遍歷的輸出序列為：DBAGECF。返回到本節(jié)目錄中序遍歷的遞歸算法算法voidInOrder(BTNode*bt)/*中序遍歷二叉樹(shù)BT*/{if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/else{InOrder(bt->lchild);/*中序遞歸遍歷左子樹(shù)*/printf("%c",bt->data);/*輸出結(jié)點(diǎn)的數(shù)據(jù)域*/InOrder(bt->rchild);/*中序遞歸遍歷右子樹(shù)*/}}返回到本節(jié)目錄3．后（根）序遍歷二叉樹(shù)（LRD）若二叉樹(shù)為空，遍歷結(jié)束。否則依次執(zhí)行以下操作：

（1）后序遍歷根結(jié)點(diǎn)的左子樹(shù)；

（2）后序遍歷根結(jié)點(diǎn)的右子樹(shù)。

（3）訪(fǎng)問(wèn)根結(jié)點(diǎn)；后序遍歷的遞歸算法如算法所示。以圖5-10為例，進(jìn)行后序遍歷的輸出序列為：DBGEFCA。返回到本節(jié)目錄后序遍歷的遞歸算法算法voidPostOrder(BTNode*bt)/*后序遍歷二叉樹(shù)BT*/{if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/else{PostOrder(bt->lchild);/*后序遞歸遍歷左子樹(shù)*/PostOrder(bt->rchild);/*后序遞歸遍歷右子樹(shù)*/printf("%c",bt->data);/*輸出結(jié)點(diǎn)的數(shù)據(jù)域*/}}返回到本節(jié)目錄4．層次遍歷二叉樹(shù)在進(jìn)行層次遍歷時(shí)，對(duì)某一層的結(jié)點(diǎn)訪(fǎng)問(wèn)完后，再按照它們的訪(fǎng)問(wèn)次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左、右孩子順序訪(fǎng)問(wèn)，這樣一層一層進(jìn)行，先訪(fǎng)問(wèn)的結(jié)點(diǎn)其左、右孩子也要先訪(fǎng)問(wèn)。這樣的操作與隊(duì)列的原則比較符合，所以可以用一個(gè)環(huán)形隊(duì)列qu來(lái)實(shí)現(xiàn)。層次遍歷過(guò)程是先將根結(jié)點(diǎn)進(jìn)隊(duì)，在隊(duì)不空時(shí)循環(huán)；從隊(duì)列中出列一個(gè)結(jié)點(diǎn)*p，訪(fǎng)問(wèn)它；若它有左孩子結(jié)點(diǎn)，將左孩子結(jié)點(diǎn)進(jìn)隊(duì)；若它有右孩子結(jié)點(diǎn)，將右孩子結(jié)點(diǎn)進(jìn)隊(duì)，直到隊(duì)空為止。算法如算法所示。以圖5-10為例，進(jìn)行按層次遍歷的輸出序列為：ABCDEFG。返回到本節(jié)目錄層次遍歷的算法算法voidLevelOrder(BTNode*bt){BTNode*p;BTNode*qu[MaxSize];/*定義循環(huán)隊(duì)列，存放結(jié)點(diǎn)指針*/intfront,rear;/*定義隊(duì)頭隊(duì)尾指針*/front=rear=-1;/*空隊(duì)*/rear++;qu[rear]=bt;/*根結(jié)點(diǎn)指針進(jìn)入隊(duì)列*/返回到本節(jié)目錄層次遍歷的算法while(front!=rear)/*隊(duì)列不空時(shí)*/{front=(front+1)%MaxSize;p=qu[front];/*隊(duì)頭出隊(duì)列*/printf("%c",p->data);if(p->lchild!=NULL)/*有左孩子時(shí)將其進(jìn)隊(duì)*/{rear=(rear+1)%MaxSize;qu[rear]=p->lchild;}if(p->rchild!=NULL)/*有右孩子時(shí)將其進(jìn)隊(duì)*/{rear=(rear+1)%MaxSize;qu[rear]=p->rchild;}}}返回到本節(jié)目錄5.3.3由遍歷序列恢復(fù)二叉樹(shù)1．由前序和中序恢復(fù)二叉樹(shù)（1）根據(jù)前序序列確定樹(shù)的根（第一個(gè)結(jié)點(diǎn)），根據(jù)中序序列確定左子樹(shù)和右子樹(shù)；（2）分別找出左子樹(shù)和右子樹(shù)的根結(jié)點(diǎn)，并把左、右子樹(shù)的根結(jié)點(diǎn)聯(lián)到雙親結(jié)點(diǎn)上去；（3）再對(duì)左子樹(shù)和右子樹(shù)按此法找根結(jié)點(diǎn)和左、右子樹(shù)，直到子樹(shù)只剩下1個(gè)結(jié)點(diǎn)或2個(gè)結(jié)點(diǎn)或空為止。返回到本節(jié)目錄5.3.3由遍歷序列恢復(fù)二叉樹(shù)2．由中序和后序恢復(fù)二叉樹(shù)由二叉樹(shù)的后序序列和中序序列也可唯一地確定一棵二叉樹(shù)。其方法為：（1）根據(jù)后序序列找出根結(jié)點(diǎn)（最后一個(gè)），根據(jù)中序序列確定左、右子樹(shù)；（2）分別找出左子樹(shù)和右子樹(shù)的根結(jié)點(diǎn)，并把左、右子樹(shù)的根結(jié)點(diǎn)聯(lián)到雙親（parent）結(jié)點(diǎn)上去；（3）再對(duì)左子樹(shù)和右子樹(shù)按此法找根結(jié)點(diǎn)和左、右子樹(shù)，直到子樹(shù)只剩下1個(gè)結(jié)點(diǎn)或2個(gè)結(jié)點(diǎn)或空為止。返回到本節(jié)目錄5.4樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換5.4.1樹(shù)、森林轉(zhuǎn)換為二叉樹(shù)5.4.2二叉樹(shù)還原為樹(shù)、森林返回到總目錄5.4.1樹(shù)、森林轉(zhuǎn)換為二叉樹(shù)1．樹(shù)轉(zhuǎn)換成二叉樹(shù)將一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)的過(guò)程如下：（1）加線(xiàn)：樹(shù)中所有相鄰兄弟之間加一條連線(xiàn)。（2）抹線(xiàn)：對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)之間的連線(xiàn)，刪除它與其它孩子結(jié)點(diǎn)之間的連線(xiàn)。（3）旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)45°，使之成為二叉樹(shù)。返回到本節(jié)目錄【例5.3】將圖5-15（a）所示的樹(shù)轉(zhuǎn)換成二叉樹(shù)。轉(zhuǎn)換過(guò)程如圖5-15(b)、(c)、(d)所示。

（a）原始樹(shù)（b）相鄰兄弟之間加連線(xiàn)（虛線(xiàn)）（c）刪除與雙親結(jié)點(diǎn)的連線(xiàn)(d)轉(zhuǎn)換之后的二叉樹(shù)圖5-15一棵樹(shù)轉(zhuǎn)換成二叉樹(shù)的過(guò)程返回到本節(jié)目錄2．森林轉(zhuǎn)換為二叉樹(shù)將森林轉(zhuǎn)換為二叉樹(shù)的過(guò)程如下：（1）將森林中的每一棵樹(shù)轉(zhuǎn)換成相應(yīng)的二叉樹(shù)。（2）第一棵二叉樹(shù)保持不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)作為前一棵二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)，直到把最后一棵二叉樹(shù)作為其前一棵二叉樹(shù)的右子樹(shù)為止。此時(shí)所得到的二叉樹(shù)就是由森林轉(zhuǎn)換得到的二叉樹(shù)。返回到本節(jié)目錄【例5.4】將圖5-16（a）所示的森林轉(zhuǎn)換成二叉樹(shù)。解：轉(zhuǎn)換的過(guò)程如圖5-16（b）~5-16（e）所示。（a）森林（b）相鄰兄弟加連線(xiàn)（虛線(xiàn)）

（c）刪除與雙親結(jié)點(diǎn)的連線(xiàn)（d）每棵樹(shù)轉(zhuǎn)換成二叉樹(shù)返回到本節(jié)目錄【例5.4】（e）所有的二叉樹(shù)連接成一棵二叉樹(shù)圖5-16森林轉(zhuǎn)換成二叉樹(shù)的過(guò)程返回到本節(jié)目錄5.4.2二叉樹(shù)還原為樹(shù)、森林1．二叉樹(shù)還原為樹(shù)二叉樹(shù)還原為樹(shù)的過(guò)程如下：（1）加線(xiàn)：如果某結(jié)點(diǎn)的左孩子有右子樹(shù)，在該結(jié)點(diǎn)和其左孩子的右子樹(shù)的右分支上各結(jié)點(diǎn)間加線(xiàn)。（2）抹線(xiàn)：抹掉各結(jié)點(diǎn)的右子樹(shù)的右分支取上的連線(xiàn)。（3）旋轉(zhuǎn)整理得到樹(shù)。返回到本節(jié)目錄5.4.2二叉樹(shù)還原為樹(shù)、森林2．二叉樹(shù)還原為森林二叉樹(shù)還原為森林的過(guò)程如下：（1）連線(xiàn)：若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子、…、都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用連線(xiàn)連起來(lái)。（2）抹線(xiàn)：刪除原二叉樹(shù)中原來(lái)雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線(xiàn)。（3）整理由（1）、（2）兩步所得到的樹(shù)或森林，使之結(jié)構(gòu)層次分明。返回到本節(jié)目錄5.5哈夫曼樹(shù)相關(guān)概念和哈夫曼樹(shù)的定義5.5.2哈夫曼樹(shù)的構(gòu)造方法5.5.3哈夫曼編碼返回到總目錄相關(guān)概念和哈夫曼樹(shù)的定義1．路徑樹(shù)中一個(gè)結(jié)點(diǎn)與另一個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。樹(shù)中不是每對(duì)結(jié)點(diǎn)之間都有路徑，如兄弟結(jié)點(diǎn)之間就無(wú)路徑，而從根結(jié)點(diǎn)到樹(shù)中任一結(jié)點(diǎn)都存在一條路徑。2．路徑長(zhǎng)度樹(shù)中路徑上的分支數(shù)目。3．樹(shù)的路徑長(zhǎng)度根結(jié)點(diǎn)到樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。4．結(jié)點(diǎn)的權(quán)值所謂權(quán)值是人們根據(jù)需要為每個(gè)葉子結(jié)點(diǎn)賦予的一個(gè)數(shù)值。返回到本節(jié)目錄5．結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度是指從樹(shù)根到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)值的乘積。6．樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)中所有葉子結(jié)點(diǎn)的權(quán)值乘以該結(jié)點(diǎn)的路徑長(zhǎng)度之和。用公式可以表示為：其中，wk為第k個(gè)葉子結(jié)點(diǎn)的權(quán)值，lk是從根結(jié)點(diǎn)到第k個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度。7．哈夫曼樹(shù)哈夫曼樹(shù)又稱(chēng)為最優(yōu)二叉樹(shù)。它是n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)所構(gòu)成的所有二叉樹(shù)中帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)。返回到本節(jié)目錄求不同二叉樹(shù)的WPL如圖5-19（a）、（b）、（c）所示的三棵二叉樹(shù)，它們的帶權(quán)路徑長(zhǎng)度分別為：（a）WPL=2×2+3×2+4×2+6×2=30（b）WPL=2×3+3×3+4×2+6×1=29（c）WPL=4×3+6×3+3×2+2×1=38（a）（b）（c）圖5-19相同葉子結(jié)點(diǎn)所構(gòu)成的不同帶權(quán)路徑長(zhǎng)度的二叉樹(shù)返回到本節(jié)目錄5.5.2哈夫曼樹(shù)的構(gòu)造方法下面介紹哈夫曼樹(shù)的構(gòu)造方法，步驟如下：（1）將給定的n個(gè)權(quán)值{w1,w2,...,wn}作為n個(gè)根結(jié)點(diǎn)的權(quán)值構(gòu)造一個(gè)具有n棵二叉樹(shù)的森林{T1,T2,...,Tn}，其中每棵二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；（2）在森林中選取兩棵樹(shù)根結(jié)點(diǎn)的權(quán)值最小的二叉樹(shù)作為左右子樹(shù)構(gòu)造一棵新二叉樹(shù)，新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為原來(lái)兩棵樹(shù)根結(jié)點(diǎn)的權(quán)值之和；（3）在森林中，將上面選擇的這兩棵根結(jié)點(diǎn)的權(quán)值最小的二叉樹(shù)從森林中刪除，并將最新構(gòu)造的二叉樹(shù)加入到森林中；（4）重復(fù)上面（2）和（3），直到森林中只有一棵二叉樹(shù)為止。這棵二叉樹(shù)就是哈夫曼樹(shù)。返回到本節(jié)目錄【例5.7】假設(shè)有一組權(quán)值{2,3,7,8,12,9,6,19}，下面我們將利用這組權(quán)值演示構(gòu)造哈夫曼樹(shù)的過(guò)程。解：第一步：以這8個(gè)權(quán)值作為根結(jié)點(diǎn)的權(quán)值構(gòu)造具有8棵樹(shù)的森林。第二步：從中選擇兩個(gè)根的權(quán)值最小的樹(shù)2、3作為左右子樹(shù)構(gòu)造一棵新樹(shù)，并將這兩棵樹(shù)從森林中刪除，并將新樹(shù)5添加進(jìn)去。返回到本節(jié)目錄第三步：重復(fù)第二步過(guò)程，直到森林中只有一棵樹(shù)為止選擇5、6，將11放回。選擇7、8，將15放回。返回到本節(jié)目錄選擇9、11，將20放回選擇12、15，將27放回。返回到本節(jié)目錄選擇19、20，將39放回。選擇27、39，最后森林中只有一棵樹(shù)，結(jié)束操作，這棵樹(shù)就是哈夫曼樹(shù)。返回到本節(jié)目錄為了實(shí)現(xiàn)構(gòu)造哈夫曼樹(shù)的算法，設(shè)計(jì)哈夫曼樹(shù)中每個(gè)結(jié)點(diǎn)類(lèi)型如下：typedefstruct{chardata;/*結(jié)點(diǎn)值*/intweight;/*權(quán)值*/intparent;/*雙親結(jié)點(diǎn)下標(biāo)*/intlchild;/*左孩子結(jié)點(diǎn)下標(biāo)*/intrchild;/*右孩子結(jié)點(diǎn)下標(biāo)*/}HTCode;/*哈夫曼樹(shù)結(jié)點(diǎn)類(lèi)型*/返回到本節(jié)目錄用ht數(shù)組存放哈夫曼樹(shù)，對(duì)于具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)，總共有2n-1個(gè)結(jié)點(diǎn)。其算法思路是：n個(gè)葉子結(jié)點(diǎn)只有data和weight域值，先將所有2n-1個(gè)結(jié)點(diǎn)的parent、lchild和rchild域置為-1。處理每個(gè)非葉子結(jié)點(diǎn)ht[i]（存放在ht[n]～ht[2n-2]中）：從ht[0]～ht[i-2]中找出根結(jié)點(diǎn)（即其parent域?yàn)?1）最小的兩個(gè)結(jié)點(diǎn)ht[lnode]和ht[rnode]，將它們作為ht[i]的左右子樹(shù)，ht[lnode]和ht[rnode]雙親結(jié)點(diǎn)置為ht[i]，并且ht[i].weight=ht[lnode].weight+ht[rnode].weight。如此這樣直到所有的n-1個(gè)非葉子結(jié)點(diǎn)處理完畢。構(gòu)造哈夫曼樹(shù)的算法如算法。返回到本節(jié)目錄算法voidCreateHT(HTCodeht[],intn){inti,j,k,lnode,rnode;intmin1,min2;for(i=0;i<2*n-1;i++)/*將雙親、左、右孩子域置初值-1*/ht[i].parent=ht[i].lchild=ht[i].rchild=-1;for(i=n;i<2*n-1;i++){min1=min2=32767;/*兩個(gè)最小值置初值為系統(tǒng)最大值*/lnode=rnode=-1;返回到本節(jié)目錄for(k=0;k<i;k++){if(ht[k].parent==-1)if(min1>ht[k].weight) {min1=ht[k].weight;/*找出最小的權(quán)值*/lnode=k;/*最小權(quán)值的結(jié)點(diǎn)下標(biāo)值*/ }}for(k=0;k<i;k++){if(ht[k].parent==-1)if(min2>ht[k].weight&&k!=lnode) {min2=ht[k].weight;/*找出次最小的權(quán)值*/rnode=k;/*次最小權(quán)值的結(jié)點(diǎn)下標(biāo)值*/ }}返回到本節(jié)目錄ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}}返回到本節(jié)目錄5.5.3哈夫曼編碼1．什么是哈夫編碼？在進(jìn)行快速遠(yuǎn)距離的通信時(shí)，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0，1組成的二進(jìn)制代碼，稱(chēng)之為編碼。如果在編碼時(shí)考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長(zhǎng)的編碼，構(gòu)造一種不等長(zhǎng)編碼，則電文的代碼就可能更短。哈夫曼編碼是一種用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。返回到本節(jié)目錄5.5.3哈夫曼編碼2．生成哈夫曼編碼的方法要設(shè)計(jì)長(zhǎng)短不同的編碼，首先要做到不同字符的編碼不會(huì)混淆，即任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴（即不是另一個(gè)字符編碼的開(kāi)頭一部分），滿(mǎn)足這個(gè)條件的編碼叫做前綴編碼。即前綴編碼是指所編碼的字符可以通過(guò)前綴唯一地正確識(shí)別并譯出。利用哈夫曼樹(shù)就可以方便的設(shè)計(jì)。返回到本節(jié)目錄2．生成哈夫曼編碼的方法（1）構(gòu)造哈夫曼樹(shù)設(shè)需要編碼的字符集合為{d1，d2，…，dn}，它們?cè)陔娢闹谐霈F(xiàn)的次數(shù)集合為{w1，w2，…，wn}，以d1，d2，…，dn作為葉子結(jié)點(diǎn)，w1，w2，…，wn作為它們的權(quán)值，構(gòu)造一棵哈夫曼樹(shù)。（2）在哈夫曼樹(shù)上求葉結(jié)點(diǎn)的編碼。

規(guī)定哈夫曼樹(shù)中的左分支代表0，右分支代表1，則從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑分支組成的0和1的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼。返回到本節(jié)目錄【例5.8】設(shè)有A，B，C，D，E，F(xiàn)6個(gè)字符，其出現(xiàn)的頻度分別為、、、、、，試設(shè)計(jì)它們的哈夫曼編碼。解：將所有頻度全部乘以100，得到各字符的權(quán)值{6，2，4，3，7，12}，根據(jù)這組權(quán)值構(gòu)造的哈夫曼樹(shù)如圖5-21所示。并設(shè)哈夫曼樹(shù)的每個(gè)左分支為0，右分支為1進(jìn)行編碼.返回到本節(jié)目錄則得到各個(gè)字符的哈夫曼編碼為：

A：00B：1010C：100D：1011E：01F：11圖5-21哈夫曼編碼樹(shù)返回到本節(jié)目錄3.哈夫曼編碼的算法實(shí)現(xiàn)（1）設(shè)計(jì)哈夫曼編碼的數(shù)據(jù)類(lèi)型如下：typedefstruct{charcd[N];/*存放當(dāng)前結(jié)點(diǎn)的哈夫曼編碼*/intstart;/*start指向cd數(shù)組中的哈夫曼編碼最開(kāi)始字符*/}HCode;/*哈夫曼編碼存放類(lèi)型*/返回到本節(jié)目錄3.哈夫曼編碼的算法實(shí)現(xiàn)（2）生成哈夫曼編碼的算法由于哈夫曼樹(shù)中的每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼長(zhǎng)度不同，為此采用HCode類(lèi)型變量的cd[start]～cd[n]存放當(dāng)前結(jié)點(diǎn)的哈夫曼編碼。只需對(duì)葉子結(jié)點(diǎn)求哈夫曼編碼。對(duì)于當(dāng)前葉子結(jié)點(diǎn)ht[i]，先將對(duì)應(yīng)的哈夫曼編碼和hcd[i]的start域置初值n，找其雙親結(jié)點(diǎn)ht[f]，若當(dāng)前結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則在hcd[i]的cd數(shù)組中添加1，將start域減1。再對(duì)雙親結(jié)點(diǎn)進(jìn)行同樣的操作，如此直到無(wú)雙親結(jié)點(diǎn)即到達(dá)樹(shù)根結(jié)點(diǎn)，最后讓start指向哈夫曼編碼最開(kāi)始字符。具體算法如算法所示。返回到本節(jié)目錄算法voidCreateHCode(HTCodeht[],HCodehcd[],intn){inti,f,c;HCodehc;for(i=0;i<n;i++){=n;c=i;f=ht[i].parent;while(f!=-1){if(ht[f].lch