數(shù)據(jù)結(jié)構(gòu)與算法：第六章 學(xué)習(xí)指導(dǎo)材料

第六章二叉樹第一部分知識(shí)點(diǎn)及例題精選所謂非線性結(jié)構(gòu)是指，在該結(jié)構(gòu)中至少存在一個(gè)數(shù)據(jù)元素，有兩個(gè)或兩個(gè)以上的直接前驅(qū)（或直接后繼）元素。樹型結(jié)構(gòu)和圖型就是其中十分重要的非線性結(jié)構(gòu)，可以用來描述客觀世界中廣泛存在的層次結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)的關(guān)系，如前面提到的族譜、城市交通等。在本書的第六、七、八章將重點(diǎn)討論這兩類非線性結(jié)構(gòu)的有關(guān)概念、存儲(chǔ)結(jié)構(gòu)、在各種存儲(chǔ)結(jié)構(gòu)上所實(shí)施的一些運(yùn)算以及有關(guān)的應(yīng)用實(shí)例。本章對(duì)樹型結(jié)構(gòu)中最簡(jiǎn)單、應(yīng)用十分廣泛的二叉樹結(jié)構(gòu)進(jìn)行討論。6.1定義與性質(zhì)6.11．二叉樹二叉樹（BinaryTree）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根(root)的元素及兩個(gè)不相交的、被分別稱為左子樹和右子樹的二叉樹組成。當(dāng)集合為空時(shí)，稱該二叉樹為空二叉樹。在二叉樹中，一個(gè)元素也稱作一個(gè)結(jié)點(diǎn)。二叉樹是有序的，即若將其左、右子樹顛倒，就成為另一棵不同的二叉樹。即使樹中結(jié)點(diǎn)只有一棵子樹，也要區(qū)分它是左子樹還是右子樹。因此二叉樹具有五種基本形態(tài)，如圖6.1所示。Ф左子樹左子樹左子樹左子樹Ф左子樹左子樹左子樹左子樹(a)(b)(c)(d)(e)圖6.1二叉樹的五種基本形態(tài)2．二叉樹的相關(guān)概念（1）結(jié)點(diǎn)的度。結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。（2）葉結(jié)點(diǎn)。度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)。（3）分枝結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。一棵樹的結(jié)點(diǎn)除葉結(jié)點(diǎn)外，其余的都是分支結(jié)點(diǎn)。（4）左孩子、右孩子、雙親。樹中一個(gè)結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子。這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親。具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。（5）路徑、路徑長(zhǎng)度。如果一棵樹的一串結(jié)點(diǎn)n1,n2,…,nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的父結(jié)點(diǎn)（1≤i<k）,就把n1,n2,…,nk稱為一條由n1至nk的路徑。這條路徑的長(zhǎng)度是k-1。（6）祖先、子孫。在樹中，如果有一條路徑從結(jié)點(diǎn)M到結(jié)點(diǎn)N，那么M就稱為N的祖先，而N稱為M的子孫。（7）結(jié)點(diǎn)的層數(shù)。規(guī)定樹的根結(jié)點(diǎn)的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)等于它的雙親結(jié)點(diǎn)的層數(shù)加1。（8）樹的深度。樹中所有結(jié)點(diǎn)的最大層數(shù)稱為樹的深度。（9）樹的度。樹中各結(jié)點(diǎn)度的最大值稱為該樹的度。（10）滿二叉樹。在一棵二叉樹中，如果所有分支結(jié)點(diǎn)都存在左子樹和右子樹，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的一棵二叉樹稱作滿二叉樹。如圖6.2所示，（a）圖就是一棵滿二叉樹，（b）圖則不是滿二叉樹，因?yàn)?，雖然其所有結(jié)點(diǎn)要么是含有左右子樹的分支結(jié)點(diǎn)，要么是葉子結(jié)點(diǎn)，但由于其葉子未在同一層上，故不是滿二叉樹。11AA11AA2B323CBC2B323CBC45677654GFEDDEG45677654GFEDDEGFHIKJHIONMLHIKJHIONML89141513121110988914151312111098(a)一棵滿二叉樹(b)一棵非滿二叉樹圖6.2滿二叉樹和非滿二叉樹示意圖（11）完全二叉樹。一棵深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹中編號(hào)為i的結(jié)點(diǎn)在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。完全二叉樹的特點(diǎn)是：葉子結(jié)點(diǎn)只能出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹的左部。顯然，一棵滿二叉樹必定是一棵完全二叉樹，而完全二叉樹未必是滿二叉樹。如圖6.3所示（a）為一棵完全二叉樹，（b）和圖6.2（b）都不是完全二叉樹。11AA11AA3132CBCB3132CBCB6547654EFDFGED6547654EFDFGED7GJIH7GJIH10891089(a)一棵完全二叉樹(b)一棵非完全二叉樹圖6.3完全二叉樹和非完全二叉樹示意圖6.1.2二叉樹的主要性質(zhì)性質(zhì)1一棵非空二叉樹的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。該性質(zhì)可由數(shù)學(xué)歸納法證明。證明略。性質(zhì)2一棵深度為k的二叉樹中，最多具有2k－1個(gè)結(jié)點(diǎn)。k∑i=1k∑i=1證明設(shè)第i層的結(jié)點(diǎn)數(shù)為xi（1≤i≤k），深度為k的二叉樹的結(jié)點(diǎn)數(shù)為M，xk∑i=1k∑i=1M＝xi≤2i-1＝2k-1性質(zhì)3對(duì)于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則有:n0＝n2＋1。證明設(shè)n為二叉樹的結(jié)點(diǎn)總數(shù)，n1為二叉樹中度為1的結(jié)點(diǎn)數(shù)，則有：n＝n0＋n1＋n2（6-1）在二叉樹中，除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)都有唯一的一個(gè)進(jìn)入分支。設(shè)B為二叉樹中的分支數(shù)，那么有：B＝n－1（6-2）這些分支是由度為1和度為2的結(jié)點(diǎn)發(fā)出的，一個(gè)度為1的結(jié)點(diǎn)發(fā)出一個(gè)分支，一個(gè)度為2的結(jié)點(diǎn)發(fā)出兩個(gè)分支，所以有：B＝n1＋2n2（6-3）綜合（6-1）、（6-2）、（6-3）式可以得到：n0＝n2＋1性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為[log2n]+1。證明根據(jù)完全二叉樹的定義和性質(zhì)2可知，當(dāng)一棵完全二叉樹的深度為k、結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，有2k－1－1<n≤2k-1即2k－1≤n<2k對(duì)不等式取對(duì)數(shù)，有k－1≤log2n<k由于k是整數(shù)，所以有k＝[log2n]+1。性質(zhì)5對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號(hào)，則對(duì)于任意的序號(hào)為i的結(jié)點(diǎn)，有：（1）如果i>1，則序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為i/2(“/”表示整除)；如果i＝1，則序號(hào)為i的結(jié)點(diǎn)是根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。（2）如果2i≤n，則序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i；如果2i>n，則序號(hào)為i的結(jié)點(diǎn)無左孩子。（3）如果2i＋1≤n，則序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)為2i＋1；如果2i＋1>n，則序號(hào)為i的結(jié)點(diǎn)無右孩子。此外，若對(duì)二叉樹的根結(jié)點(diǎn)從0開始編號(hào)，則相應(yīng)的i號(hào)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為（i－1）/2，左孩子的編號(hào)為2i＋1，右孩子的編號(hào)為2i＋2。此性質(zhì)可采用數(shù)學(xué)歸納法證明。證明略。6.2基本操作與存儲(chǔ)實(shí)現(xiàn)6.2.1二叉樹的存儲(chǔ)1．順序存儲(chǔ)結(jié)構(gòu)所謂二叉樹的順序存儲(chǔ)，就是用一組連續(xù)的存儲(chǔ)單元存放二叉樹中的結(jié)點(diǎn)。一般是按照二叉樹結(jié)點(diǎn)從上至下、從左到右的順序存儲(chǔ)。這樣結(jié)點(diǎn)在存儲(chǔ)位置上的前驅(qū)后繼關(guān)系并不一定就是它們?cè)谶壿嬌系泥徑雨P(guān)系，然而只有通過一些方法確定某結(jié)點(diǎn)在邏輯上的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)，這種存儲(chǔ)才有意義。因此，依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲(chǔ)比較合適，樹中結(jié)點(diǎn)的序號(hào)可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省存儲(chǔ)空間，又可以利用數(shù)組元素的下標(biāo)值確定結(jié)點(diǎn)在二叉樹中的位置，以及結(jié)點(diǎn)之間的關(guān)系。圖6.4給出的圖6.3(a)所示的完全二叉樹的順序存儲(chǔ)示意。對(duì)于一般的二叉樹，如果仍按從上至下和從左到右的順序?qū)渲械慕Y(jié)點(diǎn)順序存儲(chǔ)在一維數(shù)組中，則數(shù)組元素下標(biāo)之間的關(guān)系不能夠反映二叉樹中結(jié)點(diǎn)之間的邏輯關(guān)系，只有增添一些并不存在的空結(jié)點(diǎn)，使之成為一棵完全二叉樹的形式，然后再用一維數(shù)組順序存儲(chǔ)。如圖6.5給出了一棵一般二叉樹改造后的完全二叉樹形態(tài)和其順序存儲(chǔ)狀態(tài)示意圖。顯然，這種存儲(chǔ)對(duì)于需增加許多空結(jié)點(diǎn)才能將一棵二叉樹改造成為一棵完全二叉樹的存儲(chǔ)時(shí)，會(huì)造成空間的大量浪費(fèi)，不宜用順序存儲(chǔ)結(jié)構(gòu)。最壞的情況是右單支樹，如圖6.6所示，一棵深度為k的右單支樹，只有k個(gè)結(jié)點(diǎn)，卻需分配2k－1個(gè)存儲(chǔ)單元。ABCDEFGHIJ數(shù)組下標(biāo)0123456789圖6.4完全二叉樹的順序存儲(chǔ)示意圖AAAACBCBCBCBEDDEEDDEGFFGGFFG(a)一棵二叉樹(b)改造后的完全二叉樹ABC∧DE∧∧∧F∧∧G(c)改造后完全二叉樹順序存儲(chǔ)狀態(tài)圖6.5一般二叉樹及其順序存儲(chǔ)示意圖AAAABBBBCCCCDDDD(a)一棵右單支二叉樹(b)改造后的右單支樹對(duì)應(yīng)的完全二叉樹A∧B∧∧∧C∧∧∧∧∧∧∧D(c)單支樹改造后完全二叉樹的順序存儲(chǔ)狀態(tài)圖6.6右單支二叉樹及其順序存儲(chǔ)示意圖二叉樹的順序存儲(chǔ)表示可描述為：#defineMAXNODE/*二叉樹的最大結(jié)點(diǎn)數(shù)*/typedefelemtypeSqBiTree[MAXNODE]/*0號(hào)單元存放根結(jié)點(diǎn)*/SqBiTreebt;即將bt定義為含有MAXNODE個(gè)elemtype類型元素的一維數(shù)組。2．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所謂二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指，用鏈表來表示一棵二叉樹，即用鏈來指示著元素的邏輯關(guān)系。通常有下面兩種形式。（1）二叉鏈表存儲(chǔ)鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成，除了數(shù)據(jù)域外，還有兩個(gè)指針域，分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲(chǔ)地址。結(jié)點(diǎn)的存儲(chǔ)的結(jié)構(gòu)為：lchildrchilddatalchildrchilddata其中，data域存放某結(jié)點(diǎn)的數(shù)據(jù)信息；lchild與rchild分別存放指向左孩子和右孩子的指針，當(dāng)左孩子或右孩子不存在時(shí)，相應(yīng)指針域值為空（用符號(hào)∧或NULL表示）。圖6.7(a)給出了圖6.3(b)所示的一棵二叉樹的二叉鏈表示。二叉鏈表也可以帶頭結(jié)點(diǎn)的方式存放，如圖6.7(b)所示。頭指針bt頭結(jié)點(diǎn)指針btAAAAC∧BC∧BC∧BC∧B∧F∧∧E∧D∧∧F∧∧E∧D∧∧F∧∧E∧D∧∧F∧∧E∧D∧∧G∧∧G∧∧G∧∧G∧(a)帶頭指針的二叉鏈表(b)帶頭結(jié)點(diǎn)的二叉鏈表圖6.7圖6.3(b)所示二叉樹的二叉鏈表表示示意圖（2）三叉鏈表存儲(chǔ)每個(gè)結(jié)點(diǎn)由四個(gè)域組成，具體結(jié)構(gòu)為：parentrchildlchilddataparentrchildlchilddata其中，data、lchild以及rchild三個(gè)域的意義同二叉鏈表結(jié)構(gòu)；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。這種存儲(chǔ)結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)；但是，相對(duì)于二叉鏈表存儲(chǔ)結(jié)構(gòu)而言，它增加了空間開銷。圖6.8給出了圖6.3(b)所示的一棵二叉樹的三叉鏈表示。A∧A∧C∧BC∧B∧F∧∧∧E∧D∧∧F∧∧∧E∧D∧∧G∧∧G∧圖6.8圖6.3(b)所示二叉樹的三叉鏈表表示示意圖盡管在二叉鏈表中無法由結(jié)點(diǎn)直接找到其雙親，但由于二叉鏈表結(jié)構(gòu)靈活，操作方便，對(duì)于一般情況的二叉樹，甚至比順序存儲(chǔ)結(jié)構(gòu)還節(jié)省空間。因此，二叉鏈表是最常用的二叉樹存儲(chǔ)方式。本書后面所涉及到的二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不加特別說明的都是指二叉鏈表結(jié)構(gòu)。二叉樹的二叉鏈表存儲(chǔ)表示可描述為：typedefstructBiTNode{elemtypedata;structBiTNode*lchild;*rchild;/*左右孩子指針*/}BiTNode,*BiTree;即將BiTree定義為指向二叉鏈表結(jié)點(diǎn)結(jié)構(gòu)的指針類型。6.2.2二叉樹的基本操作及實(shí)現(xiàn)1．二叉樹的基本操作二叉樹的基本操作通常有以下幾種：Initiate（bt）建立一棵空二叉樹。（2）Create（x，lbt，rbt）生成一棵以x為根結(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉樹lbt和rbt為左子樹和右子樹的二叉樹。（3）InsertL（bt，x，parent）將數(shù)據(jù)域信息為x的結(jié)點(diǎn)插入到二叉樹bt中作為結(jié)點(diǎn)parent的左孩子結(jié)點(diǎn)。如果結(jié)點(diǎn)parent原來有左孩子結(jié)點(diǎn)，則將結(jié)點(diǎn)parent原來的左孩子結(jié)點(diǎn)作為結(jié)點(diǎn)x的左孩子結(jié)點(diǎn)。（4）InsertR（bt，x，parent）將數(shù)據(jù)域信息為x的結(jié)點(diǎn)插入到二叉樹bt中作為結(jié)點(diǎn)parent的右孩子結(jié)點(diǎn)。如果結(jié)點(diǎn)parent原來有右孩子結(jié)點(diǎn)，則將結(jié)點(diǎn)parent原來的右孩子結(jié)點(diǎn)作為結(jié)點(diǎn)x的右孩子結(jié)點(diǎn)。（5）DeleteL（bt，parent）在二叉樹bt中刪除結(jié)點(diǎn)parent的左子樹。（6）DeleteR（bt，parent）在二叉樹bt中刪除結(jié)點(diǎn)parent的右子樹。（7）Search（bt，x）在二叉樹bt中查找數(shù)據(jù)元素x。（8）Traverse（bt）按某種方式遍歷二叉樹bt的全部結(jié)點(diǎn)。2．算法的實(shí)現(xiàn)算法的實(shí)現(xiàn)依賴于具體的存儲(chǔ)結(jié)構(gòu)，當(dāng)二叉樹采用不同的存儲(chǔ)結(jié)構(gòu)時(shí)，上述各種操作的實(shí)現(xiàn)算法是不同的。下面討論基于二叉鏈表存儲(chǔ)結(jié)構(gòu)的上述操作的實(shí)現(xiàn)算法。（1）Initiate（bt）初始建立二叉樹bt，并使bt指向頭結(jié)點(diǎn)。在二叉樹根結(jié)點(diǎn)前建立頭結(jié)點(diǎn)，就如同在單鏈表前建立的頭結(jié)點(diǎn)，可以方便后邊的一些操作實(shí)現(xiàn)。intInitiate(BiTree*bt){/*初始化建立二叉樹*bt的頭結(jié)點(diǎn)*/if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)return0;*bt->lchild=NULL;*bt->rchild=NULL;return1;}算法6.1（2）Create（x，lbt，rbt）建立一棵以x為根結(jié)點(diǎn)的數(shù)據(jù)域信息，以二叉樹lbt和rbt為左右子樹的二叉樹。建立成功時(shí)返回所建二叉樹結(jié)點(diǎn)的指針；建立失敗時(shí)返回空指針。BiTreeCreate（elemtypex，BiTreelbt，BiTreerbt）{/*生成一棵以x為根結(jié)點(diǎn)的數(shù)據(jù)域值以lbt和rbt為左右子樹的二叉樹*/BiTreep;if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p->data=x;p->lchild=lbt;p->rchild=rbt;returnp;}算法6.2（3）InsertL（bt，x，parent）BiTreeInsertL（BiTreebt，elemtypex，BiTreeparent）{/*在二叉樹bt的結(jié)點(diǎn)parent的左子樹插入結(jié)點(diǎn)數(shù)據(jù)元素x*/BiTreep;if(parent==NULL){printf(“\n插入出錯(cuò)”)；returnNULL;}if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)returnNULL;p->data=x;p->lchild=NULL;p->rchild=NULL;if(parent->lchild==NULL)parent->lchild=p;else{p->lchild=parent->lchild;parent->lchild=p;}returnbt;}算法6.3（4）InsertR（bt，x，parent）功能類同于（3），算法略。（5）DeleteL（bt，parent）在二叉樹bt中刪除結(jié)點(diǎn)parent的左子樹。當(dāng)parent或parent的左孩子結(jié)點(diǎn)為空時(shí)刪除失敗。刪除成功時(shí)返回根結(jié)點(diǎn)指針；刪除失敗時(shí)返回空指針。BiTreeDeleteL（BiTreebt，BiTreeparent）{/*在二叉樹bt中刪除結(jié)點(diǎn)parent的左子樹*/BiTreep;if(parent==NULL||parent->lchild==NULL){printf(“\n刪除出錯(cuò)”)；returnNULL’}p=parent->lchild;parent->lchild=NULL;free(p);/*當(dāng)p為非葉子結(jié)點(diǎn)時(shí)，這樣刪除僅釋放了所刪子樹根結(jié)點(diǎn)的空間，*//*若要?jiǎng)h除子樹分支中的結(jié)點(diǎn)，需用后面介紹的遍歷操作來實(shí)現(xiàn)。*/returnbr;}算法6.4（6）DeleteR（bt，parent）功能類同于（5），只是刪除結(jié)點(diǎn)parent的右子樹。算法略。操作Search（bt，x）實(shí)際是遍歷操作Traverse（bt）的特例，關(guān)于二叉樹的遍歷操作的實(shí)現(xiàn)，將在下一節(jié)中重點(diǎn)介紹。6.3二叉樹的遍歷6.3.1二叉樹的遍歷方法及遞歸實(shí)現(xiàn)二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次。遍歷是二叉樹中經(jīng)常要用到的一種操作。因?yàn)樵趯?shí)際應(yīng)用問題中，常常需要按一定順序?qū)Χ鏄渲械拿總€(gè)結(jié)點(diǎn)逐個(gè)進(jìn)行訪問，查找具有某一特點(diǎn)的結(jié)點(diǎn)，然后對(duì)這些滿足條件的結(jié)點(diǎn)進(jìn)行處理。通過一次完整的遍歷，可使二叉樹中結(jié)點(diǎn)信息由非線性排列變?yōu)槟撤N意義上的線性序列。也就是說，遍歷操作使非線性結(jié)構(gòu)線性化。由二叉樹的定義可知，一棵由根結(jié)點(diǎn)、根結(jié)點(diǎn)的左子樹和根結(jié)點(diǎn)的右子樹三部分組成。因此，只要依次遍歷這三部分，就可以遍歷整個(gè)二叉樹。若以D、L、R分別表示訪問根結(jié)點(diǎn)、遍歷根結(jié)點(diǎn)的左子樹、遍歷根結(jié)點(diǎn)的右子樹，則二叉樹的遍歷方式有六種：DLR、LDR、LRD、DRL、RDL和RLD。如果限定先左后右，則只有前三種方式，即DLR（稱為先序遍歷）、LDR（稱為中序遍歷）和LRD（稱為后序遍歷）。1．先序遍歷（DLR）先序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則，訪問根結(jié)點(diǎn)；先序遍歷根結(jié)點(diǎn)的左子樹；先序遍歷根結(jié)點(diǎn)的右子樹。先序遍歷二叉樹的遞歸算法如下：voidPreOrder（BiTreebt）{/*先序遍歷二叉樹bt*/if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/Visite（bt->data）;/*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/PreOrder（bt->lchild）;/*先序遞歸遍歷bt的左子樹*/PreOrder（bt->rchild）;/*先序遞歸遍歷bt的右子樹*/}算法6.5對(duì)于圖6圖6.3(b)所示的二叉樹，按先序遍歷所得到的結(jié)點(diǎn)序列為：ABDGCEF2．中序遍歷（LDR）中序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則，（1）中序遍歷根結(jié)點(diǎn)的左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷根結(jié)點(diǎn)的右子樹。中序遍歷二叉樹的遞歸算法如下：voidInOrder（BiTreebt）{/*中序遍歷二叉樹bt*/if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/InOrder（bt->lchild）;/*中序遞歸遍歷bt的左子樹*/Visite（bt->data）;/*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/InOrder（bt->rchild）;/*中序遞歸遍歷bt的右子樹*/}算法6.6對(duì)于圖6.3(b)所示的二叉樹，按中序遍歷所得到的結(jié)點(diǎn)序列為：DGBAECF3．后序遍歷（LRD）后序遍歷的遞歸過程為：若二叉樹為空，遍歷結(jié)束。否則，（1）后序遍歷根結(jié)點(diǎn)的左子樹；（2）后序遍歷根結(jié)點(diǎn)的右子樹。（3）訪問根結(jié)點(diǎn)；后序遍歷二叉樹的遞歸算法如下：voidPostOrder（BiTreebt）{/*后序遍歷二叉樹bt*/if(bt==NULL)return;/*遞歸調(diào)用的結(jié)束條件*/PostOrder（bt->lchild）;/*后序遞歸遍歷bt的左子樹*/PostOrder（bt->rchild）;/*后序遞歸遍歷bt的右子樹*/Visite（bt->data）;/*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/}算法6.7對(duì)于圖圖6.3(b)所示的二叉樹，按先序遍歷所得到的結(jié)點(diǎn)序列為：GDBEFCA4．層次遍歷所謂二叉樹的層次遍歷，是指從二叉樹的第一層（根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問。對(duì)于圖6.3(b)所示的二叉樹，按層次遍歷所得到的結(jié)果序列為：ABCDEFG下面討論層次遍歷的算法。由層次遍歷的定義可以推知，在進(jìn)行層次遍歷時(shí)，對(duì)一層結(jié)點(diǎn)訪問完后，再按照它們的訪問次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左孩子和右孩子順序訪問，這樣一層一層進(jìn)行，先遇到的結(jié)點(diǎn)先訪問，這與隊(duì)列的操作原則比較吻合。因此，在進(jìn)行層次遍歷時(shí)，可設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，遍歷從二叉樹的根結(jié)點(diǎn)開始，首先將根結(jié)點(diǎn)指針入隊(duì)列，然后從對(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行下面兩個(gè)操作：訪問該元素所指結(jié)點(diǎn)；若該元素所指結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空，則將該元素所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。此過程不斷進(jìn)行，當(dāng)隊(duì)列為空時(shí)，二叉樹的層次遍歷結(jié)束。在下面的層次遍歷算法中，二叉樹以二叉鏈表存放，一維數(shù)組Queue[MAXNODE]用以實(shí)現(xiàn)隊(duì)列，變量front和rear分別表示當(dāng)前對(duì)首元素和隊(duì)尾元素在數(shù)組中的位置。voidLevelOrder（BiTreebt）/*層次遍歷二叉樹bt*/{BiTreeQueue[MAXNODE];intfront,rear;if(bt==NULL)return;front=-1;rear=0;queue[rear]=bt;while(front!=rear){front++;Visite(queue[front]->data);/*訪問隊(duì)首結(jié)點(diǎn)的數(shù)據(jù)域*/if(queue[front]->lchild!=NULL)/*將隊(duì)首結(jié)點(diǎn)的左孩子結(jié)點(diǎn)入隊(duì)列*/{rear++;queue[rear]=queue[front]->lchild;}if(queue[front]->rchild!=NULL)/*將隊(duì)首結(jié)點(diǎn)的右孩子結(jié)點(diǎn)入隊(duì)列*/{rear++;queue[rear]=queue[front]->rchild;}}}算法6.86.3.2二叉樹遍歷的非遞歸實(shí)現(xiàn)前面給出的二叉樹先序、中序和后序三種遍歷算法都是遞歸算法。當(dāng)給出二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以后，用具有遞歸功能的程序設(shè)計(jì)語言很方便就能實(shí)現(xiàn)上述算法。然而，并非所有程序設(shè)計(jì)語言都允許遞歸；另一方面，遞歸程序雖然簡(jiǎn)潔，但可讀性一般不好，執(zhí)行效率也不高。因此，就存在如何把一個(gè)遞歸算法轉(zhuǎn)化為非遞歸算法的問題。解決這個(gè)問題的方法可以通過對(duì)三種遍歷方法的實(shí)質(zhì)過程的分析得到。如圖6.3(b)所示的二叉樹，對(duì)其進(jìn)行先序、中序和后序遍歷都是從根結(jié)點(diǎn)A開始的，且在遍歷過程中經(jīng)過結(jié)點(diǎn)的路線是一樣的，只是訪問的時(shí)機(jī)不同而已。圖6.9中所示的從根結(jié)點(diǎn)左外側(cè)開始，由根結(jié)點(diǎn)右外側(cè)結(jié)束的曲線，為遍歷圖6.3(b)的路線。沿著該路線按△標(biāo)記的結(jié)點(diǎn)讀得的序列為先序序列，按*標(biāo)記讀得的序列為中序序列，按⊕標(biāo)記讀得的序列為后序序列。然而，這一路線正是從根結(jié)點(diǎn)開始沿左子樹深入下去，當(dāng)深入到最左端，無法再深入下去時(shí)，則返回，再逐一進(jìn)入剛才深入時(shí)遇到結(jié)點(diǎn)的右子樹，再進(jìn)行如此的深入和返回，直到最后從根結(jié)點(diǎn)的右子樹返回到根結(jié)點(diǎn)為止。先序遍歷是在深入時(shí)遇到結(jié)點(diǎn)就訪問，中序遍歷是在從左子樹返回時(shí)遇到結(jié)點(diǎn)訪問，后序遍歷是在從右子樹返回時(shí)遇到結(jié)點(diǎn)訪問。⊕△A⊕△A*△*△⊕△CB⊕△CB⊕**△⊕**△⊕⊕△△DFE⊕⊕△△DFE⊕***⊕***⊕G⊕G*△*△圖6.9遍歷圖6.3(b)的路線示意圖在這一過程中，返回結(jié)點(diǎn)的順序與深入結(jié)點(diǎn)的順序相反，即后深入先返回，正好符合棧結(jié)構(gòu)后進(jìn)先出的特點(diǎn)。因此，可以用棧來幫助實(shí)現(xiàn)這一遍歷路線。其過程如下。在沿左子樹深入時(shí)，深入一個(gè)結(jié)點(diǎn)入棧一個(gè)結(jié)點(diǎn)，若為先序遍歷，則在入棧之前訪問之；當(dāng)沿左分支深入不下去時(shí)，則返回，即從堆棧中彈出前面壓入的結(jié)點(diǎn)，若為中序遍歷，則此時(shí)訪問該結(jié)點(diǎn)，然后從該結(jié)點(diǎn)的右子樹繼續(xù)深入；若為后序遍歷，則將此結(jié)點(diǎn)再次入棧，然后從該結(jié)點(diǎn)的右子樹繼續(xù)深入，與前面類同，仍為深入一個(gè)結(jié)點(diǎn)入棧一個(gè)結(jié)點(diǎn)，深入不下去再返回，直到第二次從棧里彈出該結(jié)點(diǎn)，才訪問之。（1）先序遍歷的非遞歸實(shí)現(xiàn)在下面算法中，二叉樹以二叉鏈表存放，一維數(shù)組stack[MAXNODE]用以實(shí)現(xiàn)棧，變量top用來表示當(dāng)前棧頂?shù)奈恢谩oidNRPreOrder（BiTreebt）{/*非遞歸先序遍歷二叉樹*/BiTreestack[MAXNODE],p;inttop;if(bt==NULL)return;top=0;p=bt;while(!(p==NULL&&top==0)){while(p!=NULL){Visite(p->data);/*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/if(top<MAXNODE-1)/*將當(dāng)前指針p壓棧*/{stack[top]=p;top++;}else{printf(“棧溢出”)；return；}p=p->lchild；/*指針指向p的左孩子*/}if(top<=0)return;/*棧空時(shí)結(jié)束*/else{top--;p=stack[top];/*從棧中彈出棧頂元素*/p=p->rchild;/*指針指向p的右孩子結(jié)點(diǎn)*/}}}算法6.9對(duì)于圖6.3(b)所示的二叉樹，用該算法進(jìn)行遍歷過程中，棧stack和當(dāng)前指針p的變化情況以及樹中各結(jié)點(diǎn)的訪問次序如表6.1所示。（2）中序遍歷的非遞歸實(shí)現(xiàn)中序遍歷的非遞歸算法的實(shí)現(xiàn)，只需將先序遍歷的非遞歸算法中的Visite(p->data)移到p=stack[top]和p=p->rchild之間即可。（3）后序遍歷的非遞歸實(shí)現(xiàn)由前面的討論可知，后序遍歷與先序遍歷和中序遍歷不同，在后序遍歷過程中，結(jié)點(diǎn)在第一次出棧后，還需再次入棧，也就是說，結(jié)點(diǎn)要入兩次棧，出兩次棧，而訪問結(jié)點(diǎn)是在第二次出棧時(shí)訪問。因此，為了區(qū)別同一個(gè)結(jié)點(diǎn)指針的兩次出棧，設(shè)置一標(biāo)志flag，令：{1{1第一次出棧，結(jié)點(diǎn)不能訪問2第二次出棧，結(jié)點(diǎn)可以訪問flag＝當(dāng)結(jié)點(diǎn)指針進(jìn)、出棧時(shí)，其標(biāo)志flag也同時(shí)進(jìn)、出棧。因此，可將棧中元素的數(shù)據(jù)類型定義為指針和標(biāo)志flag合并的結(jié)構(gòu)體類型。定義如下：typedefstruct{BiTreelink;intflag;}stacktype;后序遍歷二叉樹的非遞歸算法如下。在算法中，一維數(shù)組stack[MAXNODE]用于實(shí)現(xiàn)棧的結(jié)構(gòu)，指針變量p指向當(dāng)前要處理的結(jié)點(diǎn)，整型變量top用來表示當(dāng)前棧頂?shù)奈恢?，整型變量sign為結(jié)點(diǎn)p的標(biāo)志量。voidNRPostOrder(BiTreebt)/*非遞歸后序遍歷二叉樹bt*/{stacktypestack[MAXNODE];BiTreep;inttop,sign;if(bt==NULL)return;top=-1/*棧頂位置初始化*/p=bt;while(!(p==NULL&&top==-1)){if(p!=NULL)/*結(jié)點(diǎn)第一次進(jìn)棧*/{top++;stack[top].link=p;stack[top].flag=1;p=p->lchild;/*找該結(jié)點(diǎn)的左孩子*/}else{p=stack[top].link;sign=stack[top].flag;top--;if(sign==1)/*結(jié)點(diǎn)第二次進(jìn)棧*/{top++;stack[top].link=p;stack[top].flag=2;/*標(biāo)記第二次出棧*/p=p->rchild;}else{Visite(p->data);/*訪問該結(jié)點(diǎn)數(shù)據(jù)域值*/p=NULL;}}}}算法6.106.3.3由遍歷序列恢復(fù)二叉樹從前面討論的二叉樹的遍歷知道，任意一棵二叉樹結(jié)點(diǎn)的先序序列和中序序列都是唯一的。反過來，若已知結(jié)點(diǎn)的先序序列和中序序列，能否確定這棵二叉樹呢？這樣確定的二叉樹是否是唯一的呢？回答是肯定的。根據(jù)定義，二叉樹的先序遍歷是先訪問根結(jié)點(diǎn)，其次再按先序遍歷方式遍歷根結(jié)點(diǎn)的左子樹，最后按先序遍歷方式遍歷根結(jié)點(diǎn)的右子樹。這就是說，在先序序列中，第一個(gè)結(jié)點(diǎn)一定是二叉樹的根結(jié)點(diǎn)。另一方面，中序遍歷是先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后再遍歷右子樹。這樣，根結(jié)點(diǎn)在中序序列中必然將中序序列分割成兩個(gè)子序列，前一個(gè)子序列是根結(jié)點(diǎn)的左子樹的中序序列，而后一個(gè)子序列是根結(jié)點(diǎn)的右子樹的中序序列。根據(jù)這兩個(gè)子序列，在先序序列中找到對(duì)應(yīng)的左子序列和右子序列。在先序序列中，左子序列的第一個(gè)結(jié)點(diǎn)是左子樹的根結(jié)點(diǎn)，右子序列的第一個(gè)結(jié)點(diǎn)是右子樹的根結(jié)點(diǎn)。這樣，就確定了二叉樹的三個(gè)結(jié)點(diǎn)。同時(shí)，左子樹和右子樹的根結(jié)點(diǎn)又可以分別把左子序列和右子序列劃分成兩個(gè)子序列，如此遞歸下去，當(dāng)取盡先序序列中的結(jié)點(diǎn)時(shí)，便可以得到一棵二叉樹。同樣的道理，由二叉樹的后序序列和中序序列也可唯一地確定一棵二叉樹。因?yàn)?，依?jù)后序遍歷和中序遍歷的定義，后序序列的最后一個(gè)結(jié)點(diǎn)，就如同先序序列的第一個(gè)結(jié)點(diǎn)一樣，可將中序序列分成兩個(gè)子序列，分別為這個(gè)結(jié)點(diǎn)的左子樹的中序序列和右子樹的中序序列，再拿出后序序列的倒數(shù)第二個(gè)結(jié)點(diǎn)，并繼續(xù)分割中序序列，如此遞歸下去，當(dāng)?shù)怪∪”M后序序列中的結(jié)點(diǎn)時(shí)，便可以得到一棵二叉樹。下面通過一個(gè)例子，來給出右二叉樹的先序序列和中序序列構(gòu)造唯一的一棵二叉樹的實(shí)現(xiàn)算法。已知一棵二叉樹的先序序列與中序序列分別為：ABCDEFGHIBCAEDGHFI試恢復(fù)該二叉樹。首先，由先序序列可知，結(jié)點(diǎn)A是二叉樹的根結(jié)點(diǎn)。其次，根據(jù)中序序列，在A之前的所有結(jié)點(diǎn)都是根結(jié)點(diǎn)左子樹的結(jié)點(diǎn)，在A之后的所有結(jié)點(diǎn)都是根結(jié)點(diǎn)右子樹的結(jié)點(diǎn)，由此得到圖6.10(a)所示的狀態(tài)。然后，再對(duì)左子樹進(jìn)行分解，得知B是左子樹的根結(jié)點(diǎn)，又從中序序列知道，B的左子樹為空，B的右子樹只有一個(gè)結(jié)點(diǎn)C。接著對(duì)A的右子樹進(jìn)行分解，得知A的右子樹的根結(jié)點(diǎn)為D；而結(jié)點(diǎn)D把其余結(jié)點(diǎn)分成兩部分，即左子樹為E，右子樹為F、G、H、I，如圖6.10(b)所示。接下去的工作就是按上述原則對(duì)D的右子樹繼續(xù)分解下去，最后得到如圖6.10(c)的整棵二叉樹。AAAAAADBDBDBDBFGIHFDEFGHIBCCECEFGIHFDEFGHIBCCECEIGIGHH(a)(b)(c)圖6.10一棵二叉樹的恢復(fù)過程示意上述過程是一個(gè)遞歸過程，其遞歸算法的思想是：先根據(jù)先序序列的第一個(gè)元素建立根結(jié)點(diǎn)；然后在中序序列中找到該元素，確定根結(jié)點(diǎn)的左、右子樹的中序序列；再在先序序列中確定左、右子樹的先序序列；最后由左子樹的先序序列與中序序列建立左子樹，由右子樹的先序序列與中序序列建立右子樹。下面給出用C語言描述的該算法。假設(shè)二叉樹的先序序列和中序序列分別存放在一維數(shù)組preod[]與inod[]中，并假設(shè)二叉樹各結(jié)點(diǎn)的數(shù)據(jù)值均不相同。voidReBiTree（charpreod[],charinod[],intn,BiTreeroot）/*n為二叉樹的結(jié)點(diǎn)個(gè)數(shù)，root為二叉樹根結(jié)點(diǎn)的存儲(chǔ)地址*/{if(n≤0)root=NULL;elsePreInOd(preod,inod,1,n,1,n,&root);}算法6.11voidPreInOd（charpreod[],charinod[],inti,j,k,h,BiTree*t）{*t=(BiTNode*)malloc(sizeof(BiTNode));*t->data=preod[i];m=k;while(inod[m]!=preod[i])m++;if(m==k)*t->lchild=NULLelsePreInOd(preod,inod,i+1,i+m-k,k,m-1,&t->lchild);if(m==h)*t->rchild=NULLelsePreInOd(preod,inod,i+m-k+1,j,m+1,h,&t->rchild);}算法6.12需要說明的是，數(shù)組preod和inod的元素類型可根據(jù)實(shí)際需要來設(shè)定，這里設(shè)為字符型。另外，如果只知道二叉樹的先序序列和后序序列，則不能唯一地確定一棵二叉樹。6.3.4不用棧的二叉樹遍歷的非遞歸方法前面介紹的二叉樹的遍歷算法可分為兩類，一類是依據(jù)二叉樹結(jié)構(gòu)的遞歸性，采用遞歸調(diào)用的方式來實(shí)現(xiàn)；另一類則是通過堆?；蜿?duì)列來輔助實(shí)現(xiàn)。采用這兩類方法對(duì)二叉樹進(jìn)行遍歷時(shí)，遞歸調(diào)用和棧的使用都帶來額外空間增加，遞歸調(diào)用的深度和棧的大小是動(dòng)態(tài)變化的，都與二叉樹的高度有關(guān)。因此，在最壞的情況下，即二叉樹退化為單支樹的情況下，遞歸的深度或棧需要的存儲(chǔ)空間等于二叉樹中的結(jié)點(diǎn)數(shù)。還有一類二叉樹的遍歷算法，就是不用棧也不用遞歸來實(shí)現(xiàn)。常用的不用棧的二叉樹遍歷的非遞歸方法有以下三種：（1）對(duì)二叉樹采用三叉鏈表存放，即在二叉樹的每個(gè)結(jié)點(diǎn)中增加一個(gè)雙親域parent，這樣，在遍歷深入到不能再深入時(shí)，可沿著走過的路徑回退到任何一棵子樹的根結(jié)點(diǎn)，并再向另一方向走。由于這一方法的實(shí)現(xiàn)是在每個(gè)結(jié)點(diǎn)的存儲(chǔ)上又增加一個(gè)雙親域，故其存儲(chǔ)開銷就會(huì)增加。（2）采用逆轉(zhuǎn)鏈的方法，即在遍歷深入時(shí)，每深入一層，就將其再深入的孩子結(jié)點(diǎn)的地址取出，并將其雙親結(jié)點(diǎn)的地址存入，當(dāng)深入不下去需返回時(shí)，可逐級(jí)取出雙親結(jié)點(diǎn)的地址，沿原路返回。雖然此種方法是在二叉鏈表上實(shí)現(xiàn)的，沒有增加過多的存儲(chǔ)空間，但在執(zhí)行遍歷的過程中改變子女指針的值，這既是以時(shí)間換取空間，同時(shí)當(dāng)有幾個(gè)用戶同時(shí)使用這個(gè)算法時(shí)將會(huì)發(fā)生問題。（3）在線索二叉樹上的遍歷，即利用具有n個(gè)結(jié)點(diǎn)的二叉樹中的葉子結(jié)點(diǎn)和一度結(jié)點(diǎn)的n＋1個(gè)空指針域，來存放線索，然后在這種具有線索的二叉樹上遍歷時(shí)，就可不需要棧，也不需要遞歸了。有關(guān)線索二叉樹的詳細(xì)內(nèi)容，將在下一節(jié)中討論。6.4線索二叉樹6.4.1線索二叉樹的定義及結(jié)構(gòu)1．線索二叉樹的定義按照某種遍歷方式對(duì)二叉樹進(jìn)行遍歷，可以把二叉樹中所有結(jié)點(diǎn)排列為一個(gè)線性序列。在該序列中，除第一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)結(jié)點(diǎn)；除最后一個(gè)結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接后繼結(jié)點(diǎn)。但是，二叉樹中每個(gè)結(jié)點(diǎn)在這個(gè)序列中的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么，二叉樹的存儲(chǔ)結(jié)構(gòu)中并沒有反映出來，只能在對(duì)二叉樹遍歷的動(dòng)態(tài)過程中得到這些信息。為了保留結(jié)點(diǎn)在某種遍歷序列中直接前驅(qū)和直接后繼的位置信息，可以利用二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)中的那些空指針域來指示。這些指向直接前驅(qū)結(jié)點(diǎn)和指向直接后繼結(jié)點(diǎn)的指針被稱為線索（thread），加了線索的二叉樹稱為線索二叉樹。線索二叉樹將為二叉樹的遍歷提供許多遍歷。2．線索二叉樹的結(jié)構(gòu)一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹若采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，在2n個(gè)指針域中只有n－1個(gè)指針域是用來存儲(chǔ)結(jié)點(diǎn)孩子的地址，而另外n＋1個(gè)指針域存放的都是NULL。因此，可以利用某結(jié)點(diǎn)空的左指針域（lchild）指出該結(jié)點(diǎn)在某種遍歷序列中的直接前驅(qū)結(jié)點(diǎn)的存儲(chǔ)地址，利用結(jié)點(diǎn)空的右指針域（rchild）指出該結(jié)點(diǎn)在某種遍歷序列中的直接后繼結(jié)點(diǎn)的存儲(chǔ)地址；對(duì)于那些非空的指針域，則仍然存放指向該結(jié)點(diǎn)左、右孩子的指針。這樣，就得到了一棵線索二叉樹。由于序列可由不同的遍歷方法得到，因此，線索樹有先序線索二叉樹、中序線索二叉樹和后序線索二叉樹三種。把二叉樹改造成線索二叉樹的過程稱為線索化。對(duì)圖6.3(b)所示的二叉樹進(jìn)行線索化，得到先序線索二叉樹、中序線索二叉樹和后序線索二叉樹分別如圖6.11(a)、(b)、(c)所示。圖中實(shí)線表示指針，虛線表示線索。那么，下面的問題是在存儲(chǔ)中，如何區(qū)別某結(jié)點(diǎn)的指針域內(nèi)存放的是指針還是線索？通?？梢圆捎孟旅鎯煞N方法來實(shí)現(xiàn)。為每個(gè)結(jié)點(diǎn)增設(shè)兩個(gè)標(biāo)志位域ltag和rtag，令：{0{0lchild指向結(jié)點(diǎn)的左孩子1lchild指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)ltag＝{0{0rchild指向結(jié)點(diǎn)的右孩子1rchild指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)rtag＝每個(gè)標(biāo)志位令其只占一個(gè)bit，這樣就只需增加很少的存儲(chǔ)空間。這樣結(jié)點(diǎn)的結(jié)構(gòu)為：rtagrchilddatalchildltagrtagrchilddatalchildltag（2）不改變結(jié)點(diǎn)結(jié)構(gòu)，僅在作為線索的地址前加一個(gè)負(fù)號(hào)，即負(fù)的地址表示線索，正的地址表示指針。AAAACBCBCBCBEFEEFEFDDFDDGGGG(a)先序線索二叉樹(b)中序線索二叉樹AABCBCEFDEFDGG(c)后序線索二叉樹圖6.11線索二叉樹這里我們按第一種方法來介紹線索二叉樹的存儲(chǔ)。為了將二叉樹中所有空指針域都利用上，以及操作便利的需要，在存儲(chǔ)線索二叉樹時(shí)往往增設(shè)一頭結(jié)點(diǎn)，其結(jié)構(gòu)與其它線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)一樣，只是其數(shù)據(jù)域不存放信息，其左指針域指向二叉樹的根結(jié)點(diǎn)，右指針域指向自己。而原二叉樹在某序遍歷下的第一個(gè)結(jié)點(diǎn)的前驅(qū)線索和最后一個(gè)結(jié)點(diǎn)的后繼線索都指向該頭結(jié)點(diǎn)。6.4.2線索二叉樹的基本操作實(shí)現(xiàn)在線索二叉樹中，結(jié)點(diǎn)的結(jié)構(gòu)可以定義為如下形式：typedefcharelemtype;typedefstructBiThrNode{elemtypedata;structBiThrNode*lchild;structBiThrNode*rchild;unsignedltag:1;unsignedrtag:1;}BiThrNodeType,*BiThrTree;下面以中序線索二叉樹為例，討論線索二叉樹的建立、線索二叉樹的遍歷以及在線索二叉樹上查找前驅(qū)結(jié)點(diǎn)、查找后繼結(jié)點(diǎn)、插入結(jié)點(diǎn)和刪除結(jié)點(diǎn)等操作的實(shí)現(xiàn)算法。1．建立一棵中序線索二叉樹建立線索二叉樹，或者說對(duì)二叉樹線索化，實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，訪問結(jié)點(diǎn)的操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域是否為空，如果為空，將它們改為指向前驅(qū)結(jié)點(diǎn)或后繼結(jié)點(diǎn)的線索。為實(shí)現(xiàn)這一過程，設(shè)指針pre始終指向剛剛訪問過的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便增設(shè)線索。另外，在對(duì)一棵二叉樹加線索時(shí)，必須首先申請(qǐng)一個(gè)頭結(jié)點(diǎn)，建立頭結(jié)點(diǎn)與二叉樹的根結(jié)點(diǎn)的指向關(guān)系，對(duì)二叉樹線索化后，還需建立最后一個(gè)結(jié)點(diǎn)與頭結(jié)點(diǎn)之間的線索。下面是建立中序線索二叉樹的遞歸算法，其中pre為全局變量。intInOrderThr(BiThrTree*head,BiThrTreeT){/*中序遍歷二叉樹T，并將其中序線索化，*head指向頭結(jié)點(diǎn)。*/if(!(*head=(BiThrNodeType*)malloc(sizeof(BiThrNodeType))))return0;(*head)->ltag=0;(*head)->rtag=1;/*建立頭結(jié)點(diǎn)*/(*head)->rchild=*head;/*右指針回指*/if(!T)(*head)->lchild=*head;/*若二叉樹為空，則左指針回指*/else{(*head)->lchild=T;pre=head;InThreading(T);/*中序遍歷進(jìn)行中序線索化*/pre->rchild=*head;pre->rtag=1;/*最后一個(gè)結(jié)點(diǎn)線索化*/(*head)->rchild=pre;}return1;}算法6.13voidInTreading(BiThrTreep){/*中序遍歷進(jìn)行中序線索化*/if(p){InThreading(p->lchild);/*左子樹線索化*/if(!p->lchild)/*前驅(qū)線索*/{p->ltag=1;p->lchild=pre;}if(!pre->rchild)/*后繼線索*/{pre->rtag=1;pre->rchild=p;}pre=p;InThreading(p->rchild);/*右子樹線索化*/}}算法6.142．在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序前驅(qū)結(jié)點(diǎn)對(duì)于中序線索二叉樹上的任一結(jié)點(diǎn)，尋找其中序的前驅(qū)結(jié)點(diǎn)，有以下兩種情況：如果該結(jié)點(diǎn)的左標(biāo)志為1，那么其左指針域所指向的結(jié)點(diǎn)便是它的前驅(qū)結(jié)點(diǎn)；（2）如果該結(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í)，它就是所要找的前驅(qū)結(jié)點(diǎn)。在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn)的算法如下：BiThrTreeInPreNode（BiThrTreep）{/*在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序前驅(qū)結(jié)點(diǎn)*/BiThrTreepre;pre=p->lchild;if(p->ltag!=1)while(pre->rtag==0)pre=pre->rchild;return(pre);}算法6.153．在中序線索二叉樹上查找任意結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)對(duì)于中序線索二叉樹上的任一結(jié)點(diǎn)，尋找其中序的后繼結(jié)點(diǎn)，有以下兩種情況：如果該結(jié)點(diǎn)的右標(biāo)志為1，那么其右指針域所指向的結(jié)點(diǎn)便是它的后繼結(jié)點(diǎn)；（2）如果該結(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)。在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序后繼結(jié)點(diǎn)的算法如下：BiThrTreeInPostNode（BiThrTreep）{/*在中序線索二叉樹上尋找結(jié)點(diǎn)p的中序后繼結(jié)點(diǎn)*/BiThrTreepost;post=p->rchild;if(p->rtag!=1)while(post->rtag==0)post=post->lchild;return(post);}算法6.16以上給出的僅是在中序線索二叉樹中尋找某結(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)。在此就不再討論了。4．在中序線索二叉樹上查找任意結(jié)點(diǎn)在先序下的后繼這一操作的實(shí)現(xiàn)依據(jù)是：若一個(gè)結(jié)點(diǎn)是某子樹在中序下的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹在先序下的最后一個(gè)結(jié)點(diǎn)。該結(jié)論可以用反證法證明。下面就依據(jù)這一結(jié)論，討論在中序線索二叉樹上查找某結(jié)點(diǎn)在先序下后繼結(jié)點(diǎn)的情況。設(shè)開始時(shí)，指向此某結(jié)點(diǎn)的指針為p。若待確定先序后繼的結(jié)點(diǎn)為分支結(jié)點(diǎn)，則又有兩種情況：①當(dāng)p->ltag=0時(shí)，p->lchild為p在先序下的后繼；②當(dāng)p->ltag=1時(shí)，p->rchild為p在先序下的后繼。若待確定先序后繼的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則也有兩種情況：①若p->rchild是頭結(jié)點(diǎn)，則遍歷結(jié)束；②若p->rchild不是頭結(jié)點(diǎn)，則p結(jié)點(diǎn)一定是以p->rchild結(jié)點(diǎn)為根的左子樹中在中序遍歷下的最后一個(gè)結(jié)點(diǎn)，因此p結(jié)點(diǎn)也是在該子樹中按先序遍歷的最后一個(gè)結(jié)點(diǎn)。此時(shí)，若p->rchild結(jié)點(diǎn)有右子樹，則所找結(jié)點(diǎn)在先序下的后繼結(jié)點(diǎn)的地址為p->rchild->rchild；若p->rchild為線索，則讓p＝p->rchild，反復(fù)情況（2）的判定。在中序線索二叉樹上尋找結(jié)點(diǎn)p的先序后繼結(jié)點(diǎn)的算法如下：BiThrTreeIPrePostNode（BiThrTreehead,BiThrTreep）{/*在中序線索二叉樹上尋找結(jié)點(diǎn)p的先序的后繼結(jié)點(diǎn),head為線索樹的頭結(jié)點(diǎn)*/BiThrTreepost;if(p->ltag==0)post=p->lchild;else{post=p;while(post->rtag==1&&post->rchild!=head)post=post->rchild;post=post->rchild;}return(post);}算法6.175．在中序線索二叉樹上查找任意結(jié)點(diǎn)在后序下的前驅(qū)這一操作的實(shí)現(xiàn)依據(jù)是：若一個(gè)結(jié)點(diǎn)是某子樹在中序下的第一個(gè)結(jié)點(diǎn)，則它必是該子樹在后序下的第一個(gè)結(jié)點(diǎn)。該結(jié)論可以用反證法證明。下面就依據(jù)這一結(jié)論，討論在中序線索二叉樹上查找某結(jié)點(diǎn)在后序下前驅(qū)結(jié)點(diǎn)的情況。設(shè)開始時(shí)，指向此某結(jié)點(diǎn)的指針為p。（1）若待確定后序前驅(qū)的結(jié)點(diǎn)為分支結(jié)點(diǎn)，則又有兩種情況：①當(dāng)p->ltag=0時(shí)，p->lchild為p在后序下的前驅(qū)；②當(dāng)p->ltag=1時(shí)，p->rchild為p在后序下的前驅(qū)。（2）若待確定后序前驅(qū)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，則也有兩種情況：①若p->lchild是頭結(jié)點(diǎn)，則遍歷結(jié)束；②若p->lchild不是頭結(jié)點(diǎn)，則p結(jié)點(diǎn)一定是以p->lchild結(jié)點(diǎn)為根的右子樹中在中中序遍歷下的第一個(gè)結(jié)點(diǎn)，因此p結(jié)點(diǎn)也是在該子樹中按后序遍歷的第一個(gè)結(jié)點(diǎn)。此時(shí)，若p->lchild結(jié)點(diǎn)有左子樹，則所找結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的地址為p->lchild->lchild；若p->lchild為線索，則讓p＝p->lchild，反復(fù)情況（2）的判定。在中序線索二叉樹上尋找結(jié)點(diǎn)p的后序前驅(qū)結(jié)點(diǎn)的算法如下：BiThrTreeIPostPretNode（BiThrTreehead,BiThrTreep）{/*在中序線索二叉樹上尋找結(jié)點(diǎn)p的先序的后繼結(jié)點(diǎn)，head為線索樹的頭結(jié)點(diǎn)*/BiThrTreepre;if(p->rtag==0)pre=p->rchild;else{pre=p;while(pre->ltag==1&&post->rchild!=head)pre=pre->lchild;pre=pre->lchild;}return(pre);}算法6.186．在中序線索二叉樹上查找值為x的結(jié)點(diǎn)利用在中序線索二叉樹上尋找后繼結(jié)點(diǎn)和前驅(qū)結(jié)點(diǎn)的算法，就可以遍歷到二叉樹的所有結(jié)點(diǎn)。比如，先找到按某序遍歷的第一個(gè)結(jié)點(diǎn)，然后再依次查詢其后繼；或先找到按某序遍歷的最后一個(gè)結(jié)點(diǎn)，然后再依次查詢其前驅(qū)。這樣，既不用棧也不用遞歸就可以訪問到二叉樹的所有結(jié)點(diǎn)。在中序線索二叉樹上查找值為x的結(jié)點(diǎn)，實(shí)質(zhì)上就是在線索二叉樹上進(jìn)行遍歷，將訪問結(jié)點(diǎn)的操作具體寫為那結(jié)點(diǎn)的值與x比較的語句。下面給出其算法：BiThrTreeSearch(BiThrTreehead,elemtypex){/*在以head為頭結(jié)點(diǎn)的中序線索二叉樹中查找值為x的結(jié)點(diǎn)*/BiThrTreep;p=head->lchild;while(p->ltag==0&&p!=head)p=p->lchild;while(p!=head&&p->data!=x)p=InPostNode(p);if(p==head){printf(“NotFoundthedata!\n”);return(0);}elsereturn(p);}算法6.197．在中序線索二叉樹上的更新線索二叉樹的更新是指，在線索二叉樹中插入一個(gè)結(jié)點(diǎn)或者刪除一個(gè)結(jié)點(diǎn)。一般情況下，這些操作有可能破壞原來已有的線索，因此，在修改指針時(shí)，還需要對(duì)線索做相應(yīng)的修改。一般來說，這個(gè)過程的代價(jià)幾乎與重新進(jìn)行線索化相同。這里僅討論一種比較簡(jiǎn)單的情況，即在中序線索二叉樹中插入一個(gè)結(jié)點(diǎn)p，使它成為結(jié)點(diǎn)s的右孩子。下面分兩種情況來分析：（1）若s的右子樹為空，如圖6.13(a)所示，則插入結(jié)點(diǎn)p之后成為圖6.13(b)所示的情形。在這種情況中，s的后繼將成為p的中序后繼，s成為p的中序前驅(qū)，而p成為s的右孩子。二叉樹中其它部分的指針和線索不發(fā)生變化。（2）若s的右子樹非空，如圖6.14(a)所示，插入結(jié)點(diǎn)p之后如圖6.14(b)所示。S原來的右子樹變成p的右子樹，由于p沒有左子樹，故s成為p的中序前驅(qū)，p成為s的右孩子；又由于s原來的后繼成為p的后繼，因此還要將s原來的本來指向s的后繼的左線索，改為指向p。NULLNULLsssssspspspp(a)(b)(a)(b)圖6.13中序線索樹更新位置右子樹為空?qǐng)D6.14中序線索樹更新位置右子樹不為空下面給出上述操作的算法。voidInsertThrRight(BiThrTrees,BiThrTreep){/*在中序線索二叉樹中插入結(jié)點(diǎn)p使其成為結(jié)點(diǎn)s的右孩子*/BiThrTreew;p->rchild=s->rchild;p->rtag=s->rtag;p->lchild=s;p->ltag=1;/*將s變?yōu)閜的中序前驅(qū)*/s->rchild=p;s->rtag=0;/*p成為s的右孩子*/if(p->rtag==0)/*當(dāng)s原來右子樹不空時(shí)，找到s的后繼w，變w為p的后繼，p為w的前驅(qū)*/{w=InPostNode(p);w->lchild=p;}}算法6.206.5二叉樹的應(yīng)用6.5.1二叉樹遍歷的應(yīng)用在以上討論的遍歷算法中，訪問結(jié)點(diǎn)的數(shù)據(jù)域信息，即操作Visite（bt->data）具有更一般的意義，需根據(jù)具體問題，對(duì)bt數(shù)據(jù)進(jìn)行不同的操作。下面介紹幾個(gè)遍歷操作的典型應(yīng)用。1．查找數(shù)據(jù)元素Search（bt，x）在bt為二叉樹的根結(jié)點(diǎn)指針的二叉樹中查找數(shù)據(jù)元素x。查找成功時(shí)返回該結(jié)點(diǎn)的指針；查找失敗時(shí)返回空指針。算法實(shí)現(xiàn)如下，注意遍歷算法中的Visite(bt->data)等同于其中的一組操作步驟。BiTreeSearch（BiTreebt，elemtypex）{/*在bt為根結(jié)點(diǎn)指針的二叉樹中查找數(shù)據(jù)元素x*/BiTreep;if(bt->data==x)returnbt;/*查找成功返回*/if(bt->lchild!=NULL)return(Search(bt->lchild,x));/*在bt->lchild為根結(jié)點(diǎn)指針的二叉樹中查找數(shù)據(jù)元素x*/if(bt->rchild!=NULL)return(Search(bt->rchild,x));/*在bt->rchild為根結(jié)點(diǎn)指針的二叉樹中查找數(shù)據(jù)元素x*/returnNULL;/*查找失敗返回*/}算法6.212．統(tǒng)計(jì)出給定二叉樹中葉子結(jié)點(diǎn)的數(shù)目（1）順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)intCountLeaf1（SqBiTreebt，intk）{/*一維數(shù)組bt[2k-1]為二叉樹存儲(chǔ)結(jié)構(gòu)，k為二叉樹深度，函數(shù)值為葉子數(shù)。*/total=0;for(i=1;i<=2k-1;i++){if(bt[i]!=0){if((bt[2i]==0&&bt[2i+1]==0)||(i>(2k-1)/2))total++;}}return(total);}算法6.22（2）二叉鏈表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)intCountLeaf2（BiTreebt）{/*開始時(shí)，bt為根結(jié)點(diǎn)所在鏈結(jié)點(diǎn)的指針，返回值為bt的葉子數(shù)*/if(bt==NULL)return(0);if(bt->lchild==NULL&&bt->rchild==NULL)return(1);return(CountLeaf2(bt->lchild)+CountLeaf2(bt->rchild));}算法6.233．創(chuàng)建二叉樹二叉鏈表存儲(chǔ)，并顯示。設(shè)創(chuàng)建時(shí)，按二叉樹帶空指針的先序次序輸入結(jié)點(diǎn)值，結(jié)點(diǎn)值類型為字符型。輸出按中序輸出。CreateBinTree（BinTree*bt）是以二叉鏈表為存儲(chǔ)結(jié)構(gòu)建立一棵二叉樹T的存儲(chǔ)，bt為指向二叉樹T根結(jié)點(diǎn)指針的指針。設(shè)建立時(shí)的輸入序列為：AB0D00CE00F建立如圖6.3(b)所示的二叉樹存儲(chǔ)。InOrderOut（bt）為按中序輸出二叉樹bt的結(jié)點(diǎn)。算法實(shí)現(xiàn)如下，注意在創(chuàng)建算法中，遍歷算法中的Visite(bt->data)被讀入結(jié)點(diǎn)、申請(qǐng)空間存儲(chǔ)的操作所代替；在輸出算法中，遍歷算法中的Visite(bt->data)被c語言中的格式輸出語句所代替。voidCreateBinTree(BinTree*T){/*以加入結(jié)點(diǎn)的先序序列輸入，構(gòu)造二叉鏈表*/charch;scanf("\n%c",&ch);if(ch=='0')*T=NULL;/*讀入0時(shí)，將相應(yīng)結(jié)點(diǎn)置空*/else{*T=(BinTNode*)malloc(sizeof(BinTNode));/*生成結(jié)點(diǎn)空間*/ (*T)->data=ch; CreateBinTree(&(*T)->lchild);/*構(gòu)造二叉樹的左子樹*/ CreateBinTree(&(*T)->rchild);/*構(gòu)造二叉樹的右子樹*/ }}voidInOrderOut(BinTreeT){/*中序遍歷輸出二叉樹T的結(jié)點(diǎn)值*/if(T) {InOrderOut(T->lchild);/*中序遍歷二叉樹的左子樹*/ printf("%3c",T->data);/*訪問結(jié)點(diǎn)的數(shù)據(jù)*/ InOrderOut(T->rchild);/*中序遍歷二叉樹的右子樹*/}}main(){BiTreebt;CreateBinTree(&bt);InOrderOut(bt);}算法6.246.5.2最優(yōu)二叉樹――哈夫曼樹1．哈夫曼樹的基本概念最優(yōu)二叉樹，也稱哈夫曼（Haffman）樹，是指對(duì)于一組帶有確定權(quán)值的葉結(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹。那么什么是二叉樹的帶權(quán)路徑長(zhǎng)度呢？在前面我們介紹過路徑和結(jié)點(diǎn)的路徑長(zhǎng)度的概念，而二叉樹的路徑長(zhǎng)度則是指由根結(jié)點(diǎn)到所有葉結(jié)點(diǎn)的路徑長(zhǎng)度之和。如果二叉樹中的葉結(jié)點(diǎn)都具有一定的權(quán)值，則可將這一概念加以推廣。設(shè)二叉樹具有n個(gè)帶權(quán)值的葉結(jié)點(diǎn)，那么從根結(jié)點(diǎn)到各個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長(zhǎng)度，記為：n∑k=1WPL＝Wk·Lk其中Wk為第k個(gè)葉結(jié)點(diǎn)的權(quán)值，Lk為第k個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度。如圖6.16所示的二叉樹，它的帶權(quán)路徑長(zhǎng)度值WPL＝2×2＋4×2＋5×2＋3×2＝28。在給定一組具有確定權(quán)值的葉結(jié)點(diǎn)，可以構(gòu)造出不同的帶權(quán)二叉樹。例如，給出4個(gè)葉結(jié)點(diǎn)，設(shè)其權(quán)值分別為1，3，5，7，我們可以構(gòu)造出形狀不同的多個(gè)二叉樹。這些形狀不同的二叉樹的帶權(quán)路徑長(zhǎng)度將各不相同。圖6.17給出了其中5個(gè)不同形狀的二叉樹。這五棵樹的帶權(quán)路徑長(zhǎng)度分別為：（a）WPL＝1×2＋3×2＋5×2＋7×2＝323542（b）WPL＝1×3＋3×3＋5×2＋7×1＝293542（c）WPL＝1×2＋3×3＋5×3＋7×1＝33（d）WPL＝7×3＋5×3＋3×2＋1×1＝43圖6.16一個(gè)帶權(quán)二叉樹（e）WPL＝7×1＋5×2＋3×3＋1×3＝29777755311753131175315353(a)(b)(c)7171535357573131(d)(e)圖6.17具有相同葉子結(jié)點(diǎn)和不同帶權(quán)路徑長(zhǎng)度的二叉樹由此可見，由相同權(quán)值的一組葉子結(jié)點(diǎn)所構(gòu)成的二叉樹有不同的形態(tài)和不同的帶權(quán)路徑長(zhǎng)度，那么如何找到帶權(quán)路徑長(zhǎng)度最小的二叉樹（即哈夫曼樹）呢？根據(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í)，這棵二叉樹便是所要建立的哈夫曼樹。圖6.18給出了前面提到的葉結(jié)點(diǎn)權(quán)值集合為W＝{1，3，5，7}的哈夫曼樹的構(gòu)造過程?？梢杂?jì)算出其帶權(quán)路徑長(zhǎng)度為29，由此可見，對(duì)于同一組給定葉結(jié)點(diǎn)所構(gòu)造的哈夫曼樹，樹的形狀可能不同，但帶權(quán)路徑長(zhǎng)度值是相同的，一定是最小的。4第一步第二步45713575713573131第三步第四步1691697794759475413541351313圖6.18哈夫曼樹的建立過程2．哈夫曼樹的構(gòu)造算法在構(gòu)造哈夫曼樹時(shí)，可以設(shè)置一個(gè)結(jié)構(gòu)數(shù)組HuffNode保存哈夫曼樹中各結(jié)點(diǎn)的信息，根據(jù)二叉樹的性質(zhì)可知，具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n－1個(gè)結(jié)點(diǎn)，所以數(shù)組HuffNode的大小設(shè)置為2n－1，數(shù)組元素的結(jié)構(gòu)形式如下：rchildweightlchildparentrchildweightlchildparent其中，weight域保存結(jié)點(diǎn)的權(quán)值，lchild和rchild域分別保存該結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)在數(shù)組HuffNode中的序號(hào)，從而建立起結(jié)點(diǎn)之間的關(guān)系。為了判定一個(gè)結(jié)點(diǎn)是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。初始時(shí)parent的值為0，當(dāng)結(jié)點(diǎn)加入到樹中時(shí)，該結(jié)點(diǎn)parent的值為其雙親結(jié)點(diǎn)在數(shù)組HuffNode中的序號(hào)，就不會(huì)是0了。構(gòu)造哈夫曼樹時(shí)，首先將由n個(gè)字符形成的n個(gè)葉結(jié)點(diǎn)存放到數(shù)組HuffNode的前