數據結構 第6章 樹和森林

第六章樹和森林主要內容樹的概念二叉樹二叉樹的存儲結構遍歷二叉樹線索二叉樹二叉樹的應用樹的概念某家族的血統關系如下：張宇有四個孩子分別是：張山、張川、張星和張月；張山有二個孩子張冰和張雪；張星有三個孩子張雨、張云和張風；張云有兩個孩子張亮和張麗。

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

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

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

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

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

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

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

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

二叉樹的定義:

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

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

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

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

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

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

數組表示法:

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

采用這種方法表示一般的二叉樹時，空間利用效率低是一個主要的問題。當被表示的二叉樹結構很不完整時，在數組中就會出現很多空位置，因此空間浪費就變得非常大。

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

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

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

Typedata;//結點的數據域public:BinTreeNode():leftChild(NULL),rightChild(NULL){}//構造函數，構造一個空結點

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

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;//二叉樹根結點指針

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){}//構造函數

BinaryTree(Typed):root(d){}//構造函數

virtual~BinaryTree(){destroy(root);}//析構函數

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();}部分成員函數的實現: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);}遍歷二叉樹:

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

對上圖所示的二叉樹，進行前序遍歷，按訪問結點的先后順序將結點的數據元素排列起來，得到二叉樹的前序序列為：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)的遞歸定義為：若二叉樹為空，遍歷結束。否則，（1）中序遍歷根結點的左子樹；（2）訪問根結點；（3）中序遍歷根結點的右子樹。對上圖所示的二叉樹，進行中序遍歷，按訪問結點的先后順序將結點的數據元素排列起來，可得到二叉樹的中序序列為：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)的遞歸定義為：若二叉樹為空，遍歷結束。否則，（1）后序遍歷根結點的左子樹；（2）后序遍歷根結點的右子樹；（3）訪問根結點。對上圖所示的二叉樹，進行后序遍歷，按訪問結點的先后順序將結點的數據元素排列起來，可得到二叉樹的后序序列為：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)二叉樹，是指從二叉樹的第一層(根結點)開始，自上至下逐層遍歷，在同一層中，則按從左到右的順序對結點逐個訪問。對于右圖所示的二叉樹，按層序遍歷方式進行遍歷所得到的結點序列為：A、B、C、D、E、F、G、H、I。在進行層序遍歷時，需要設置一個隊列結構，并按下述步驟層序遍歷二叉樹：(1)初始化隊列，并將根結點入隊。(2)當隊列非空時，取出隊頭結點p，轉步驟3；如果隊列為空，則結束遍歷。(3)訪問結點p；如果該結點有左孩子，則將其左孩子入隊列；如果該結點有右孩子，則將其右孩子入隊列。(4)重復步驟(2)、(3)，直到隊列為空。下面給出層序遍歷算法的C++描述，其中二叉樹的存儲結構仍為二叉鏈表。在此還用到了前面定義的隊列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());}}

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

線索二叉樹的定義:

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

leftChild為左孩子指針當leftTag=1時, leftChild為前驅線索當rightTag=0時, rightChild為右孩子指針當rightTag=1時, rightChild為后繼指針

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

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

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

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

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

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;//左右標志位

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

Typedata;//結點數據};線索二叉樹的類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;//當前結點指針

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

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

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

ThreadBinTreeNode<Type>*ThreadPreOrderPrior();//當前結點指針指向其前驅結點

voidPreorder();//前序遍歷

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

ThreadBinTreeNode<Type>*current;//當前結點指針

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

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

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

ThreadBinTreeNode<Type>*ThreadInOrderPrior();//當前結點指針指向其前驅結點

voidInorder();//中序遍歷

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

ThreadBinTreeNode<Type>*current;//當前結點指針

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

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

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

ThreadBinTreeNode<Type>*ThreadPostOrderPrior();//當前結點指針指向其前驅結點

voidPostorder();//后序遍歷

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

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

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

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

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

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

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>;//建立頭結點

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);//最后一個結點的后續(xù)線索指向頭結點

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

}}2．中序線索化二叉樹中的部分成員函數的實現在中序線索樹中尋找中序序列中的最后一個結點的算法如下：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;}中序線索樹中尋找當前結點CURRENT的中序后繼結點的算法如下：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;}

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

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

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

cout<<p.GetData<<endl;}3.在中序線索二叉樹上插入結點在中序線索二叉樹上插入結點有兩種方法：一種是將新結點插入到二叉樹中作為某結點的左孩子結點；另一種方法是將新結點插入到二叉樹中作為某結點的右孩子結點。在此討論后一種情況。假設指針p指向線索二叉樹中的某一結點，指針x指向要插入的新結點，新結點x將插入到二叉樹中作為結點p的右孩子。此時，將有兩種情況第一種情況：結點p沒有右孩子，則插入過程很簡單，下圖(a)、(b)給出了這種情況下插入前后二叉樹的兩種形態(tài)。這時結點P原來的后繼結點變?yōu)榻Y點x的后繼結點，結點p為結點x的前驅結點，結點x成為結點p的右孩子。第二種情況：若結點P有右子樹，結點x插入后，令結點p原來的右子樹成為結點x的右子樹，x為P的右孩子。此時，結點p成為結點x的前驅結點，根據中序線索二叉樹的定義，這時還需修改結點p原來右子樹中最左下結點的左指針，使它由原來指向結點p改為指向結點x。下圖(c)、(d)給出了這種情況下插入前后二叉樹的兩種形態(tài)。插入結點的算法如下：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);}}二叉樹的應用

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

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

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

~MinHeap(){delete[]heapArr;}//析構函數

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

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

{returnheapArr[0];}

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

intSizeofHeap()const//取堆的當前元素數目

{returnheapCurrentSize;}

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

intheapCurrentSize;//堆中當前數據元素數目

intheapMaxSize;//堆中數據元素的最大數目

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

voidFilterUp(intp);//向上調整使結點p所在的子樹成為堆}2．堆的構造在最小堆的類定義中，有兩個構造函數用于建立堆，第一個構造函數建立一個空間大小maxSize的空堆；另一個構造函數是通過復制一個記錄數組并對其進行調整形成一個堆。下面分別給出這兩個構造函數的定義。template<classType>MinHeap<Type>::MinHeap(intmaxSize){//根據給定大小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){//根據數組a[]中的數據,建立堆,n為數組的大小

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

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

heapArr=a;//數組傳送

heapCurrentSize=n;//當前堆大小

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

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

FilterDown(i);//從i開始到heapCurrentSize為止進行調整

i--;}}

調整算法FilterDown要求將以分支結點i為根的子樹調整為最小堆，其基本思想是：從結點i開始向下調整，先比較結點i左孩子結點和右孩子結點的關鍵字大小，如果結點i左孩子結點的關鍵字小于右孩子結點的關鍵字，則沿結點i的左分支進行調整；否則沿結點i的右分支進行調整，在算法中用j指示關鍵字值較小的孩子結點。然后結點i和結點j進行關鍵字比較，若結點i的關鍵字大于結點j的關鍵字，則兩結點對調位置，相當于把關鍵字小的結點上浮。再令i＝j，j＝2*j十l，繼續(xù)向下一層進行比較；若結點i的關鍵字不大于結點j的關鍵字或結點i沒有孩子時調整結束。向下調整算法的定義。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++;//在左右孩子中選關鍵字較小者

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

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

if(IsFull())//堆滿

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

heapCurrentSize++;//堆元素數目加1

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

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．在堆中刪除元素在堆的類定義中成員函數DeleteTop()用于刪除堆頂數據元素。在從堆中刪除堆頂元素后，一般把堆的最后一個元素移到堆頂，并將堆的當前元素個數heapCurrentSize減1，最后需要調用FilterDown()函數從堆頂向下進行調整。如圖6-20所示給出了在堆中刪除堆頂元素的過程。成員函數DeleteTop()的C++描述:template<classType>TypeMinHeap<Type>::DeleteTop(){

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

"<<endl;return

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

heapA