數(shù)據(jù)結(jié)構(gòu)樹和二叉樹

第6章樹和二叉樹本章主題：樹、二叉樹

教學(xué)目的：掌握樹和二叉樹的類型定義、運算及存儲結(jié)構(gòu)教學(xué)重點：樹的各種表示、各種存儲方式和運算，

二叉樹的概念及其運算和應(yīng)用教學(xué)難點：二叉樹的非遞歸運算及應(yīng)用

主要內(nèi)容：樹二叉樹

樹、森林與二叉樹的轉(zhuǎn)換

樹的應(yīng)用

1整理ppt本章學(xué)習(xí)導(dǎo)讀

本章主要介紹樹的根本概念，樹的存儲結(jié)構(gòu)，樹和二叉樹的遍歷等一些常用算法。通過本章學(xué)習(xí)，讀者應(yīng)該：1)熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。2)理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點的前驅(qū)和后繼的方法。3)熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及建立的算法。4)學(xué)會編寫實現(xiàn)樹的各種操作的算法。5)了解最優(yōu)二叉樹的特性，掌握建立最優(yōu)二叉樹和哈夫曼編碼的方法。2整理ppt

數(shù)據(jù)結(jié)構(gòu):線性結(jié)構(gòu)和非線性結(jié)構(gòu)

線性結(jié)構(gòu)(線性表,棧,隊列等)

非線性結(jié)構(gòu):至少存在一個數(shù)據(jù)元素有不止一個直接前驅(qū)或后繼(樹,圖等)

樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)是結(jié)點之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界國是大量存在的，例如家譜、行政組織機構(gòu)都可用樹形象地表示。樹在計算機領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程。等等。3整理ppt

6.1.1樹型結(jié)構(gòu)實例

1．家族樹

6.1樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

圖6-1家族樹

4整理ppt2．書的目錄結(jié)構(gòu)

圖6-2書的目錄

5整理ppt6.1.2樹的定義1．樹的定義樹(Tree)是n(n≥0)個結(jié)點的有限集(記為T)，T為空時稱為空樹，否那么它滿足以下兩個條件：(1)有且僅有一個結(jié)點沒有前驅(qū)，稱該結(jié)點為根結(jié)點(Root)；(2)除根結(jié)點以外，其余結(jié)點可分為m(m≥0)個互不相交的有限集合T0，Tl，…，Tm-1。其中每個集合又構(gòu)成一棵樹，樹T0，Tl，…，Tm-1被稱為根結(jié)點的子樹(Subree)。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個后繼。樹的邏輯結(jié)構(gòu)表示數(shù)據(jù)之間的關(guān)系是一對多，或者多對一的關(guān)系。它的結(jié)構(gòu)特點具有明顯的層次關(guān)系，是一種十分重要的非線性的數(shù)據(jù)結(jié)構(gòu)。6.1樹的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)

6整理ppt圖6-3樹的例如圖6-3(a)是一棵只有一個根結(jié)點的樹；圖6-3(b)是一棵有12個結(jié)點的樹，即T={A，B，C，…，K，L}。A是棵根，除根結(jié)點A之外，其余的11個結(jié)點分為三個互不相交的集合。T1，T2和T3是根A的三棵子樹，且本身又都是一棵樹。所以樹的定義是遞歸的。

返回7整理ppt2．樹的根本術(shù)語樹的結(jié)點包含一個數(shù)據(jù)元素及假設(shè)干指向其子樹的分支。1.樹的結(jié)點:包含一個DE和指向其子樹的所有分支;2.結(jié)點的度:一個結(jié)點擁有的子樹個數(shù),度為零的結(jié)點稱為葉結(jié)點;3.樹的度:樹中所有結(jié)點的度的最大值Max(D(I))含義:樹中最大分支數(shù)為樹的度;4.結(jié)點的層次及樹的深度:根為第一層,根的孩子為第二層,假設(shè)某結(jié)點為第k層,那么其孩子為k+1層.樹中結(jié)點的最大層次稱為樹的深度或高度5.森林:是m(m>=0)棵互不相的樹的集合森林與樹概念相近,相互很容易轉(zhuǎn)換.6.有序樹、無序樹如果樹中每棵子樹從左向右的排列擁有一定的順序，不得互換，那么稱為有序樹，否那么稱為無序樹。8整理ppt7.森林:是m〔m≥0〕棵互不相交的樹的集合。在樹結(jié)構(gòu)中，結(jié)點之間的關(guān)系又可以用家族關(guān)系描述，定義如下：8.孩子、雙親:結(jié)點子樹的根稱為這個結(jié)點的孩子，而這個結(jié)點又被稱為孩子的雙親。9.子孫:以某結(jié)點為根的子樹中的所有結(jié)點都被稱為是該結(jié)點的子孫。10.祖先:從根結(jié)點到該結(jié)點路徑上的所有結(jié)點。11.兄弟:同一個雙親的孩子之間互為兄弟。12.堂兄弟:雙親在同一層的結(jié)點互為堂兄弟。

9整理ppt3.樹的根本運算樹的根本運算主要有：⒈初始化操作INITIATE(T)：創(chuàng)立一棵空樹。⒉求根函數(shù)ROOT(T)：求樹T的根；ROOT(X)：求結(jié)點x所在樹的根。⒊求雙親函數(shù)PARENT(T,x)：在樹T中求x的雙親。⒋求第i個孩子函數(shù)CHILD(T,x,i)：在樹T中求結(jié)點x的第i個孩子。⒌建樹函數(shù)CRT-TREE(x,F)：建立以結(jié)點x為根，森林F為子樹的樹。6.遍歷樹操作TRAVERSE(T)：按順序訪問樹T中各個結(jié)點。

10整理ppt6.1.3樹的表示樹的邏輯表示方法有多種，常見的有：1．樹形圖表示法2．嵌套集合表示法〔文氏圖表示法〕3．凹入表示法4．廣義表表示法11整理ppt6.1.3樹的存儲結(jié)構(gòu)和線性表一樣，樹可以用順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)。樹的順序存儲結(jié)構(gòu)適合樹中結(jié)點比較“滿〞的情況。根據(jù)樹的非線性結(jié)構(gòu)特點，常用鏈?zhǔn)酱鎯Ψ绞絹肀硎緲?。樹常用的存儲方法有：雙親存儲表示法、孩子鏈表表示法和孩子兄弟鏈表表示法。1．雙親存儲表示法一般采用順序存儲結(jié)構(gòu)實現(xiàn)。用一組地址連續(xù)的存儲單元來存放樹的結(jié)點，每個結(jié)點有兩個域：data域-----存放結(jié)點的信息；parent域-----存放該結(jié)點雙親結(jié)點的位置特點：求結(jié)點的雙親很容易，但求結(jié)點的孩子需要遍歷整個向量。12整理ppt存儲結(jié)構(gòu)描述為：#defineMaxTreeSize100//定義數(shù)組空間的大小

typedefcharDataType；//定義數(shù)據(jù)類型

typedefstruct{DataTypedata；//結(jié)點數(shù)據(jù)intparent；//雙親指針，指示結(jié)點的雙親在數(shù)組中的位置}PTreeNode；typedefstruct{

PTreeNodenodes[MaxTreeSize];intn；//結(jié)點總數(shù)}PTree；PTreeT；//T是雙親鏈表13整理ppt2．孩子鏈表表示法這是樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)。每個結(jié)點的孩子用單鏈表存儲，稱為孩子鏈表。n個結(jié)點可以有n個孩子鏈表〔葉結(jié)點的孩子鏈表為空表〕。n個孩子鏈表的頭指針用一個向量表示。圖6-6樹的孩子鏈表結(jié)構(gòu)

頭指針向量孩子鏈表特點：與雙親相反，求孩子易，求雙親難。14整理ppt存儲結(jié)構(gòu)描述為：

typedefstructCTNode{intchild;//孩子鏈表結(jié)點

structCTNode*next;}*ChildPtr;typedefstruct//孩子鏈表頭結(jié)點{ElemTypedata;//結(jié)點的數(shù)據(jù)元素ChildPtrfirstchild;//孩子鏈表頭指針}CTBox;typedefstruct{CTBoxnodes[MaxTreeSize];intn,r,//數(shù)的結(jié)點數(shù)和根結(jié)點的位置}CTree;15整理ppt孩子鏈表表示法的類型說明typedefstructCnode//DataType和MaxTreeSize由用戶定義{//孩子鏈表結(jié)點

intchild;//孩子結(jié)點在數(shù)組中對應(yīng)的下標(biāo)

structCNode*next;}Cnode;typedefstruct//孩子鏈表頭結(jié)點{

DataTypedata;//存放樹中結(jié)點數(shù)據(jù)CNode*firstchild;//孩子鏈表的頭指針}PTNode;typedefstruct{PTNodenodes[MaxTreeSize];Intn,root;//樹的結(jié)點數(shù)和根結(jié)點的位置}Ctree;CtreeT;//T的孩子鏈表表示16整理ppt3．孩子兄弟鏈表表示法孩子兄弟鏈表表示法也是樹的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。用二叉鏈表作為樹的存儲結(jié)構(gòu)，每個結(jié)點的左鏈域指向該結(jié)點的第一個孩子，右鏈域指向下一個兄弟結(jié)點。由于結(jié)點中的兩個指針指示的分別為“孩子〞和“兄弟〞，故稱為“孩子-兄弟鏈表〞。這種結(jié)構(gòu)也稱為二叉鏈表。圖6-7樹的孩子-兄弟存儲結(jié)構(gòu)

特點：雙親只管長子長子連接兄弟17整理ppt樹的孩子兄弟鏈表的存儲結(jié)構(gòu)描述為：typedefstructCSNode{ElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;孩子兄弟存儲結(jié)構(gòu)的最大優(yōu)點是可以方便地實現(xiàn)樹和二叉樹的相互轉(zhuǎn)換和樹的各種操作。但是，孩子兄弟存儲結(jié)構(gòu)的缺點也是查找當(dāng)前結(jié)點的雙親結(jié)點比較麻煩，需要從樹根結(jié)點開始逐個結(jié)點比較查找。18整理ppt6.1.5樹和森林的遍歷1．樹的遍歷所謂樹的遍歷，就是按照某種順序依次訪問樹中各個結(jié)點，并使得每個結(jié)點只被訪問一次。也就是把非線性結(jié)構(gòu)的樹結(jié)點變成線性序列的一種方式。樹的遍歷可以按深度優(yōu)先遍歷，也可以按照廣度優(yōu)先〔按層次〕遍歷。深度優(yōu)先遍歷通常有兩種方式：前序遍歷和后序遍歷。(1)前序遍歷的遞歸定義：

假設(shè)樹T非空，那么：訪問根結(jié)點R；按照從左到右的順序依次前序遍歷根結(jié)點R的各子樹T1，T2，…，Tk。19整理ppt(2)后序遍歷的遞歸定義：假設(shè)樹T非空，那么：按照從左到右的順序依次后序遍歷根T的各子樹Tl，T2，…，Tk；訪問根結(jié)點R。(3)廣度優(yōu)先〔按層〕遍歷廣度優(yōu)先〔按層次〕遍歷定義為：先訪問第一層結(jié)點〔即樹根結(jié)點〕，再從左至右訪問第二層結(jié)點，依次按層訪問……，直到樹中結(jié)點全部被訪問為止。對圖6-6(a)中的樹進(jìn)行按層次遍歷得到樹的廣度優(yōu)先遍歷序列為：ABCDEFG。說明：①前序遍歷一棵樹恰好等價于前序遍歷該樹所對應(yīng)的二叉樹?！?.2節(jié)將介紹二叉樹〕②后序遍歷樹恰好等價于中序遍歷該樹所對應(yīng)的二叉樹。20整理ppt樹的先序遍歷算法描述如下：voidPreorder(Btree*root)//先根遍歷k叉樹{if(root!=NULL){printf(“%c\n〞,root->data);//訪問根結(jié)點for(i=0;i<k;i++)preorder(root->t[i]);//遞歸前序遍歷每一個子結(jié)點}}

21整理ppt2．森林的遍歷森林的深度優(yōu)先遍歷通常也有兩種方式：前序遍歷和后序遍歷。(1)前序遍歷森林假設(shè)森林非空，那么：訪問森林中第一棵樹的根結(jié)點；前序遍歷第一棵樹中根結(jié)點的各子樹所構(gòu)成的森林前序遍歷去掉第一棵樹外其它樹構(gòu)成的森林。(2)后序遍歷森林假設(shè)森林非空，那么:后序遍歷森林中第一棵樹中根結(jié)點的各子樹所構(gòu)成的森林；訪問第一棵樹的根結(jié)點；后序遍歷去掉第一棵樹外其它樹構(gòu)成的森林。當(dāng)用二叉鏈表作為樹和森林的存儲結(jié)構(gòu)時，樹和森林的前序遍歷和后序遍歷可用二叉樹的前序遍歷和中序遍歷算法來實現(xiàn)。22整理ppt2．森林的遍歷森林的深度優(yōu)先遍歷通常也有兩種方式：前序遍歷和后序遍歷。(1)前序遍歷森林假設(shè)森林非空，那么：訪問森林中第一棵樹的根結(jié)點；前序遍歷第一棵樹中根結(jié)點的各子樹所構(gòu)成的森林前序遍歷去掉第一棵樹外其它樹構(gòu)成的森林。(2)后序遍歷森林假設(shè)森林非空，那么:后序遍歷森林中第一棵樹中根結(jié)點的各子樹所構(gòu)成的森林；訪問第一棵樹的根結(jié)點；后序遍歷去掉第一棵樹外其它樹構(gòu)成的森林。23整理ppt圖6-8森林和對應(yīng)的二叉樹

24整理ppt

6.2.1二叉樹的定義與性質(zhì)

二叉樹(BinaryTree)是另一種重要的樹型結(jié)構(gòu)。是度為2的有序樹，它的特點是每個結(jié)點至多有兩棵子樹。和樹結(jié)構(gòu)的定義類似，二叉樹的定義也可以用遞歸形式給出。1．二叉樹的遞歸定義二叉樹(BinaryTree)是n(n≥0)個結(jié)點的有限集。它或者是空集(n=0)，或者同時滿足以下兩個條件：(1)有且僅有一個根結(jié)點；(2)其余的結(jié)點分成兩棵互不相交的左子樹和右子樹。

6.2二叉樹25整理ppt二叉樹與樹有區(qū)別：樹至少應(yīng)有一個結(jié)點，而二叉樹可以為空；樹的子樹沒有順序，但如果二叉樹的根結(jié)點只有一棵子樹，必須明確區(qū)分它是左子樹還是右子樹，因為兩者將構(gòu)成不同形態(tài)的二叉樹。因此，二叉樹不是樹的特例。它們是兩種不同的數(shù)據(jù)結(jié)構(gòu)。二叉樹有5種根本形態(tài)：圖6-9二叉樹的五種根本形態(tài)(a)空二叉樹(b)只有根結(jié)點的二叉樹(c)右子樹為空的二叉樹

(d)左子樹為空的二叉樹(e)左右子樹均不為空的二叉樹

26整理ppt兩種特殊形態(tài)的二叉樹：滿二叉樹和完全二叉樹。(1)滿二叉樹(FullBinaryTree)

深度為k，且有2k-1個結(jié)點的二叉樹。特點：〔1〕每一層上結(jié)點數(shù)都到達(dá)最大〔2〕度為1的結(jié)點n1=0，樹葉都在最下一層上。結(jié)點層序編號方法：從根結(jié)點起從上到下逐層〔層內(nèi)從左到右〕對二叉樹的結(jié)點進(jìn)行連續(xù)編號。1237654K=3n=23-1=7滿二叉樹27整理ppt

(2)

完全二叉樹(CompleteBinaryTree)

深度為k，結(jié)點數(shù)為n的二叉樹，當(dāng)且僅當(dāng)每個結(jié)點的編號都與相同深度的滿二叉樹中從1到n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。圖6-11完全二叉樹完全二叉樹的特點：〔1〕每個結(jié)點i的左子樹的深度Lhi-其結(jié)點i的右子樹的深度Rhi等于0或1，即葉結(jié)點只可能出現(xiàn)在層次最大或次最大的兩層上?！?〕完全二叉樹結(jié)點數(shù)n滿足2k-1-1＜n≤2k-1〔3〕滿二叉樹一定是完全二叉樹，反之不成立。4521328整理ppt1324653241LH1=3RH1=1LH1-RH1=2

非完全二叉樹非完全二叉樹LH2=0RH2=1LH2-RH2=0-1=-129整理ppt2．二叉樹的性質(zhì)性質(zhì)1在二叉樹的第i層上至多有2i-1個結(jié)點(i≥1)。性質(zhì)2深度為k的二叉樹至多有2k-1個結(jié)點(k≥1)?！采疃纫欢?，二叉樹的最大結(jié)點數(shù)也確定〕性質(zhì)3二叉樹中,終端結(jié)點數(shù)n0與度為2的結(jié)點數(shù)n2有如下關(guān)系:n0=n2+1性質(zhì)4結(jié)點數(shù)為n的完全二叉樹，其深度為log2n+l性質(zhì)5在按層序編號的n個結(jié)點的完全二叉樹中，任意一結(jié)點i(1≤i≤n)有：⑴i=1時，結(jié)點i是樹的根；否那么，結(jié)點i的雙親為結(jié)點i/2(i>1)。⑵2i＞n時，結(jié)點i無左孩子，為葉結(jié)點；否那么，結(jié)點i的左孩子為結(jié)點2i。⑶2i+1＞n時，結(jié)點i無右孩子；否那么，結(jié)點i的右孩子為結(jié)點2i+1。30整理ppt6.2.2二叉樹的存儲結(jié)構(gòu)同線性表一樣，二叉樹的存儲結(jié)構(gòu)也有順序和鏈表兩種結(jié)構(gòu)。1．順序存儲結(jié)構(gòu)

用一組地址連續(xù)的存儲單元，以層序順序存放二叉樹的數(shù)據(jù)元素，結(jié)點的相對位置蘊含著結(jié)點之間的關(guān)系。

完全二叉樹DCGFEBA

bt[3]的雙親為

3/2

=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩子在bt[2i+1]=bt[7]中。1234567891011ABCDEFG000031整理ppt

這種存儲結(jié)構(gòu)適合于完全二叉樹，既不浪費存儲空間，又能很快確定結(jié)點的存放位置、結(jié)點的雙親和左右孩子的存放位置，但對一般二叉樹，可能造成存儲空間的大量浪費。D二叉樹CGFEBA123456789101112ABCDE0000FG0000

一般二叉樹也按完全二叉樹形式存儲，無結(jié)點處用0表示。32整理ppt例如：深度為k，且只有k個結(jié)點的右單枝樹(每個非葉結(jié)點只有右孩子)，需2k-1個單元，即有2k-1-k個單元被浪費。⒉鏈?zhǔn)酱鎯Y(jié)構(gòu)〔二叉鏈表〕設(shè)計不同的結(jié)點結(jié)構(gòu)，可以構(gòu)成不同的鏈?zhǔn)酱鎯Y(jié)構(gòu)。常用的有：二叉鏈表三叉鏈表線索鏈表用空鏈域存放指向前驅(qū)或后繼的線索33整理ppt由于二叉樹每個結(jié)點至多只有2個孩子，分別為左孩子和右孩子。因此可以把每個結(jié)點分成三個域：一個域存放結(jié)點本身的信息，另外兩個是指針域，分別存放左、右孩子的地址。每個結(jié)點的結(jié)構(gòu)表示為：其中左鏈域lchild為指向左孩子的指針，右鏈域rchild為指向右孩子的指針，數(shù)據(jù)域data表示結(jié)點的值。假設(shè)某結(jié)點沒有左孩子或右孩子，其相應(yīng)的鏈域為空指針。對應(yīng)的結(jié)構(gòu)類型定義如下：typedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BTree,*tree;其中，tree是指向根結(jié)點的指針。

34整理ppt二叉鏈表的結(jié)點結(jié)構(gòu)

lchilddatarchildD

二叉樹CEBAACBDE∧∧∧∧∧∧二叉鏈表說明：●一個二叉鏈表由根指針root唯一確定。假設(shè)二叉樹為空，那么root=NULL；假設(shè)結(jié)點的某個孩子不存在，那么相應(yīng)的指針為空?！窬哂衝個結(jié)點的二叉鏈表中，共有2n個指針域。其中只有n-1個用來指示結(jié)點的左、右孩子，其余的n+1個指針域為空。35整理pptlchilddataparentrchildD

二叉樹CEBAACBDE∧∧∧∧∧∧∧三叉鏈表3．帶雙親指針的二叉鏈表由于經(jīng)常要在二叉樹中尋找某結(jié)點的雙親時，可在每個結(jié)點上再加一個指向其雙親的指針parent，形成一個帶雙親指針的二叉鏈表。就是三叉鏈表。三叉鏈表的結(jié)點結(jié)構(gòu)性質(zhì)6

含有n個結(jié)點的二叉鏈表中，有n+1個空鏈域。二叉樹存儲方法的選擇，主要依賴于所要實施的各種運算的頻度。36整理ppt6.2.3二叉樹的根本運算及實現(xiàn)1．二叉樹的根本運算〔1〕Inittree(&T)功能：初始化操作(建立一棵空的二叉樹)?！?〕Root(T)功能：求二叉樹的根?！?〕Parent(T,x)功能：求二叉樹T中值為x的結(jié)點的雙親?！?〕Lchild(T,x)功能：求結(jié)點的左孩子?！?〕Rchild(T,x)功能：求結(jié)點的右孩子?！?〕Traverse(T)功能：遍歷或訪問二叉樹T?！?〕creatree(&T)功能：創(chuàng)立二叉樹T37整理ppt2．二叉樹局部運算的算法描述(1)創(chuàng)立二叉樹creatree(&root,str)：功能：創(chuàng)立二叉樹T。算法描述如下：voidcreatree(BTree**b,char*str){BTree*stack[MAXSIZE],p=NULL;inttop=-1,k,j=0;charch;*b=NULL;ch=str[j];while(ch!=’\0’){switch(ch){case’(’：top++;stack[top]=p;k=1,break;//為左結(jié)點case’)’：top--;break;case’,’：k=2;break;//為右結(jié)點default：p=(BTree*)malloc(sizeof(BTree));p->data=ch;p->lchild=p->rchild=NULL;38整理ppt

p->data=ch;p->lchild=p->rchild=NULL;if(*b==NULL)//為根結(jié)點*b=p;else{switch(k){case1：stack[top]->lchild=p;break;case2：stack[top]->rchild=p;break;}}}j++;ch=str[j];}}39整理ppt(2)查找給定的結(jié)點find(root，x)(3)找左孩子結(jié)點lchild(p)或右孩子結(jié)點rchild(p)(4)輸出二叉樹disptree(root)40整理ppt6.3.1遍歷二叉樹在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點，或者對樹中全部結(jié)點逐一進(jìn)行某種處理。這就引入了遍歷二叉樹的問題，即如何按某條搜索路徑訪問樹中的每一個結(jié)點，使得每一個結(jié)點僅切僅被訪問一次。

遍歷二叉樹：指按一定的規(guī)律對二叉樹的每個結(jié)點，訪問且僅訪問一次的處理過程。

遍歷對線性結(jié)構(gòu)是容易解決的。而二叉樹是非線性的，因而需要尋找一種規(guī)律，使二叉樹上的結(jié)點能排列在一個線性隊列上，從而便于遍歷。

6.3

遍歷二叉樹和線索二叉樹

41整理ppt訪問是一種抽象操作，是對結(jié)點的某種處理，例如可以是求結(jié)點的度、或?qū)哟?、打印結(jié)點的信息，或做其他任何工作。一次遍歷后，使樹中結(jié)點的非線性排列，按訪問的先后順序變?yōu)槟撤N線性排列。遍歷的次序：假設(shè)以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點和遍歷右子樹，遍歷整個二叉樹那么有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。假設(shè)規(guī)定先左后右，那么只有前三種情況，分別規(guī)定為：DLR——先〔根〕序遍歷，LDR——中〔根〕序遍歷，LRD——后〔根〕序遍歷。1．遍歷方案LDR中序遍歷；LRD后序遍歷；DLR先序遍歷42整理ppt1〕中序遍歷二叉樹算法思想:假設(shè)二叉樹非空，那么：1〕中序遍歷左子樹2〕訪問根結(jié)點3〕中序遍歷右子樹算法描述:voidInorder(BiTreebt){//bt為根結(jié)點指針

if(bt){//根非空

Inorder(bt->lchild);

visit(bt->data)；Inorder(bt->rchild);}}2〕后序遍歷二叉樹算法思想:假設(shè)二叉樹非空，那么：1〕后序遍歷左子樹2〕后序遍歷右子樹3〕訪問根結(jié)點算法描述:voidPostorder(BiTreebt){//bt為根結(jié)點指針

if(bt){Postorder(bt->lchild);Postorder(bt->rchild);

visit(bt->data)；

}}43整理ppt3〕先序遍歷二叉樹算法思想:假設(shè)二叉樹非空，那么：1〕訪問根結(jié)點2〕先序遍歷左子樹3〕先序遍歷右子樹算法描述:voidPreorder(BiTreebt){//bt為根結(jié)點指針

if(bt){//根非空

visit(bt->data)；Preorder(bt->lchild);Preorder(bt->rchild);}}例：表達(dá)式a+b×(c-d)-e/facdef－b×＋－+遍歷結(jié)果:中序:a+b×c-d-e/f后序:abcd-×+ef/-先序:-+a×b-cd/ef44整理ppt〔1〕先序遍歷的遞歸算法如下〔假定結(jié)點的元素值為字符型〕：#include"stdio.h"typedefcharElemType;typedefstructnode//定義鏈表結(jié)構(gòu){ElemTypedata;//定義結(jié)點值structnode*lchild;//定義左子結(jié)點指針structnode*rchild;//定義右子結(jié)點指針}BTree;preorder(BTree*root)//前序遍歷{if(root!=NULL)//如果不是空結(jié)點{printf(“%c\n〞,root->data);//輸出當(dāng)前結(jié)點值preorder(root->lchild);//遞歸前序遍歷左子結(jié)點preorder(root->rchild);//遞歸前序遍歷右子結(jié)點}return;//結(jié)束}2．遍歷算法45整理pptvoidinorder(BTree*root)//中序遍歷{if(root!=NULL)//如果不是空結(jié)點{inorder(root->lchild);//遞歸中序遍歷左子結(jié)點printf(“%c\n〞,root->data);//輸出當(dāng)前結(jié)點值inorder(root->rchild);//遞歸中序遍歷右子結(jié)點}}

(3)后序遍歷的算法實現(xiàn)voidpostorder(BTree*root)//后序遍歷{if(root!=NULL)//如果不是空結(jié)點{postorder(root->lchild);//遞歸后序遍歷左子結(jié)點postorder(root->rchild);//遞歸后序遍歷右子結(jié)點printf(“%c\n〞,root->data);//輸出當(dāng)前結(jié)點值}}〔2〕中序遍歷的遞歸算法如下〔假定結(jié)點的元素值為字符型〕：46整理pptvoidinorder(BiTreebt){InitStack(s)；Push(s,bt)；while(!StackEmpty(s)){

while(GetTop(s)){Push(s,GetTop(s)->lchild)；

p=POP(s)；if(!StackEmpty(s)){visit(GetTop(s)->data)；p=Pop(s)；Push(s,p->rchild);}}}}中序遍歷非遞歸算法,s為存儲二叉樹結(jié)點指針棧：操作過程：根結(jié)點先進(jìn)棧，左結(jié)點緊跟根后面進(jìn)棧,右結(jié)點在根出棧后入棧；

每個結(jié)點都要進(jìn)一次和出一次棧，并且總是訪問棧頂元素，因此，算法正確，時間復(fù)雜度為O(n)。47整理ppt通過上述三種不同的遍歷方式得到三種不同的線性序列，它們的共同的特點是有且僅有一個開始結(jié)點和一個終端結(jié)點，其余各結(jié)點都有且僅有一個前驅(qū)結(jié)點和一個后繼結(jié)點。從二叉樹的遍歷定義可知，三種遍歷算法的不同之處僅在于訪問根結(jié)點和遍歷左右子樹的先后關(guān)系。如果在算法中隱去和遞歸無關(guān)的語句printf()，那么三種遍歷算法是完全相同的。遍歷二叉樹的算法中的根本操作是訪問結(jié)點，顯然，不管按那種方式進(jìn)行遍歷，對含n個結(jié)點的二叉樹，其時間復(fù)雜度均為O(n)。所含輔助空間為遍歷過程中占的最大容量，即樹的深度。最壞的情況下為n，那么空間復(fù)雜度也為O(n)。48整理ppt3．二叉鏈表的構(gòu)造(1)根本思想利用遍歷可以實現(xiàn)對結(jié)點的一些操作，如求結(jié)點的雙親，求結(jié)點的孩子等。還可以在遍歷過程中生成結(jié)點，建立二叉樹的存儲結(jié)構(gòu)。前面介紹過用棧建立二叉樹，此處介紹一種基于先序遍歷的二叉樹構(gòu)造方式，即以二叉樹的先序序列為輸入構(gòu)造二叉鏈表。先序序列中必須參加虛結(jié)點以示空指針的位置。(2)構(gòu)造算法〔舉例說明〕49整理ppt【例6-4】建立圖6-13(a)所示二叉樹，其輸入的先序序列是：ABD∮G∮∮CE∮∮F∮∮?！窘狻考僭O(shè)虛結(jié)點輸入時以空格字符表示，相應(yīng)的構(gòu)造算法為：voidCreateBinTree(BTree**T){//構(gòu)造二叉鏈表。T是指向根指針的指針，故修改*T就修改了實參(根指針)本身

charch;

if((ch=getchar())==“〞)*T=NULL;//讀入空格，將相應(yīng)指針置空

else//讀入非空格

{*T=(BTree*)malloc(sizeof(BTree));//生成結(jié)點

(*T)->data=ch；

CreateBinTree(&(*T)->lchild)；//構(gòu)造左子樹

CreateBinTree(&(*T)->rchild)；//構(gòu)造右子樹

}}調(diào)用該算法時，應(yīng)將待建立的二叉鏈表的根指針的地址作為實參。50整理ppt6.3.2線索二叉樹

⒈問題的提出：通過遍歷二叉樹可得到結(jié)點的一個線性序列，在線性序列中，很容易求得某個結(jié)點的直接前驅(qū)和后繼。但是在二叉樹上只能找到結(jié)點的左孩子、右孩子，結(jié)點的前驅(qū)和后繼只有在遍歷過程中才能得到，那么，如何保存遍歷二叉樹后動態(tài)得到的線性序列，以便快速找到某個結(jié)點的直接前驅(qū)和后繼？

2.分析：

n個結(jié)點有n-1個前驅(qū)和n-1個后繼；一共有2n個鏈域，其中：n+1個空鏈域，n-1個指針域；因此,可以用空鏈域來存放結(jié)點的前驅(qū)和后繼。線索二叉樹就是利用n+1個空鏈域來存放結(jié)點的前驅(qū)和后繼結(jié)點的信息。51整理ppt3.線索二叉樹：有效利用二叉鏈表中空的存儲空間，指定原有的孩子指針為空的域來存放指向前驅(qū)和后繼的信息，這樣的指針被稱為“線索〞。加線索的過程稱為線索化，由此得到的二叉樹稱作線索二叉樹。⑴結(jié)點結(jié)構(gòu)在二叉鏈表中增加ltag和rtag兩個標(biāo)志域假設(shè)結(jié)點有左子樹，那么左鏈域lchild指示其左孩子〔ltag=0〕；否那么，令左鏈域指示其前驅(qū)〔ltag=1〕；假設(shè)結(jié)點有右子樹，那么右鏈域rchild指示其右孩子〔rtag=0〕；否那么，令右鏈域指示其后繼〔rtag=1〕；52整理ppt中序、先序和后序線索二叉樹中所有實線均相同，所有結(jié)點的標(biāo)志位取值也完全相同，只是當(dāng)標(biāo)志位取1時，不同的線索二叉樹將用不同的虛線表示。按中序遍歷得到的線索二叉樹稱為中序線索二叉樹；按先序遍歷得到的線索二叉樹稱為先序線索二叉樹；按后序遍歷得到的線索二叉樹稱為后序線索二叉樹；〔2〕整體結(jié)構(gòu)增設(shè)一個頭結(jié)點，令其lchild指向二叉樹的根結(jié)點，ltag=0、rtag=1；并將該結(jié)點作為遍歷訪問的第一個結(jié)點的前驅(qū)和最后一個結(jié)點的后繼；最后用頭指針指示該頭結(jié)點。53整理ppt圖6-14線索二叉樹

54整理ppt線索二叉樹的存儲結(jié)點可描述如下：structnode{ElemenTypedata;//數(shù)據(jù)域intltag;//左標(biāo)志域intrtag;//右標(biāo)志域structnode*lchild;//左指針域structnode*rchild;//右指針域}BTree;同樣，線索二叉樹根據(jù)遍歷規(guī)那么的不同，可分為前序線索二叉樹、中序線索二叉樹、后序線索二叉樹。55整理ppt建立中序線索二叉樹的算法：voidthread(BTree**current,BTree**pre){if(*current!=NULL){thread(&(*current)->lchild,pre);//左子樹線索化

if((*current)->lchild==NULL){(*current)->lchild=*pre;//建立當(dāng)前結(jié)點的前驅(qū)線索(*current)->ltag=1;}if((*pre)->rchild==NULL){(*pre)->rchild=*current;//建立前驅(qū)結(jié)點的后繼線索(*pre)->rtag=1;}*pre=*current;thread(&(*current)->rchild,pre);//右子樹線索化}}56整理pptBTree*creathread(BTree*b)//中序線索化二叉樹{BTree*pre,*root,*current;root=(BTree*)malloc(sizeof(BTree));//創(chuàng)立根結(jié)點root->data=’r’;//值’r’表示根結(jié)點root->ltag=1;root->rtag=0;if(b==NULL);//空二叉樹{root->lchild=root;root->rchild=root;}else57整理pptelse{current=root->lchild=b;root->ltag=0;pre=root;//pre是前驅(qū)結(jié)點，供加線索用thread(¤t,&pre);//中序遍歷線索化二叉樹pre->rchild=root;//最后處理，參加指向根結(jié)點的線索pre->rtag=1;root->rchild=pre;//根結(jié)點右線索化root->rtag=1;}returnroot；}58整理ppt１．樹與二叉樹的對應(yīng)關(guān)系樹與二叉樹均可用二叉鏈表作為存儲結(jié)構(gòu)，因此給定一棵樹，用二叉鏈表存儲，可唯一對應(yīng)一棵二叉樹，反之亦然。2．樹轉(zhuǎn)換成二叉樹將一棵樹轉(zhuǎn)化為等價的二叉樹方法如下：(1)在樹中各兄弟〔堂兄弟除外〕之間加一根連線。(2)對于任一結(jié)點，只保存它與最左孩子的連線外，刪去它與其余孩子之間的連線。(3)以樹根為軸心，將整棵樹按順時鐘方向旋轉(zhuǎn)約45°。特點：根無右子樹6.4樹、森林與二叉樹的轉(zhuǎn)換59整理ppt圖6-15樹轉(zhuǎn)換成二叉樹

圖6-16森林和對應(yīng)的二叉樹

60整理ppt3．森林轉(zhuǎn)換成二叉樹樹和森林都可轉(zhuǎn)換成二叉樹，但樹轉(zhuǎn)換成二叉樹后根結(jié)點無右分支，而森林轉(zhuǎn)換后的二叉樹，其根結(jié)點有右分支。將森林轉(zhuǎn)化為二叉樹方法如下：(1)將森林中的每一棵樹轉(zhuǎn)換成等價的二叉樹。(2)保存第一棵二叉樹，自第二棵二叉樹始，依次將后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當(dāng)所有的二叉樹依此相連后，所得到的二叉樹就是由森林轉(zhuǎn)化成的二叉樹。(3)以樹根為軸心，將整棵樹按順時鐘方向旋轉(zhuǎn)約45°。轉(zhuǎn)換過程如圖圖6-16。61整理ppt4．二叉樹轉(zhuǎn)換成森林將當(dāng)前根結(jié)點和其左子樹作為森林的一棵樹,并將其右子樹作為森林的其他子樹；重復(fù)上面直到某結(jié)點的右子樹為空。JIHGFEBCDAT1BCDAFET2T3JIHG62整理ppt樹型結(jié)構(gòu)具有廣泛的應(yīng)用領(lǐng)域，常見的有：二叉排序樹、哈夫曼樹和判定樹等。6.5.1二叉排序樹二叉排序樹T是一棵二叉樹，或者為空，或者滿足下面條件：〔1〕假設(shè)T的根結(jié)點的左子樹非空，那么左子樹中所有結(jié)點的值均小于根結(jié)點值；〔2〕假設(shè)T的根結(jié)點的右子樹非空，那么右子樹中所有結(jié)點的值均大于根結(jié)點值；〔3〕T的左右子樹也分別為二叉排序樹。二叉排序樹又稱二叉查找樹，是一種動態(tài)樹表。它把查找和插入操作集為一體，或查找成功或插入。具體的查找和插入方法將在第9章介紹。6.5二叉樹的應(yīng)用

63整理ppt6.5.2路徑長度和最優(yōu)二叉樹〔哈夫曼樹〕哈夫曼〔Huffman〕樹又稱最優(yōu)二叉樹或最優(yōu)搜索樹，是一種帶權(quán)路徑長度最短的二叉樹。在許多應(yīng)用中，常常賦給樹中結(jié)點一個有某種意義的實數(shù)，稱此實數(shù)為該結(jié)點的權(quán)。從樹根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點上權(quán)的乘積稱為結(jié)點的帶權(quán)路徑長度(WPL)。樹中所有葉子結(jié)點的帶權(quán)路徑長度之和稱為該樹的帶權(quán)路徑長度，通常記為：兩結(jié)點間的路徑：從一結(jié)點到另一結(jié)點所經(jīng)過的結(jié)點序列路徑長度：路徑上的分支樹樹的路徑長度：從根到每一結(jié)點的路徑長度之和

64整理ppt2763415例⑴-⑵-⑸為結(jié)點1到5之間的路徑，其路徑長度為2，樹的路徑長度=l12+l13+

l14+l15+

l16+l17

=1+1+2+2+2+2=10完全二叉樹是路徑長度最短的二叉樹?？紤]帶權(quán)時：設(shè)樹中有m個葉結(jié)點，每個葉結(jié)點帶一個權(quán)值wｉ且根到葉結(jié)點i的路徑長度為Li(ｉ=1，2，．．m〕，那么樹的帶權(quán)路徑長度為樹中所有葉結(jié)點的權(quán)值與路徑長度的乘積的總和。Ｍ即：ＷＰＬ＝∑ＷｋＬｋＫ＝１65整理ppt例如，給定4個葉結(jié)點，設(shè)權(quán)值分別為1，3，5，7，據(jù)此可以構(gòu)造出形狀不同的4棵二叉樹，如圖6-19所示。它們的帶權(quán)路徑長度分別為：

(a)WPL=1×2+3×2+5×2+7×2=32(b)WPL=1×2+3×3+5×3+7×l=33(c)WPL=7×3+5×3+3×2+1×1=43(d)WPL=1×3+3×3+5×2+7×1=29

WPL最小的二叉樹是最優(yōu)二叉樹(Huffman樹)，圖6-19(d)所示。

圖6-19由4個結(jié)點構(gòu)成的不同的帶權(quán)二叉樹

第0層第1層第2層第3層66整理ppt1．二叉樹的路徑長度從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的路徑，路經(jīng)上的分支數(shù)目稱為路徑長度。樹的路徑長度是指從樹根到樹中每一結(jié)點的路徑長度之和。在結(jié)點數(shù)目相同的二叉樹中，完全二叉樹的路徑長度最短。2．二叉樹的帶權(quán)路徑長度(WeightedPathLengthofTree，簡記為WPL)結(jié)點的帶權(quán)路徑長度定義為結(jié)點到樹根之間的路徑長度與該結(jié)點上所帶權(quán)值的乘積。樹的帶權(quán)路徑長度(WeightedPathLengthofTree)是樹中所有葉結(jié)點的帶權(quán)路徑長度之和，通常記為：67整理ppt3．最優(yōu)二叉樹或哈夫曼樹哈夫曼樹〔或最優(yōu)二叉樹〕：在權(quán)為wl，w2，…，wn的n個葉子所構(gòu)成的所有二叉樹中，帶權(quán)路徑長度最小(即代價最小)的二叉樹。結(jié)論:①當(dāng)葉子上的權(quán)值均相同時，完全二叉樹一定是最優(yōu)二叉樹。否那么完全二叉樹不一定是最優(yōu)二叉樹。②在最優(yōu)二叉樹中，權(quán)值越大的葉子離根越近。③最優(yōu)二叉樹的形態(tài)不唯一，但WPL最小。68整理ppt3．最優(yōu)二叉樹或哈夫曼樹哈夫曼樹〔或最優(yōu)二叉樹〕：在權(quán)為wl，w2，…，wn的n個葉子所構(gòu)成的所有二叉樹中，帶權(quán)路徑長度最小(即代價最小)的二叉樹。結(jié)論:①當(dāng)葉子上的權(quán)值均相同時，完全二叉樹一定是最優(yōu)二叉樹。否那么完全二叉樹不一定是最優(yōu)二叉樹。②在最優(yōu)二叉樹中，權(quán)值越大的葉子離根越近。③最優(yōu)二叉樹的形態(tài)不唯一，但WPL最小。69整理ppt6.5.3構(gòu)造最優(yōu)二叉樹：1．哈夫曼算法哈夫曼算法的根本思想是：(1)以權(quán)值分別為W1,W2．．．Ｗｎ的ｎ各結(jié)點，構(gòu)成n棵二叉樹T1,T2,．．．Tn并組成森林F={T1,T2,．．．Tn},其中每棵二叉樹Ti僅有一個權(quán)值為Wi的根結(jié)點；(2)在F中選取兩棵根結(jié)點權(quán)值最小的樹作為左右子樹構(gòu)造一棵新二叉樹，并且置新二叉樹根結(jié)點權(quán)值為左右子樹上根結(jié)點的權(quán)值之和〔根結(jié)點的權(quán)值=左右孩子權(quán)值之和，葉結(jié)點的權(quán)值=Wi〕(3)從F中刪除這兩棵二叉樹，同時將新二叉樹參加到F中;(4)重復(fù)(2)．(３)直到F中只含一棵二叉樹為止，這棵二叉樹就是Huffman樹。70整理ppt

例如，給定權(quán)值集合{5，15，40，30，10}構(gòu)造哈夫曼樹的過程如圖6-21所示，其中最優(yōu)的帶權(quán)路徑長度為：WTL＝(5＋10)×4＋15×3＋30×2＋40＝205。由圖6-21可以看出，哈夫曼樹的結(jié)點的度數(shù)為0或2，沒有度為1的結(jié)點。

圖6-21哈夫曼樹構(gòu)造過程

71整理ppt2．哈夫曼樹的存儲結(jié)構(gòu)及哈夫曼算法的實現(xiàn)(1)哈夫曼樹的存儲結(jié)構(gòu)

用大小為2n-1的一維數(shù)組來存儲哈夫曼樹中的結(jié)點，其存儲結(jié)構(gòu)為：#definen100//葉結(jié)點數(shù)目#definem2*n-1//樹中結(jié)點總數(shù)typedefstruct{floatweight;//權(quán)值，設(shè)權(quán)值均大于零intlchild,rchild,parent;//左右孩子及雙親指針}HTNode;

typedefHTNodeHuffmanTree[m];//哈夫曼樹是一維數(shù)組因為C語言數(shù)組的下界為0，用-1表示空指針。樹中結(jié)點的lchild、rchild和parent不等于-1時，分別表示該結(jié)點的左、右孩子和雙親結(jié)點在數(shù)組中的下標(biāo)。設(shè)置parent域有兩個作用：一是使查找某結(jié)點的雙親變得簡單；二是可通過判定parent的值是否為-1來區(qū)分根與非根結(jié)點。

72整理ppt(2)哈夫曼算法的簡要描述在上述存儲結(jié)構(gòu)上實現(xiàn)的哈夫曼算法可大致描述為(設(shè)T的類型為HuffmanTree)：①初始化將T[0…m-1]中2n-1個結(jié)點里的三個指針均置為空(即置為-1)，權(quán)值置為0。②輸入讀入n個葉子的權(quán)值存于數(shù)組的前n個分量(即T[0…n-1])中。它們是初始森林中n個孤立的根結(jié)點上的權(quán)值。③合并對森林中的樹共進(jìn)行n-1次合并，所產(chǎn)生的新結(jié)點依次放入數(shù)組T的第i個分量中(n≤i≤m-1)。每次合并分兩步：73整理ppt1)在當(dāng)前森林T[0…i-1]的所有結(jié)點中，選取權(quán)值最小和次小的兩個根結(jié)點T[p1]和T[p2]作為合并對象，這里0≤p1，p2≤i-1。2)將根為T[p1]和T[p2]的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結(jié)點T[i]。

具體操作：將T[p1]和T[p2]的parent置為i；將T[i]的lchild和rchild分別置為p1和p2；新結(jié)點T[i]的權(quán)值置為T[p1]和T[p2]的權(quán)值之和。合并后T[pl]和T[p2]在當(dāng)前森林中已不再是根，因為它們的雙親指針均已指向了T[i]，所以下一次合并時不會被選中為合并對象。

74整理ppt(3)哈夫曼樹的構(gòu)造〔數(shù)組法〕voidCreateHuffmanTree(HuffmanTreeT){inti,p1,p2;//構(gòu)造哈夫曼樹，T[m-1]為其根結(jié)點InitHuffmanTree(T);//T初始化InputWeight(T);//輸入葉子權(quán)值至T[0．．n-1]的weight域for(i=n;i<m;i++){SelectMin(T,i-1,&p1,&p2);//共進(jìn)行n-1次合并，新結(jié)點依次存于T[i]中//在T[0…i-1]中選擇兩個權(quán)最小的根結(jié)點，其序號分別為p1和p2T[p1].parent=T[p2].parent=i;T[i].1child=p1;//最小權(quán)的根結(jié)點是新結(jié)點的左孩子T[i].rchild=p2;//次小權(quán)的根結(jié)點是新結(jié)點的右孩子T[i].weight=T[p1].weight+T[p2].weight;}}75整理ppt【例6-7】用鏈表構(gòu)造哈夫曼樹【解】哈夫曼樹的鏈表結(jié)構(gòu)算法描述如下：#include“stdio.h〞#include“stdlib.h〞#include“alloc.h〞#definem100structptree//定義二叉樹結(jié)點類型{intw;//定義結(jié)點權(quán)值structptree*lchild;//定義左子結(jié)點指針structptree*rchild;//定義右子結(jié)點指針};structpforest//定義鏈表結(jié)點類型{structpforest*link;structptree*root;};intWPL=0;//初始化WTL為0structptree*hafm();voidtravel();structpforest*inforest();76整理pptmain(){structptree*head;intn,i,w[m];printf("pleaseinputthesumofnode\n");//提示輸入結(jié)點數(shù)scanf("%d",&n);//輸入結(jié)點數(shù)printf("pleaseinputweightofeverynode\n");//提示輸入每個結(jié)點的權(quán)值for(i=1;i<=n;i++)scanf("%d",&w[i]);//輸入每個結(jié)點權(quán)值head=hafm(w,n);travel(head,0);printf("ThelengthofthebestpathisWPL=%d",WPL);//輸出最正確路徑權(quán)值之和}77整理pptvoidtravel(structptree*head,intn)//為驗證harfm算法的正確性進(jìn)行的遍歷{structptree*p;p=head;if(p!=NULL){if((p->lchild)==NULL&&(p->rchild)==NULL)//如果是葉子結(jié)點{printf("%d",p->w);printf("thehopsofthenodeis:%d\n",n);WPL=WPL+n*(p->w);//計算權(quán)值}travel(p->lchild,n+1);travel(p->rchild,n+1);}}

78整理pptstructptree*hafm(intn,intw[m]){structpforest*p1,*p2,*f;structptree*ti,*t,*t1,*t2;inti;f=(structpfores*)malloc(sizeof(structpforest));f->link=NULL;for(i=1;i<=n;i++)//產(chǎn)生n棵只有根結(jié)點的二叉樹{ti=(structptree*)malloc(sizeof(structptree));//開辟新的結(jié)點空間ti->w=w[i];//給結(jié)點賦權(quán)值ti->lchild=NULL;ti->rchild=NULL;f=inforest(f,ti);}while(((f->link)->link)!=NULL)//至少有二棵二叉樹{p1=f->link;p2=p1->link;f->link=p2->link;//取出前兩棵樹

79整理pptf->link=p2->link;//取出前兩棵樹t1=p1->root;t2=p2->root;free(p1);//釋放p1free(p2);//釋放p2t=(structptree*)malloc(sizeof(structptree));//開辟新的結(jié)點空間t->w=t1->w+t2->w;//權(quán)相加t->lchild=t1;t->rchild=t2;//產(chǎn)生新二叉樹f=inforest(f,t);}p1=f->link;t=p1->root;free(f);return(t);//返回t}80整理pptstructpforest*inforest(structpforest*f,sturctptree*t){structpforest*p,*q,*r;structptree*ti;r=(structpforest*)malloc(sizeof(structpforest));//開辟新的結(jié)點空間r->root=t;q=f;p=f->link;while(p!=NULL)//尋找插入位置{ti=p->root;if(t->w>ti->w)//如果t的權(quán)值大于ti的權(quán)值{q=p;p=p->link;//p向后尋找}elsep=NULL;//強迫退出循環(huán)}r->link=q->link;q->link=r;