數(shù)據(jù)結(jié)構(gòu) 第6章 樹和森林

第六章樹和森林主要內(nèi)容樹的概念二叉樹二叉樹的存儲結(jié)構(gòu)遍歷二叉樹線索二叉樹二叉樹的應(yīng)用樹的概念某家族的血統(tǒng)關(guān)系如下：張宇有四個孩子分別是：張山、張川、張星和張月；張山有二個孩子張冰和張雪；張星有三個孩子張雨、張云和張風(fēng)；張云有兩個孩子張亮和張麗。

樹的定義：樹（tree）T是一個包含n(n>=0)個數(shù)據(jù)元素的有限集合。并且有：（1）當(dāng)n=0時，T稱為空樹；（2）如果n>0，則樹有且僅有一個特定的被稱為根（root）的結(jié)點，樹的根結(jié)點只有后繼，沒有前驅(qū)；（3）當(dāng)n>1時,除根結(jié)點以外的其余結(jié)點可分為m(m>0)個互不相交的非空有限集T1、T2、...、Tm,其中每一個集合本身又是一棵非空樹,并且稱它們?yōu)楦Y(jié)點的子樹（subtree）。

如右圖（a）表示了一棵空樹，它沒有數(shù)據(jù)元素；如右圖（b）表示了只有一個數(shù)據(jù)元素的樹，樹中只有一個沒有子樹的根結(jié)點A；如右圖（c）是有14個數(shù)據(jù)元素結(jié)點的樹，其中A是樹根，其余結(jié)點分成三個互不相交的有限集：T1={B,E,F,K,L}、T2={C,G}、T3={D,H,I,J,M,N}，T1、T2、T3又都是樹，且它們是結(jié)點A的子樹。樹的術(shù)語：

1．結(jié)點（node）：在樹中每一個數(shù)據(jù)元素及指向其子樹根的分支稱為一個結(jié)點。

2．結(jié)點的度（degreeofnode）：一個結(jié)點的子樹數(shù)目稱之為該結(jié)點的度。例如在圖（c）所示的樹中,結(jié)點A的度為3，結(jié)點C的度數(shù)為1,結(jié)點E的度數(shù)為0。

3．終端結(jié)點(terminalnode)：在樹中，度為0的結(jié)點稱為終端結(jié)點或葉子(leaf)。如在圖6-2（c）所示的樹中，結(jié)點E，K，L，G，H，M，N，J都是樹的葉子。

4．非終端結(jié)點(nonterminalnode)：在樹中，度不為0的結(jié)點稱為非終端結(jié)點或分支結(jié)點。除根結(jié)點之外的分支結(jié)點也稱內(nèi)部結(jié)點。如在圖6-2（c）所示的樹中，結(jié)點A、B、C、D、F、I都是樹的分支結(jié)點，且結(jié)點B、C、D、F、I是樹T的內(nèi)部結(jié)點。5．樹的度（degreeoftree）：樹的結(jié)點中，最大的度稱為該樹的度。如圖6-2（c）所示的樹，其度為3。6．孩子(child)和雙親(parent)：在樹中，結(jié)點p的子樹的根稱為結(jié)點p的孩子；反之,這個結(jié)點p稱為其孩子的雙親（父親）。如在圖6-2（c）所示的樹中，結(jié)點D為結(jié)點A的子樹的根，因此結(jié)點D是結(jié)點A的孩子，結(jié)點A是結(jié)點D的雙親結(jié)點（父結(jié)點）。7．兄弟(sibling)：在樹中，同一個雙親的孩子之間互稱為兄弟。例如，在圖6-2（c）所示的樹中，結(jié)點B、C、D互為兄弟。8．祖先(ancestor)：在樹中，從根結(jié)點到結(jié)點x所經(jīng)的分支上的所有結(jié)點稱為結(jié)點x的祖先。如在圖6-2（c）所示的樹中，結(jié)點M的祖先為：A、D、I。9．子孫（descendant）：在樹中，以某結(jié)點p為根的子樹中的所有結(jié)點都稱為結(jié)點p的子孫。例如在圖6-2（c）所示的樹中，D的子孫有H、I、J、M、N。10．結(jié)點的層次（level）：在樹中，從根結(jié)點開始，根為第一層，根的孩子為第二層，依次類推，樹中任一結(jié)點的層次是其雙親結(jié)點層次數(shù)加1。例如在圖6-2（c）所示的樹中，結(jié)點K、L、M、N的層次數(shù)為4。11．樹的深度（depth）：樹中結(jié)點的最大層次稱為樹的深度或樹的高度（height）。例如圖6-2（c）所示的樹的深度為4。12．堂兄弟：雙親在同一層的結(jié)點互稱為堂兄弟。如在圖6-2（c）所示的樹中，結(jié)點F、G、H互稱為堂兄弟。13．有序樹：如果樹中結(jié)點p的各棵子樹是有次序的則稱該樹為有序樹，此時結(jié)點p從左到右的k子樹分別稱為p的第1棵子樹、第2棵子樹、…、第k棵子樹。14．無序樹：如果樹中結(jié)點的各棵子樹的次序是無關(guān)的則稱該樹為稱無序樹。15．森林(forest)：森林是m(m>0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。

樹的表示形式：樹形表示法嵌套集合表示法凹入目錄表示法廣義表形式的表示法。

由于樹形表示法比較直觀，所以在本書中主要采用樹形表示法來表示樹形結(jié)構(gòu)。樹的基本操作：（1）Root()：求樹根結(jié)點的指針，若樹為空，則返回0。（2）CreateRoot(d):建立樹的根結(jié)點，使根結(jié)點的數(shù)據(jù)元素值為d。（3）Parent(x)：求樹中給定結(jié)點x的雙親結(jié)點的指針，若x為根結(jié)點，則返回空。（4）FirstChild(x)：求樹中給定結(jié)點x的第一個孩子結(jié)點的的指針，若x為葉子結(jié)點，則返回空。（5）NextSibling(x,y)：給定結(jié)點x、y，其中結(jié)點y是結(jié)點x的一個孩子。該函數(shù)求樹中結(jié)點y的下一個兄弟結(jié)點的指針，若結(jié)點y是結(jié)點x的最后一個孩子，則返回空。（6）PreSibling(x,y)給定結(jié)點x、y，其中結(jié)點y是結(jié)點x的一個孩子。該函數(shù)求樹中結(jié)點y的前一個兄弟結(jié)點的指針，若結(jié)點y是結(jié)點x的第一個孩子，則返回空。（7）Retrieve(x)：求給定結(jié)點x中數(shù)據(jù)元素的值。（8）Assign(x，d)：對二叉樹中給定結(jié)點x賦值為d。（9）InsertChild(x,d)：在結(jié)點x下插入數(shù)據(jù)元素值為d的新孩子結(jié)點，若插入成功，則返回1；否則返回0。（10）DeleteChild(x,i)：刪除以結(jié)點x的第i個孩子為根的子樹，若刪除成功，則返回1；否則返回0。（11）DeleteSubTree(x)：刪除以結(jié)點x為根的子樹；（12）IsEmpty()：判斷樹是否為空樹。若樹為空樹，則返回1；否則返回0。（13）Travers（）：遍歷樹，按某種次序依次訪問樹中的每一個結(jié)點，并使每一個結(jié)點只被訪問一次。二叉樹

二叉樹的定義:

二叉樹BT是有限個結(jié)點的集合。當(dāng)集合非空時，其中有一個結(jié)點稱為二叉樹的根結(jié)點，用BT表示，余下的結(jié)點（如果有的話）最多被組成兩棵分別被稱為BT的左子樹（leftsubtree）和右子樹（rightsubtree）、互不相交的二叉樹。二叉樹的五種形態(tài):二叉樹的性質(zhì):性質(zhì)1：有n(n>0)個結(jié)點的二叉樹的分支數(shù)為n-1。證明：因為在二叉樹中，除根結(jié)點以外的其它每個結(jié)點有且僅有一個父結(jié)點。而子結(jié)點與父結(jié)點間有且只有一條分支，因此對于有n(n>0)個結(jié)點的二叉樹，其分支的數(shù)目為n-1。性質(zhì)2：若二叉樹的高度為h（h≥0），則該二叉樹最少有h個結(jié)點，最多有2h-1個結(jié)點。證明：因為在二叉樹中，每一層至少要有1個結(jié)點，因此對于高度為h的二叉樹，其結(jié)點數(shù)至少為h個。在二叉樹中，第一層只有一個根結(jié)點；又因為每個結(jié)點最多有2個孩子結(jié)點，所以第i層的結(jié)點最多為2i-1個，所以高度為h（h≥0）的二叉樹結(jié)點總數(shù)最多為：20+21+…+2h-1=2h-1性質(zhì)3：含有n個結(jié)點的二叉樹的高度最大值為n，最小值為log2(n+1)

。證明：因為在二叉樹中，每層至少有一個結(jié)點，因此對于含有n個結(jié)點的二叉樹，其高度不會超過n。根據(jù)性質(zhì)2可以得知，高度為h的二叉樹最多有2h-1個結(jié)點，即n≤2h-1，因此h≥log2(n+1)。由于h是整數(shù)，所以h≥log2(n+1)。滿二叉樹的定義：若高度為h的二叉樹具有最大數(shù)目（2h-1個）的結(jié)點，則稱其為滿二叉樹（fullbinarytree）。完全二叉樹的定義：若高度為h的二叉樹，除第h層外，其它各層(1h-1)的結(jié)點數(shù)都達(dá)到最大個數(shù)，并且第h層的結(jié)點是自左向右連續(xù)分布的。則稱它為完全二叉樹（completebinarytree）。性質(zhì)4：具有n個結(jié)點的完全二叉樹的高度為log2(n+1)

。證明：設(shè)完全二叉樹的高度為h，則由性質(zhì)2得：2h-1-1＜n≤2h-12h-1＜n+1≤2h

不等式中的各項取對數(shù)得：h-1＜log2(n+1)≤h。因為h為整數(shù)，所以h=log2(n+1)。性質(zhì)5：如果將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號0、1、2、…、n-1。則有以下關(guān)系：（1）若i＝0，則i無雙親，若i＞0，則i的雙親為i/2-1；（2）若2*i+1<n，則i的左孩子為2*i+1；（3）若2*i+2<n，則i的右孩子為2*i+2；（4）若i為偶數(shù)，且i≥1，則i是其雙親的右孩子，且其有編號為i-1左兄弟；（5）若i為奇數(shù)，且i＜n-1，則i是其雙親的左孩子，且其有編號為i+1右兄弟。證明：此性質(zhì)可以用歸納法證明，在此先證明其中的(2)和(3)。當(dāng)i＝0時，由完全二叉樹的定義得知，如果2*i+1＝1<n，說明二叉樹中存在兩個或兩個以上的結(jié)點，所以結(jié)點i的左孩子存在且編號為1；反之，如果2*i+1＝1=n，說明二叉樹中只有一個結(jié)點i，結(jié)點i的左孩子結(jié)點不存在。同理，如果2i+2＝2<n，說明結(jié)點i的右孩子存在且編號為2；如果2*i+2＝2=n，說明二叉樹中不存在編號為2的結(jié)點，即結(jié)點i的右孩子不存在。

假設(shè)對于編號為j(0＜j＜i）的結(jié)點，(2)和(3)成立。當(dāng)i＝j(luò)+1時，根據(jù)完全二叉樹的定義，若其左孩子結(jié)點存在則其左孩子結(jié)點的編號等于編號為j的結(jié)點的右孩子的編號加1，即其左孩子結(jié)點的編號等于2*j+2+1＝2*i+1；同樣，當(dāng)i＝j(luò)+1時，根據(jù)完全二叉樹的定義，若其右孩子結(jié)點存在，則其右孩子結(jié)點的編號等于其左孩子結(jié)點的編號加1，即其右孩子結(jié)點的編號等于2i+1+1=2*i+2，因此性質(zhì)5的(2)，(3)得證。

由上述(2)和(3)可很容易證明(1)，證明如下：當(dāng)i＝0時，顯然該結(jié)點為根結(jié)點，所以它沒有雙親結(jié)點。當(dāng)i＞0時，設(shè)編號為i的結(jié)點的雙親結(jié)點的編號為f。如果i是其雙親結(jié)點的左孩子結(jié)點，根據(jù)性質(zhì)5的(2)有i＝2*f+1（i為奇數(shù)），即f＝(i-1)/2；如果結(jié)點i是其雙親結(jié)點的右孩子結(jié)點，根據(jù)性質(zhì)5的(3)有i＝2*f+2（i為偶數(shù)），即f＝i/2-1。綜合這兩種情況可以得到，當(dāng)i＞0時，其雙親結(jié)點的編號等于i/2-1。因此性質(zhì)5的(1)得證。二叉樹的基本操作:（1）IsEmpty()：判斷二叉樹是否為空。若二叉樹為空，則返回1；否則返回0。（2）Root()：求二叉樹根結(jié)點的指針，若二叉樹為空，則返回空指。（3）CreateRoot(d):建立二叉樹的根結(jié)點，使根結(jié)點的數(shù)據(jù)元素值為d。（4）Parent(p)：求二叉樹中給定結(jié)點p的雙親結(jié)點的指針，若p為根結(jié)點，則返回空。（5）LeftChild(p)：求二叉樹中給定結(jié)點p的左孩子結(jié)點的指針；若結(jié)點p沒有左孩子，則返回空。（6）RightChild(p)：求二叉樹中給定結(jié)點p的右孩子結(jié)點的指針；若結(jié)點p沒有右孩子，則返回空。（7）LeftSibling(p)：求二叉樹中給定結(jié)點p的左兄弟結(jié)點的指針；若結(jié)點p是其雙親的左孩子或結(jié)點p是其雙親的右孩子但其雙親沒有左孩子，則返回空。（8）RightSibling(p)：求二叉樹中給定結(jié)點p的右兄弟結(jié)點的指針；若結(jié)點p是其雙親的右孩子或結(jié)點p是其雙親的左孩子但其雙親沒有右孩子，則返回空。（9）Retrieve(p)：求給定結(jié)點p中的數(shù)據(jù)元素的值。（10）Assign(p，d)：對二叉樹中給定結(jié)點p賦值為d。（11）InsertLeftChild(p,d)：在二叉樹中插入數(shù)據(jù)元素值為d的結(jié)點作為結(jié)點p的左孩子，若結(jié)點p原來有左子樹PL，則插入完成后PL作為新結(jié)點的左子樹。（12）InsertRightChild(p,d)：在二叉樹中插入數(shù)據(jù)元素值為d的結(jié)點作為結(jié)點p的右孩子，若結(jié)點p原來有右子樹PR，則插入完成后PR作為新結(jié)點的右子樹。（13）DeleteLeftChild(p)：刪除結(jié)點p的左子樹。（14）DeleteRightChild(p)：刪除結(jié)點p的右子樹。（15）PreOrderTravers（）：先序遍歷二叉樹。（16）InOrderTravers（）：中序遍歷二叉樹。（17）PostOrderTravers（）：后序遍歷二叉樹。（18）LevelOrderTravers（）：按層次順序遍歷二叉樹。二叉樹的存儲結(jié)構(gòu)

數(shù)組表示法:

二叉樹的數(shù)組表示就是采用一組連續(xù)存儲空間存儲二叉樹結(jié)點中的數(shù)據(jù)元素，利用數(shù)組下標(biāo)來反映數(shù)據(jù)元素之間的關(guān)系。對具有n個結(jié)點的完全二叉樹按從上到下、自左向右的順序連續(xù)給結(jié)點編號0、1、2、…、n-1。按此結(jié)點編號將二叉樹中各結(jié)點中的數(shù)據(jù)元素順序地存放于一個一維數(shù)組中，首先將根結(jié)點中的數(shù)據(jù)元素儲存在數(shù)組的0號位置；對于二叉樹中任一個結(jié)點，如果它的數(shù)據(jù)元素存儲在數(shù)組的第i個位置，就把它的左、右孩子結(jié)點中的數(shù)據(jù)元素分別存放在數(shù)組的第2*i+1個位置和第2*i+2個位置。這樣就得到了二叉樹的一種數(shù)組表示法。

采用這種方法表示一般的二叉樹時，空間利用效率低是一個主要的問題。當(dāng)被表示的二叉樹結(jié)構(gòu)很不完整時，在數(shù)組中就會出現(xiàn)很多空位置，因此空間浪費就變得非常大。

用這種方法表示二叉樹時，還有一個問題需要注意的是：必須處理結(jié)點不存在的情況。如果一個結(jié)點不存在，就必須在數(shù)組中相應(yīng)位置設(shè)置一個特殊標(biāo)志，指明在這個位置沒有結(jié)點。鏈表表示法:

在二叉樹的鏈表表示中，樹中的每一個元素用一個結(jié)點表示，結(jié)點一般包括三個域，其結(jié)構(gòu)如圖(a)所示。其中，Data域用于存放數(shù)據(jù)元素的信息；leftChild域用于存放指向其左孩子結(jié)點的指針；rightChild域用于存放指向其右孩子結(jié)點的指針。二叉樹的這種鏈表表示稱為二叉鏈表。

二叉樹的二叉鏈表表示，對于大多數(shù)的應(yīng)用來說是適合的。但是，在二叉鏈表中要想找出一個結(jié)點的雙親是比較困難的，必須通過二叉樹的遍歷才能實現(xiàn)。如果在應(yīng)用中需要方便地找到任何一個結(jié)點的雙親，可以在結(jié)點中增加一個Parent域來指向該結(jié)點的雙親，二叉樹的這種表示方法稱為三叉鏈表。二叉樹的二叉鏈表類聲明:二叉鏈表中結(jié)點的類定義如下：template<classType>classBinaryTree;template<classType>ClassBinTreeNode{friendclassBinaryTree<Type>;private:BinTreeNode<Type>*leftChild,*rightChild;//結(jié)點的左、右孩子指針域

Typedata;//結(jié)點的數(shù)據(jù)域public:BinTreeNode():leftChild(NULL),rightChild(NULL){}//構(gòu)造函數(shù)，構(gòu)造一個空結(jié)點

BinTreeNode(Typed,BinTreeNode<Type>*lp=NULL,BinTreeNode<Type>*rp=NULL):data(d),leftChild(lp),rightChild(rp){}//構(gòu)造函數(shù)，構(gòu)造一個數(shù)據(jù)域的值為d的結(jié)點

Type&GetData()const{returndata;}BinTreeNode<Type>*GetLeftChild()const{returnleftChild;}BinTreeNode<Type>*GetRightChild()const{returnrightChild;}voidSetData(constType&d){data=d;}voidSetLeftChild(BinTreeNode<Type>*p){leftChild=p;}voidSetRightChild(BinTreeNode<Type>*p){rightChild=p;}};二叉鏈表類定義如下：template<classType>classBinaryTree{private:BinTreeNode<Type>*root;//二叉樹根結(jié)點指針

BinTreeNode<Type>*Parent(BinTreeNode<Type>*start,BinTreeNode<Type>*p);

voiddestroy(BinTreeNode<Type>*p);//刪除以p為根的二叉樹

voidPreOrder(BinTreeNode<Type>*r);//前序遍歷以r為根的二叉樹

voidInOrderTravers(BinTreeNode<Type>*r);//中序遍歷以r為根的二叉樹

voidPostOrderTravers(BinTreeNode<Type>*r);//后序遍歷以r為根的二叉樹public:BinaryTree():root(NULL){}//構(gòu)造函數(shù)

BinaryTree(Typed):root(d){}//構(gòu)造函數(shù)

virtual~BinaryTree(){destroy(root);}//析構(gòu)函數(shù)

virtualintIsEmpty(){returnroot==NULL?1:0;}//判斷二叉樹是否為空

BinTreeNode<Type>*Root(){returnroot;}CreateRoot(Typedata){root=newBinTreeNode<Type>(d);}virtualBinTreeNode<Type>*Parent(BinTreeNode<Type>*p){returnParent(root,p);}//找p的雙親virtualBinTreeNode<Type>*LeftChild(BinTreeNode<Type>*p){returnp==NULL?NULL:p→GetLeftChild();}virtualBinTreeNode<Type>*RightChild(BinTreeNode<Type>*p){returnp==NULL?NULL:p→GetRightChild();}BinTreeNode<Type>*LeftSibling(BinTreeNode<Type>*p);BinTreeNode<Type>*RightSibling(BinTreeNode<Type>*p);TypeRetrieve(BinTreeNode<Type>*p){returnp→GetData();}Assign(BinTreeNode<Type>*p,Typed);{p→SetData(d);}InsertLeftChild(BinTreeNode<Type>*p,Typed);InsertRightChild(BinTreeNode<Type>*p,Typed);DeleteLeftChild(BinTreeNode<Type>*p);{destroy(p→GetLeftChild());}DeleteRightChild(BinTreeNode<Type>*p);{destroy(p→GetRightChild());}PreOrder(){PreOrder(root);}InOrderTravers(){InOrderTravers(root)};PostOrderTravers(){PostOrderTravers(root)};LevelOrderTravers();}部分成員函數(shù)的實現(xiàn):template<classType>voidBinaryTree<Type>::destroy(BinTreeNode<Type>*p){

if(p!=NULL){destroy(p→GetLeftChild());destroy(p→GetRightChild());deletep;}}template<classType>BinTreeNode<Type>*BinaryTree<Type>::Parent(BinTreeNode<Type>*r,BinTreeNode<Type>*p){BinTreeNode<Type>*q;

if(r==NULL)return

NULL;

if(r→GetLeftChild()==p||r→GetRightChild()==p)returnr;

if((q=Parent(r→GetLeftChild(),p))!=NULL)returnq;

else

returnParent(r→GetRightChild(),p);}template<classType>BinTreeNode<Type>*BinaryTree<Type>::LeftSibling(BinTreeNode<Type>*p){BinTreeNode<Type>*q;q=Parent(root,p);

if((q==NULL)||(p==q→GetLeftChild()))

return

NULL;

else

returnq→GetLeftChild();}template<classType>BinTreeNode<Type>*BinaryTree<Type>::RightSibling(BinTreeNode<Type>*p){BinTreeNode<Type>*q;q=Parent(root,p);

if((q==NULL)||(p==q→GetRightChild()))

return

NULL;

else

returnq→GetRightChild();}template<classType>BinTreeNode<Type>::InsertLeftChild(BinTreeNode<Type>*p,Typed){BinTreeNode<Type>*q=newBinTreeNode<Type>(d);q→SetLeftChild(p→GetRightChild());p→SetLefttChild(q);}template<classType>BinTreeNode<Type>::InsertRightChild(BinTreeNode<Type>*p,Typed){BinTreeNode<Type>*q=newBinTreeNode<Type>(d);q→SetRightChild(p→GetRightChild());p→SetRightChild(q);}遍歷二叉樹:

二叉樹的遍歷是指按照某種順序訪問二叉樹中的每個結(jié)點，并使每個結(jié)點被訪問一次且只被訪問一次。在遍歷過程中，對結(jié)點的訪問具有普遍的含義，可以是輸出各結(jié)點的數(shù)據(jù)元素信息，也可以是對結(jié)點作其他處理。另外，通過一次完整的遍歷，可使二叉樹中結(jié)點信息由非線性排列變?yōu)槟撤N意義上的線性排列。也就是說，遍歷操作使非線性結(jié)構(gòu)線性化。前序遍歷:前序遍歷(PreorderTraversal)的遞歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）訪問根結(jié)點；（2）前序遍歷根結(jié)點的左子樹；（3）前序遍歷根結(jié)點的右子樹。

對上圖所示的二叉樹，進(jìn)行前序遍歷，按訪問結(jié)點的先后順序?qū)⒔Y(jié)點的數(shù)據(jù)元素排列起來，得到二叉樹的前序序列為：A、B、D、E、G、H、C、F、I。前序遍歷二叉樹的遞歸算法如下：template<classType>voidBinaryTree<Type>::PreOrder(BinTreeNode<Type>*r){

if(r!=NULL){

cout<<r→GetData()<<endl;PreOrder(r→GetLeftChild());PreOrder(r→GetRightChild());}}中序遍歷:中序遍歷(InorderTraversal)的遞歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）中序遍歷根結(jié)點的左子樹；（2）訪問根結(jié)點；（3）中序遍歷根結(jié)點的右子樹。對上圖所示的二叉樹，進(jìn)行中序遍歷，按訪問結(jié)點的先后順序?qū)⒔Y(jié)點的數(shù)據(jù)元素排列起來，可得到二叉樹的中序序列為：D、B、G、E、H、A、C、F、I。中序遍歷二叉樹的遞歸算法如下：template<classType>voidBinaryTree<Type>::InOrder(BinTreeNode<Type>*r){

if(r!=NULL){InOrder(r→GetLeftChild());

cout<<r→GetData()<<endl;InOrder(r→GetRightChild());}}后序遍歷:后序遍歷(PostorderTraversal)的遞歸定義為：若二叉樹為空，遍歷結(jié)束。否則，（1）后序遍歷根結(jié)點的左子樹；（2）后序遍歷根結(jié)點的右子樹；（3）訪問根結(jié)點。對上圖所示的二叉樹，進(jìn)行后序遍歷，按訪問結(jié)點的先后順序?qū)⒔Y(jié)點的數(shù)據(jù)元素排列起來，可得到二叉樹的后序序列為：D、G、H、E、B、I、F、C、A。后序遍歷二叉樹的遞歸算法如下：template<classType>voidBinaryTree<Type>::PostOrder(BinTreeNode<Type>*r){

if(bt!=NULL){PostOrder(r→GetLeftChild());PostOrder(r→GetRightChild());}

cout<<r→GetData()<<endl;}層序遍歷:所謂層序遍歷(LevelorderTraversal)二叉樹，是指從二叉樹的第一層(根結(jié)點)開始，自上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。對于右圖所示的二叉樹，按層序遍歷方式進(jìn)行遍歷所得到的結(jié)點序列為：A、B、C、D、E、F、G、H、I。在進(jìn)行層序遍歷時，需要設(shè)置一個隊列結(jié)構(gòu)，并按下述步驟層序遍歷二叉樹：(1)初始化隊列，并將根結(jié)點入隊。(2)當(dāng)隊列非空時，取出隊頭結(jié)點p，轉(zhuǎn)步驟3；如果隊列為空，則結(jié)束遍歷。(3)訪問結(jié)點p；如果該結(jié)點有左孩子，則將其左孩子入隊列；如果該結(jié)點有右孩子，則將其右孩子入隊列。(4)重復(fù)步驟(2)、(3)，直到隊列為空。下面給出層序遍歷算法的C++描述，其中二叉樹的存儲結(jié)構(gòu)仍為二叉鏈表。在此還用到了前面定義的隊列Queue。template<classType>voidBinaryTree<Type>::LevelOrder(){linkqueue<BinTreeNode*>q;BinTreeNode*p=root;

if(p)q.EnQueue(p);

While(!q.IsEmpty()){p=*q.DeQueue();

cout<<p.GetData()<<endl;

if(p→GetLeftChild())q.EnQueue(p→GetLeftChild());

if(p→GetRightChild())q.EnQueue(p→GetRightChild());}}

在遍歷二叉樹時，無論采用前面所講的哪一種方式進(jìn)行遍歷，其基本操作都是訪問結(jié)點。所以，對具有n個結(jié)點的二叉樹，遍歷操作的時間復(fù)雜度均為O(n)。在前序、中序和后序遍歷的過程中，遞歸時棧所需要的空間最多等于樹的深度h乘以每個棧元素所需空間，在最壞的情況下，二叉樹的深度等于結(jié)點數(shù)目，所以空間復(fù)雜度為O(n)。在層序遍歷時，所設(shè)置隊列的大小顯然小于二叉樹中結(jié)點的個數(shù)，所以空間復(fù)雜度也為O(n)。利用二叉樹的遍歷可以實現(xiàn)許多關(guān)于二叉樹的運算，例如計算二叉樹的結(jié)點數(shù)目、計算二叉樹的高度、二叉樹的復(fù)制等。線索二叉樹

線索二叉樹的定義:

一棵具有n個結(jié)點的二叉樹就會發(fā)現(xiàn)，當(dāng)它采用二叉鏈表作存儲結(jié)構(gòu)時，二叉鏈表中的所有結(jié)點共有n+1個空指針域。因此，可以設(shè)法利用這些空指針域來存放結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點的指針信息。在此，可以作這樣的規(guī)定：當(dāng)某結(jié)點的左指針域為空時，令其指向依某種方式遍歷時所得到的該結(jié)點的前驅(qū)結(jié)點，否則指向它的左孩子；當(dāng)某結(jié)點的右指針域為空時，令其指向依某種方式遍歷時所得到的該結(jié)點的后繼結(jié)點，否則指向它的右孩子。在每個結(jié)點中增設(shè)兩個標(biāo)志位leftTag和rightTag，令：當(dāng)leftTag=0時,

leftChild為左孩子指針當(dāng)leftTag=1時, leftChild為前驅(qū)線索當(dāng)rightTag=0時, rightChild為右孩子指針當(dāng)rightTag=1時, rightChild為后繼指針

為算法設(shè)計方便起見，通常在線索鏈表中添加一個與二叉樹中結(jié)點的類型相同的頭結(jié)點，令頭結(jié)點的數(shù)據(jù)域為空；其leftChild指向二叉樹的根結(jié)點，但當(dāng)二叉樹為空時，leftChild指向頭結(jié)點本身；其rightChild域指向以某種方式遍歷二叉樹時第一個訪問的結(jié)點，而當(dāng)二叉樹為空時，rightChild域指向該結(jié)點本身。并令原來指向二叉樹根結(jié)點的頭指針指向該頭結(jié)點。以某種方式遍歷二叉樹時第一個被訪問結(jié)點的左指針和最后一個被訪問結(jié)點的右指針如果是線索，也指向頭結(jié)點。這樣一來，就相當(dāng)于為二叉樹建立了帶頭結(jié)點的雙向循環(huán)鏈表。線索二叉樹的類定義:線索二叉樹的結(jié)點類template<classType>classThreadBinTreeNode{friend

classThreadBinTree;//線索二叉樹的類friend

classThreadPreorderTree;//前序線索二叉樹的類friend

classThreadInorderTree;//中序線索二叉樹的類friend

classThreadPostorderTree;//后序線索二叉樹的類Public:ThreadBinTreeNode(constTyped)://構(gòu)造函數(shù)

data(d),leftChild(NULL),rightChild(NULL),leftTag(0),rightTag(0){}Type&GetData()const{returndata;}ThreadBinTreeNode<Type>*GetLeftChild()const{returnleftChild;}ThreadBinTreeNode<Type>*GetRightChild()const{returnrightChild;}

voidSetData(constType&d){data=d;}

voidSetLeftChild(ThreadBinTreeNode<Type>*p){leftChild=p;}

voidSetRightChild(ThreadBinTreeNode<Type>*p){rightChild=p;}private:

intleftTag,rightTag;//左右標(biāo)志位

ThreadBinTreeNode<Type>*leftChild,*rightChild;//線索或孩子指針

Typedata;//結(jié)點數(shù)據(jù)};線索二叉樹的類template<classType>classThreadBinTreeBinTree{friend

classThreadPreorderTree;//前序線索二叉樹的類friend

classThreadInorderTree;//中序線索二叉樹的類friend

classThreadPostorderTree;//后序線索二叉樹的類public:ThreadBinTree():root(NULL){}private:ThreadBinTreeNode<Type>*root;};3．前序線索二叉樹的類template<classType>classThreadPreorderTree{private:ThreadBinTree<Type>&T;//線索二叉樹

ThreadBinTreeNode<Type>*current;//當(dāng)前結(jié)點指針

voidpreThread(ThreadBinTreeNode<Type>*r,ThreadBinTreeNode<Type>*pre);//前序線索化以r為根的二叉樹，pre為前序序歷中第一個結(jié)點的前驅(qū)public:ThreadPreorderTree(ThreadBinTree<Type>&Tree):T(Tree){current=T.root}ThreadBinTreeNode<Type>*ThreadPreOrderFirst();//當(dāng)前結(jié)點指針指向前序遍歷的第一個結(jié)點

ThreadBinTreeNode<Type>*ThreadPreOrderLast();//當(dāng)前結(jié)點指針指向前序遍歷的最后一個結(jié)點

ThreadBinTreeNode<Type>*ThreadPreOrderNext();//當(dāng)前結(jié)點指針指向其后繼結(jié)點

ThreadBinTreeNode<Type>*ThreadPreOrderPrior();//當(dāng)前結(jié)點指針指向其前驅(qū)結(jié)點

voidPreorder();//前序遍歷

voidCreatePreThread();//建立前序線索二叉樹};4．中序線索二叉樹的類template<classType>classThreadInorderTree{private:ThreadBinTree<Type>&T;//線索二叉樹

ThreadBinTreeNode<Type>*current;//當(dāng)前結(jié)點指針

voidinThread(ThreadBinTreeNode<Type>*r,ThreadBinTreeNode<Type>*pre);//中序線索化以r為根的二叉樹，pre為中序序歷中第一個結(jié)點的前驅(qū)public:ThreadInorderTree(ThreadBinTree<Type>&Tree):T(Tree){current=T.root}ThreadBinTreeNode<Type>*ThreadInOrderFirst();//當(dāng)前結(jié)點指針指向中序遍歷的第一個結(jié)點

ThreadBinTreeNode<Type>*ThreadInOrderLast();//當(dāng)前結(jié)點指針指向中序遍歷的最后一個結(jié)點

ThreadBinTreeNode<Type>*ThreadInOrderNext();//當(dāng)前結(jié)點指針指向其后繼結(jié)點

ThreadBinTreeNode<Type>*ThreadInOrderPrior();//當(dāng)前結(jié)點指針指向其前驅(qū)結(jié)點

voidInorder();//中序遍歷

voidCreateInThread();//建立中序線索二叉樹};5．后序線索二叉樹的類template<classType>classThreadPostorderTree{private:ThreadBinTree<Type>&T;//線索二叉樹

ThreadBinTreeNode<Type>*current;//當(dāng)前結(jié)點指針

voidpostThread(ThreadBinTreeNode<Type>*r,ThreadBinTreeNode<Type>*pre);//后序線索化以r為根的二叉樹，pre為后序序歷中第一個結(jié)點的前驅(qū)public:ThreadPostorderTree(ThreadBinTree<Type>&Tree):T(Tree){current=T.root}ThreadBinTreeNode<Type>*ThreadPostOrderFirst();//當(dāng)前結(jié)點指針指向后序遍歷的第一個結(jié)點

ThreadBinTreeNode<Type>*ThreadPostOrderLast();//當(dāng)前結(jié)點指針指向后序遍歷的最后一個結(jié)點

ThreadBinTreeNode<Type>*ThreadPostOrderNext();//當(dāng)前結(jié)點指針指向其后繼結(jié)點

ThreadBinTreeNode<Type>*ThreadPostOrderPrior();//當(dāng)前結(jié)點指針指向其前驅(qū)結(jié)點

voidPostorder();//后序遍歷

voidCreatePostThread();//建立后序線索二叉樹};中序線索二叉樹:

下面以中序線索二義樹為例，討論線索二叉樹的建立、線索二叉樹的遍歷以及在線索二叉樹中查找前驅(qū)結(jié)點、查找后繼結(jié)點、插入結(jié)點和刪除結(jié)點等操作的實現(xiàn)算法。1．建立中序線索二叉樹

建立線索二叉樹，或者說對二叉樹線索化，實質(zhì)上就是遍歷一棵二叉樹。在遍歷的過程中檢查當(dāng)前結(jié)點的左、右指針域是否為空。如果為空，將它們改為指向前驅(qū)結(jié)點或后繼結(jié)點的線索。另外，在對一棵二叉樹加線索時，必須首先申請一個頭結(jié)點，并使頭結(jié)點的leftchild指向二叉樹的根結(jié)點。對二叉樹線索化后，還須建立最后一個結(jié)點到頭結(jié)點的線索；并使頭結(jié)點的rightchild指向第一個結(jié)點。

template<classType>voidThreadBinTree<Type>::InThread(ThreadBinTreeNode<Type>*r,ThreadBinTreeNode<Type>*pre){//利用中序遍歷線索化以r為根的二叉樹，pre為中序序歷中第一個結(jié)點的前驅(qū)

if(r!=NULL){InThread(r→GetLeftChild(),pre);//中序線索化r的左子樹

if(r→GetLeftChild()==NULL){r→SetLeftChild(pre);r→leftTag=1;}//建立前驅(qū)線索

if(pre→GetRightChild()==NULL){pre→SetRightChild(r);pre→rightTag=1;}//建立后繼線索

pre=r;InThread(r→GetRightChild(),pre);//中序線索化r的右子樹

}}template<classType>voidThreadBinTree<Type>::CreateInThread(){//建立中序線索二叉樹

ThreadBinTreeNode<Type>*pre;root=newThreadBinTreeNode<Type>;//建立頭結(jié)點

root→leftTag=1;root→rightTag=1;

if(this==NULL){root→SetLeftChild(root);root→SetRightChild(root);}//二叉樹為空樹

else{current==this;root→SetLeftChild(this);root→leftThread=0;pre=root;InThread(current,pre);//中序線索化

pre→SetRightChild(root);//最后一個結(jié)點的后續(xù)線索指向頭結(jié)點

pre→rightTag=1;root→SetRightChild(ThreadInOrderFirst());//頭結(jié)點的rightChild指向中序序列的第一個結(jié)點

}}2．中序線索化二叉樹中的部分成員函數(shù)的實現(xiàn)在中序線索樹中尋找中序序列中的最后一個結(jié)點的算法如下：template<classType>ThreadBinTreeNode<Type>*ThreadInorderTree<Type>::ThreadInOrderLast(){if(T.root→leftTag==0){current=T.root→GetLeftChild();while(current→rightTag==0)current=current→GetRightChild();returncurrent;}elsereturnNULL;}中序線索樹中尋找當(dāng)前結(jié)點CURRENT的中序后繼結(jié)點的算法如下：template<classType>ThreadBinTreeNode<Type>*ThreadInorderTree<Type>::ThreadInOrderNext(){//在線索樹中尋找CURRENT的中序后繼

ThreadBinTreeNode<Type>*p=current→GetRightChild();

if(current→rightTag==0)//CURRENT有右孩子

while(p→leftTag==0)p=p→GetLeftChild();current=p;

if(current==T.root)return

NULL;

else

returncurrent;}

在中序線索樹中進(jìn)行中序遍歷，可以通過從第一個結(jié)點開始依次找當(dāng)前結(jié)點的后繼來完成。算法的描述如下：template<classType>void

ThreadInorderTree<Type>::Inorder(){ThreadBinTreeNode<Type>*p;

for(p=T.root→GetLeftChild();p!=NULL;p=ThreadInOrderNext())

cout<<p.GetData<<endl;}3.在中序線索二叉樹上插入結(jié)點在中序線索二叉樹上插入結(jié)點有兩種方法：一種是將新結(jié)點插入到二叉樹中作為某結(jié)點的左孩子結(jié)點；另一種方法是將新結(jié)點插入到二叉樹中作為某結(jié)點的右孩子結(jié)點。在此討論后一種情況。假設(shè)指針p指向線索二叉樹中的某一結(jié)點，指針x指向要插入的新結(jié)點，新結(jié)點x將插入到二叉樹中作為結(jié)點p的右孩子。此時，將有兩種情況第一種情況：結(jié)點p沒有右孩子，則插入過程很簡單，下圖(a)、(b)給出了這種情況下插入前后二叉樹的兩種形態(tài)。這時結(jié)點P原來的后繼結(jié)點變?yōu)榻Y(jié)點x的后繼結(jié)點，結(jié)點p為結(jié)點x的前驅(qū)結(jié)點，結(jié)點x成為結(jié)點p的右孩子。第二種情況：若結(jié)點P有右子樹，結(jié)點x插入后，令結(jié)點p原來的右子樹成為結(jié)點x的右子樹，x為P的右孩子。此時，結(jié)點p成為結(jié)點x的前驅(qū)結(jié)點，根據(jù)中序線索二叉樹的定義，這時還需修改結(jié)點p原來右子樹中最左下結(jié)點的左指針，使它由原來指向結(jié)點p改為指向結(jié)點x。下圖(c)、(d)給出了這種情況下插入前后二叉樹的兩種形態(tài)。插入結(jié)點的算法如下：template<classtype>voidThreadBinTree<type>::insertRight(ThreadBinTreeNode<type>*p,ThreadBinTreeNode<type>*x){ThreadBinTreeNode<type>*qx→SetRightChild(p.GetRightChild());x→rightTag=p→rightTag;x→SetLeftChild(p);x→leftTag=1;p→SetRightChild(x);p→rightTag=0;

if(x→rightTag==0){q=x→GetRightChild();q=ThreadInOrderFirst(q);q→SetLeftChild(x);}}二叉樹的應(yīng)用

二叉樹結(jié)構(gòu)在實際問題中有著廣泛的應(yīng)用。二叉排序樹、堆排序、哈夫曼樹等是最典型的二叉樹應(yīng)用。作為二叉樹的應(yīng)用例子，本節(jié)介紹堆和哈夫曼樹(或稱最優(yōu)二叉樹)以及哈夫曼樹在編碼問題中的應(yīng)用。1．堆的定義設(shè)有n個數(shù)據(jù)元素的關(guān)鍵字為（k0、k1、…、kn-1），如果它們滿足以下的關(guān)系：ki<=k2i+1且ki<=k2i+2（或ki>=k2i+1且ki>=k2i+2）（i=0、1、…、(n-2)/2）則稱之為堆(Heap)。如果將此數(shù)據(jù)元素序列用一維數(shù)組存儲，并將此數(shù)組對應(yīng)一棵完全二叉樹，則堆的含義可以理解為：在完全二叉樹中任何非終端結(jié)點的關(guān)鍵字均不大于（或不小于）其左、右孩子結(jié)點的關(guān)鍵字。堆

右圖(b)、(c)分別給出了最小堆和最大堆的例子，前者任一非終端結(jié)點的關(guān)鍵字均小于或等于它的左、右孩子的關(guān)鍵字，此時位于堆頂(即完全二叉樹的根結(jié)點位置)的結(jié)點的關(guān)鍵字是整個序列中最小的，所以稱它為最小堆；后者任一非終端結(jié)點的關(guān)鍵字均大于或等于它的左、右孩子的關(guān)鍵字，此時位于堆頂?shù)慕Y(jié)點的關(guān)鍵字是整個序列中最大的，所以稱它為最大堆。最小堆的類定義:template<classType>classMinHeap{public:MinHeap(intmaxSize);//構(gòu)造函數(shù)，建立空堆

MinHeap(Typea[],intn);//構(gòu)造函數(shù)，以數(shù)組a[]的值建立堆

~MinHeap(){delete[]heapArr;}//析構(gòu)函數(shù)

intInsert(constType&d);//在堆中插入元素dTypeDeleteTop();//刪除堆頂元素

TypeGetTop()const//取堆頂元素值

{returnheapArr[0];}

intIsEmpty()const//判斷堆是否為空。空堆返回1，否則返回0{returnheapCurrentSize==0;}intIsFull()const//判斷堆是否為滿。滿堆返回1，否則返回0{returnheapCurrentSize==heapMaxSize;}

intSizeofHeap()const//取堆的當(dāng)前元素數(shù)目

{returnheapCurrentSize;}

voidSetEmpty(){heapCurrentSize=0;}//置堆為一個空堆private:Type*heapArr;//存放堆中數(shù)據(jù)元素的數(shù)組

intheapCurrentSize;//堆中當(dāng)前數(shù)據(jù)元素數(shù)目

intheapMaxSize;//堆中數(shù)據(jù)元素的最大數(shù)目

voidFilterDown(intp);//向下調(diào)整使以結(jié)點p為根的子樹成為堆

voidFilterUp(intp);//向上調(diào)整使結(jié)點p所在的子樹成為堆}2．堆的構(gòu)造在最小堆的類定義中，有兩個構(gòu)造函數(shù)用于建立堆，第一個構(gòu)造函數(shù)建立一個空間大小maxSize的空堆；另一個構(gòu)造函數(shù)是通過復(fù)制一個記錄數(shù)組并對其進(jìn)行調(diào)整形成一個堆。下面分別給出這兩個構(gòu)造函數(shù)的定義。template<classType>MinHeap<Type>::MinHeap(intmaxSize){//根據(jù)給定大小maxSize,建立空堆

if(maxSize<=0){cerr<<”堆的大小不能小于1”<<endl;exit(1);}heapMaxSize=maxSize;//確定堆的最大空間

heapArr=newType[heapMaxSize];//創(chuàng)建堆空間

heapCurrentSize=0;//初始化}template<classType>MinHeap<Type>::MinHeap(Typea[],intn){//根據(jù)數(shù)組a[]中的數(shù)據(jù),建立堆,n為數(shù)組的大小

if(n<=0){cerr<<”堆的大小不能小于1”<<endl;exit(1);}heapMaxSize=n;//確定堆的最大空間

heapArr=newType[heapMaxSize];//創(chuàng)建堆空間

heapArr=a;//數(shù)組傳送

heapCurrentSize=n;//當(dāng)前堆大小

inti=(heapCurrentSize-2)/2;//找最后一個分支結(jié)點的序號

while(i>=0){//自下而上逐步調(diào)整形成堆

FilterDown(i);//從i開始到heapCurrentSize為止進(jìn)行調(diào)整

i--;}}

調(diào)整算法FilterDown要求將以分支結(jié)點i為根的子樹調(diào)整為最小堆，其基本思想是：從結(jié)點i開始向下調(diào)整，先比較結(jié)點i左孩子結(jié)點和右孩子結(jié)點的關(guān)鍵字大小，如果結(jié)點i左孩子結(jié)點的關(guān)鍵字小于右孩子結(jié)點的關(guān)鍵字，則沿結(jié)點i的左分支進(jìn)行調(diào)整；否則沿結(jié)點i的右分支進(jìn)行調(diào)整，在算法中用j指示關(guān)鍵字值較小的孩子結(jié)點。然后結(jié)點i和結(jié)點j進(jìn)行關(guān)鍵字比較，若結(jié)點i的關(guān)鍵字大于結(jié)點j的關(guān)鍵字，則兩結(jié)點對調(diào)位置，相當(dāng)于把關(guān)鍵字小的結(jié)點上浮。再令i＝j(luò)，j＝2*j十l，繼續(xù)向下一層進(jìn)行比較；若結(jié)點i的關(guān)鍵字不大于結(jié)點j的關(guān)鍵字或結(jié)點i沒有孩子時調(diào)整結(jié)束。向下調(diào)整算法的定義。template<classType>voidMinHeap<Type>::FilterDown(const

intstart){inti=start,j;Typetemp=heapArr[i];j=2*i+1;//j為i的左孩子

while(j<heapCurrentSize){

if(j<heapCurrentSize-1&&heapArr[j].key>heapArr[j+1].key)j++;//在左右孩子中選關(guān)鍵字較小者

if(temp.key<=heapArr[j].key)break;

else{heapArr[i]=heapArr[j];i=j;j=2*j+1;}}heapArr[i]=temp;}3．在堆中插入元素在堆的類定義中成員函數(shù)Insert()用于在堆中插入一個數(shù)據(jù)元素，在此規(guī)定數(shù)據(jù)元素總是插在已經(jīng)建成的最小堆后面，如下圖所示在堆中插入關(guān)鍵字為14的數(shù)據(jù)元素。顯然在堆中插入元素后可能破壞堆的性質(zhì)，所以還需要調(diào)用FilterUp()函數(shù)，進(jìn)行自下而上調(diào)整使之所在的子樹成為堆。成員函數(shù)Insert()的C++描述:template<classType>intMinHeap<Type>::Insert(constType&d){//在堆中插入新元素d

if(IsFull())//堆滿

{cout<<"堆已滿"<<endl;return0;}heapArr[heapCurrentSize]=d;//在堆尾插入數(shù)據(jù)元素dFilterUp(heapCurrentSize);//向上調(diào)整為堆

heapCurrentSize++;//堆元素數(shù)目加1

return1;}下面給出函數(shù)FilterUp()的C++描述template<classType>voidMinHeap<Type>::FilterUp(intp){//從p開始向上調(diào)整。使序列成為堆

intj=p,i;Typetemp=heapArr[j];i=(j-1)/2;//i是

j的雙親

while(j>0){

if(heapArr[i].key<=temp.key)break;

else{heapArr[j]=heapArr[i];j=i;i=(j-1)/2;}}heapArr[j]=temp;}4．在堆中刪除元素在堆的類定義中成員函數(shù)DeleteTop()用于刪除堆頂數(shù)據(jù)元素。在從堆中刪除堆頂元素后，一般把堆的最后一個元素移到堆頂，并將堆的當(dāng)前元素個數(shù)heapCurrentSize減1，最后需要調(diào)用FilterDown()函數(shù)從堆頂向下進(jìn)行調(diào)整。如圖6-20所示給出了在堆中刪除堆頂元素的過程。成員函數(shù)DeleteTop()的C++描述:template<classType>TypeMinHeap<Type>::DeleteTop(){

if(IsEmpty()){cout<<“堆已空

"<<endl;return

NULL;}Typetemp=heapArr[0];//取堆頂元素

heapA