《數(shù)據(jù)結(jié)構(gòu)-C語言描述》課件第6章

第6章樹

6.1樹的基本概念6.2二叉樹6.3樹和森林6.4*堆和優(yōu)先權(quán)隊列6.5哈夫曼樹和哈夫曼編碼6.6*并查集和等價關(guān)系習(xí)題66.1樹的基本概念6.1.1樹的定義層次結(jié)構(gòu)的數(shù)據(jù)在現(xiàn)實世界中大量存在。例如，一個國家包括若干省，一個省有若干市，每個市管轄若干個縣、區(qū)，這就存在層次關(guān)系，又如，書的內(nèi)容可以分成章節(jié)，章節(jié)編號也是層次的，所有上級和下級，整體和部分、祖先和后裔的關(guān)系都是層次關(guān)系的例子。許多應(yīng)用程序都是用來處理層次數(shù)據(jù)(hierarchicaldata)或譜系數(shù)據(jù)(genealogicaldata)的。

圖6－1描述了歐洲部分語言的譜系關(guān)系，它是一個后裔圖，圖中使用的描述樹形結(jié)構(gòu)數(shù)據(jù)的形式為倒置的樹形表示法。在前幾章中，我們學(xué)習(xí)了多種線性數(shù)據(jù)結(jié)構(gòu)，但是一般來講，這些數(shù)據(jù)結(jié)構(gòu)不適合表示如圖6－1所示的層次結(jié)構(gòu)的數(shù)據(jù)。為了表示這類層次結(jié)構(gòu)的數(shù)據(jù)，我們采用樹形數(shù)據(jù)結(jié)構(gòu)。在本章中我們將學(xué)習(xí)多種不同特性的樹形數(shù)據(jù)結(jié)構(gòu)，如一般樹、二叉樹、穿線二叉樹、堆和哈夫曼樹等。圖6－1西歐語言譜系圖

定義樹(tree)是包括n(n≥1)個元素的有限非空集合。其中，有一個特定的元素稱為根(root)，其余元素劃分成m(m≥0)個互不相交的子集。這m個子集每一個也都是樹，并稱之為該樹根的子樹(subtree)。上述定義是遞歸的，即用子樹來定義樹，在樹的定義中引用了樹的概念本身，這種定義方式被稱為遞歸定義。一個結(jié)點的樹是僅有根結(jié)點的樹，這時m＝0，這棵樹沒有子樹。n>1的樹可借助于少于n個結(jié)點的樹來定義，即一個根結(jié)點加上m棵子樹組成有n個結(jié)點的樹。從上面的定義可以看到，樹至少有一個結(jié)點，沒有空樹。樹結(jié)構(gòu)被稱為遞歸數(shù)據(jù)結(jié)構(gòu)(recursivedatastructures)。6.1.2基本術(shù)語關(guān)于樹結(jié)構(gòu)的討論中經(jīng)常使用家族譜系的慣用語。樹中元素常稱為結(jié)點(node)。樹根和子樹的根(如果有子樹)之間有一條邊。從某個結(jié)點沿著樹中的邊可到達另一個結(jié)點，則稱這兩個結(jié)點間存在一條路徑(path)。若一個結(jié)點有子樹，那么該結(jié)點稱為子樹根的雙親(parent)，子樹的根是該結(jié)點的孩子(child)。有相同雙親的結(jié)點互為兄弟(sibling)。一個結(jié)點的所有子樹上的任何結(jié)點都是該結(jié)點的后裔(descendent)。從根結(jié)點到某個結(jié)點的路徑上的所有結(jié)點都是該結(jié)點的祖先(ancestor)。

結(jié)點擁有的子樹數(shù)稱為該結(jié)點的度(degree)。度為零的結(jié)點稱為葉子(leaf)，其余結(jié)點稱為分支結(jié)點(branch)。樹中結(jié)點的最大的度稱為樹的度。根結(jié)點的層次(level)為1，其余結(jié)點的層次等于該結(jié)點的雙親結(jié)點的層次加1。樹中結(jié)點的最大層次稱為該樹的高度(height)。如果樹中結(jié)點的各子樹之間的次序不分先后，可以交換位置，這樣的樹稱為無序樹(non-ordered)。如果樹中結(jié)點的各棵子樹看成是從左到右有次序的，則稱該樹為有序樹(orderedtree)，那么從左到右，可分別稱這些子樹為第一子樹，第二子樹等等。

森林(forest)是樹的集合。果園(orchard)或稱有序森林(orderedforest)是有序樹的有序集合。在數(shù)據(jù)結(jié)構(gòu)中，森林和樹只有微小差別：刪去樹根，樹變成森林；對森林加上一個結(jié)點作樹根，森林即成為樹。但是需要注意的是：在上面樹和森林的定義中，樹不能為空樹，森林可以為空森林。

圖6－2(a)中，T1和T2是兩棵樹，組合在一起成為森林。圖6－2中，如果T1和T3是無序樹，則它們是相同的樹，否則是不相同的樹。在樹T1中，結(jié)點A、F和B是結(jié)點E的孩子，結(jié)點E是A、F和B的雙親，結(jié)點A、F和B互為兄弟。結(jié)點E、F、C和L都是結(jié)點N的祖先，F(xiàn)的后裔結(jié)點有C、L、M、N、D和J。結(jié)點E的度為3。根結(jié)點E的層次是1，F(xiàn)的層次為2，樹T1的高度為5，T2的高度為3。在樹T1中，G、M、N、J和B是葉子結(jié)點，其余結(jié)點是分支結(jié)點。圖6－2樹的例子

(a)樹T1和T2組成森林；(b)樹T36.2二叉樹

二叉樹是非常重要的樹形數(shù)據(jù)結(jié)構(gòu)。很多從實際問題中抽象出來的數(shù)據(jù)都是二叉樹形的，而且許多算法如果采用二叉樹形式解決則非常方便和高效。此外，以后我們將看到一般的樹或森林都可通過一個簡單的轉(zhuǎn)換得到與之相應(yīng)的二叉樹，從而為樹和森林的存儲及運算的實現(xiàn)提供了有效方法。

例如，設(shè)有序表為(21,25,28,33,36,43)，若要在表中查找元素36，通常的做法是從表中第一個元素開始，將待查元素與表中元素逐一比較進行查找，直到找到36為止。粗略地說，如果表中每個元素的查找概率是相等的，則平均起來，成功查找一個元素需要將該元素與表中一半元素作比較。如果將表中元素組成圖6－3所示的樹形結(jié)構(gòu)，情況就大為改觀。我們可以從根結(jié)點起，將各結(jié)點與待查元素比較，在查找成功的情況下，所需的最多的比較次數(shù)是從根到待查元素的路徑上遇到的結(jié)點數(shù)目。當(dāng)表的長度n很大時，使用圖6－3所示的樹形結(jié)構(gòu)組織表中數(shù)據(jù)，可以很大程度地減少查找所需的時間。為了查找36，我們可以讓36與根結(jié)點元素28比較，36比28大，接著查右子樹，查找成功。顯然，采用樹形結(jié)構(gòu)能節(jié)省查找時間。

圖6－3樹形結(jié)構(gòu)應(yīng)用舉例6.2.1二叉樹的定義和性質(zhì)

1.二叉樹的定義二叉樹(binarytree)是結(jié)點的有限集合，該集合或者為空集，或者是由一個根和兩棵互不相交的稱為該根的左子樹和右子樹的二叉樹組成。上述定義表明二叉樹可以為空集，因此，可以有空二叉樹，二叉樹的根也可以有空的左子樹或右子樹，從而得到圖6－4所示的二叉樹的五種基本形態(tài)。圖6－5是一個二叉樹的例子。

請注意樹和二叉樹定義之間的差別。首先，沒有空樹，卻可以有空二叉樹。其次，一般地，樹的子樹之間是無序的，其子樹不分次序，而二叉樹中結(jié)點的子樹要區(qū)分左、右子樹，即使在一棵子樹的情況下也要指明是左子樹還是右子樹(見圖6－6)。最后，樹中結(jié)點的度可以大于2，但二叉樹的每個結(jié)點最多只有兩棵子樹。除此之外，上一節(jié)中引入的關(guān)于樹的術(shù)語對二叉樹同樣適用圖6－4二叉樹的五種基本形態(tài)圖6－5二叉樹的例子圖6－6兩棵不同的二叉樹2.二叉樹的性質(zhì)性質(zhì)1

二叉樹的第i?(i≥1)層上至多有2i–1

個結(jié)點。對此結(jié)論可用歸納法證明之。當(dāng)i=1時，二叉樹只有一個結(jié)點，結(jié)論成立。設(shè)當(dāng)i=k時結(jié)論成立，即二叉樹上至多有2k–1

個結(jié)點,則當(dāng)i=k+1時，因為每個結(jié)點最多只有兩個孩子，所以，第k+1層上至多有2*2k–1=2k個結(jié)點，性質(zhì)成立。

性質(zhì)2

高度為h的二叉樹上至多有2h-1個結(jié)點。當(dāng)h=0時，二叉樹為空二叉樹。當(dāng)h>0時，利用性質(zhì)1，高度為h的二叉樹中結(jié)點的總數(shù)最多為(6－1)

性質(zhì)3

包含n個結(jié)點的二叉樹的高度至少為

lb

(n+1)

。因為高度為h的二叉樹最多有2h–1個結(jié)點，所以n≤2h–1,則有h≥lb(n+1)。由于h是整數(shù)，因而h≥

lb

(n+1)

。

性質(zhì)4

任意一棵二叉樹中，若葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則必有n0=n2+1。設(shè)二叉樹的度為1的結(jié)點數(shù)為n1，樹中結(jié)點總數(shù)為n，則n=n0+n1+n2。除根結(jié)點沒有雙親外，每個結(jié)點都有且僅有一個雙親，所以有n－1=n1+2n2作為孩子的結(jié)點，因此有n0=n2+1，結(jié)論成立。

定義1

高度為h的二叉樹如果有2h－1個結(jié)點，則該二叉樹稱為滿二叉樹(fullbinarytree)。

定義2

一棵二叉樹中，只有最下面兩層的結(jié)點的度可以小于2，并且最下一層的葉結(jié)點集中在靠左的若干位置上，這樣的二叉樹稱為完全二叉樹(completebinarytree)。圖6－7為上面兩種特殊的二叉樹的例子。圖6－7滿二叉樹和完全二叉樹的例子

(a)滿二叉樹;(b)完全二叉樹

性質(zhì)5

具有n個結(jié)點的完全二叉樹的高度為

lb

(n+1)

。設(shè)完全二叉樹的高度為h，則除最下一層外上面各層都是滿的，總共有2h

1－1個結(jié)點，而最下層，即第h層的結(jié)點個數(shù)最多不超過2h

1個。因此有

2h

1－1＜n≤2h－1(6－2)

移項得2h

1＜n+1≤2h(6－3)

取對數(shù)h－1＜lb(n+1)≤h(6－4)

因而h是不小于lb(n+1)的最小整數(shù)，即h=

lb

(n+1)

。

性質(zhì)6

假定對一棵有n個結(jié)點的完全二叉樹中的結(jié)點，按從上到下、從左到右的順序，從1到n編號(見圖6－7)，設(shè)樹中某一個結(jié)點的序號為i，1≤i≤n，則有以下關(guān)系成立：

(1)若i>1，則該結(jié)點的雙親的序號為

i/2

;當(dāng)i=1時，該結(jié)點為二叉樹的根;(2)若2i≤n，則該結(jié)點的左孩子的序號為2i，否則該結(jié)點無左孩子；

(3)若2i+1≤n，則該結(jié)點的右孩子的序號為2i+1，否則該結(jié)點無右孩子。6.2.2二叉樹ADT

現(xiàn)在我們使用抽象數(shù)據(jù)類型(見ADT6－1)定義二叉樹。這里只列出幾個最常見的運算。ADT6－1BTree{數(shù)據(jù)：二叉樹是結(jié)點的有限集合，它或者為空，或者由一個根結(jié)點和左、右子二叉樹組成。運算：

voidCreateBT(BTree*Bt);

后置條件:已構(gòu)造一個空二叉樹。BOOLIsEmpty(BTreebt)后置條件:若二叉樹為空，則返回TRUE，否則返回FALSE。

voidMakeBT(BTree*Bt，Kx,BTree*Lt，BTree*Rt)

后置條件：構(gòu)造一棵二叉樹*Bt，x為*Bt的根結(jié)點的元素值，*Lt成為*Bt的左子樹，*Rt成為右子樹，*Lt和*Rt都成為空二叉樹。

voidBreakBT(BTree*Bt，K*x,BTree*Lt，BTree*Rt)

前置條件：二叉樹非空。

后置條件：拆分二叉樹*Bt成為三部分，*x為根結(jié)點的值，*Lt為原*Bt的左子樹，*Rt為原*Bt的右子樹，*Bt自身成為空二叉樹。

BOOLRoot(BTreeBt,K*x)

后置條件：若二叉樹非空，則*x為根結(jié)點的值，返回TRUE，否則返回FALSE。

voidInOrder(BTreeBt,void(*Visit)(BTNode*u))

后置條件：中序遍歷二叉樹Bt，使用函數(shù)Visit訪問結(jié)點*u。

voidPreOrder(BTreeBt,void(*Visit)(BTNode*u))

后置條件：先序遍歷二叉樹Bt，使用函數(shù)Visit訪問結(jié)點*u。

voidPostOrder(BTreeBt,void(*Visit)(BTNode*u))

后置條件：后序遍歷二叉樹Bt，使用函數(shù)Visit訪問結(jié)點*u。}6.2.3二叉樹的存儲表示

1.完全二叉樹的順序表示完全二叉樹中的結(jié)點可以按層次順序存儲在一片連續(xù)的存儲單元中。根據(jù)性質(zhì)6，我們由一個結(jié)點的位置，可方便地計算出它的左、右孩子和雙親的位置，從而完全獲得二叉樹結(jié)構(gòu)的信息。為方便計算存儲位置，圖6－8中，我們從下標為1的位置開始存放完全二叉樹，即根結(jié)點存放在位置1。當(dāng)然從位置0開始存放也是可行的。一般二叉樹不宜采用順序表示，這是因為從圖6－8的存儲結(jié)構(gòu)上看，無法確定一棵普通二叉樹的樹形結(jié)構(gòu)信息。圖6－8圖6－7(b)的完全二叉樹的順序存儲

2.二叉樹的鏈接表示鏈接存儲結(jié)構(gòu)提供了一種自然的二叉樹在計算機內(nèi)的表示方法。我們可定義二叉樹的結(jié)點如下：LchildElementRchild

每個結(jié)點有三個域：Lchild、Element和Rchild。其中，Lchild和Rchild分別為指向左、右孩子的指針，Elment是元素域。圖6－9(b)是圖6－9(a)所示的二叉樹的鏈接存儲表示(常稱為二叉鏈表存儲結(jié)構(gòu))的示意圖。圖6－9二叉樹的鏈接存儲表示

(a)二叉樹;(b)二叉樹的鏈接表示

一棵有n個結(jié)點的二叉樹中，除了根結(jié)點外，其余每個結(jié)點均有一個出自某個指針域的指向該結(jié)點的指針，因此，共有n－1個指針域非空。指針域的數(shù)目為2n，所以恰有n+1個空指針域。下面給出二叉鏈表的結(jié)點結(jié)構(gòu)和二叉樹結(jié)構(gòu)的C語言類型定義。其中，BTNode是二叉樹的結(jié)點類型，BTree為二叉樹類型。typedefstructbtnode{KElement;structbtnode*Lchild,*Rchild;}BTNode;typedefstructbtree{structbtnode*Root;}BTree;

上面定義的二叉樹結(jié)構(gòu)適合從雙親到孩子方向的訪問。如果已知二叉樹的一個結(jié)點，要查找其雙親結(jié)點，在該結(jié)構(gòu)下只能采取從根結(jié)點開始，遍歷整個二叉樹的方法來實現(xiàn)，這顯然是費時的。這種做法類似于已知單鏈表的一個結(jié)點，為了得到其前驅(qū)結(jié)點，只能從表頭開始查找的情況。如果應(yīng)用程序需要經(jīng)常執(zhí)行從孩子到雙親訪問，那么可以在每個結(jié)點都增加一個Parent域，令它指向該結(jié)點的雙親結(jié)點。這樣做就實現(xiàn)了從孩子到雙親，從雙親到孩子的雙向鏈接結(jié)構(gòu)。

細心的讀者可能已注意到，在BTNode的定義中，元素Element的類型被定義為K，而非我們以前常使用的通用類型T，其目的是為了表明當(dāng)兩種元素類型不同的數(shù)據(jù)結(jié)構(gòu)同時使用時，需要使用兩種不同的通用數(shù)據(jù)類型，如K和T，這一點非常重要。在以后的二叉樹非遞歸遍歷算法中，我們將需要同時使用二叉樹和堆棧兩種數(shù)據(jù)結(jié)構(gòu)，它們的具體元素類型不同，也就是說K和T將被定義成不同的實際類型。事實上，即使對于同一個數(shù)據(jù)結(jié)構(gòu)，如果需要構(gòu)造具有不同具體元素類型的數(shù)據(jù)結(jié)構(gòu)對象時，也需要使用不同的通用數(shù)據(jù)類型。例如，如果我們希望定義兩個堆棧：整數(shù)棧和字符棧，在C語言環(huán)境下，也必須定義通用元素類型不同的兩個堆棧類型。C++的模板類有效地解決了這一問題，它能更自然、更方便地實現(xiàn)類屬ADT(見2.3節(jié))。

3.二叉樹運算的實現(xiàn)程序6－1是ADT6－1中定義的部分二叉樹運算，在二叉鏈表表示下的C語言實現(xiàn)。這里，我們給出了CreateBT、MakeBT和BreakBT三個運算的實現(xiàn)。三種二叉樹的遍歷運算的算法和實現(xiàn)將在下一節(jié)中專門討論。函數(shù)CreateBT的目的是構(gòu)造一棵空二叉樹，所以只需讓二叉樹結(jié)構(gòu)中指向根結(jié)點的指針Root為空指針即可，通過執(zhí)行語句Bt->Root=NULL;來實現(xiàn)。

函數(shù)MakeBT有四個參數(shù)BTree*Bt，Tx，BTree*Lt和BTree*Rt，它構(gòu)造一棵新二叉樹，該二叉樹的根結(jié)點的值為x，左、右子樹分別是二叉樹*Lt和*Rt所包含的二叉樹。值得注意的是：二叉樹*Lt和*Rt所包含的二叉樹成為*Bt所包含的二叉樹的左右子樹，它們自身應(yīng)當(dāng)成為空二叉樹。如果不這樣做，Lt->Root和Rt>Root在函數(shù)MakeBT執(zhí)行后仍然指向它們各自原來的根結(jié)點，而事實上，Lt->Root所指向的結(jié)點已成為Bt->Root所指向的結(jié)點的左孩子結(jié)點；同樣，Rt->Root所指向的結(jié)點已成為Bt->Root所指向的結(jié)點的右孩子結(jié)點。這種共享二叉樹中結(jié)點的現(xiàn)象是十分危險的，程序可以使用指針Lt->Root刪除或修改原屬于二叉樹*Lt中的那部分結(jié)點，這同時也是對二叉樹*Bt結(jié)點的刪除或修改。這種修改會造成混亂，應(yīng)當(dāng)盡量避免。函數(shù)MakeBt不難實現(xiàn)，但需注意語句Lt->Root=Rt->Root=NULL;是不可少的。

實現(xiàn)函數(shù)BreakBT的注意事項與MakeBT的相同。在拆分一棵二叉樹成為三部分后，應(yīng)當(dāng)執(zhí)行語句Bt->Root=NULL;free(p);，使得原二叉樹成為空二叉樹，并將原樹的根結(jié)點回收。同樣由于上面所述的原因，調(diào)用函數(shù)MakeBT和BreakBT也需注意，左、右子樹*Lt和*Rt不能是同一棵二叉樹，除非它們都是空二叉樹?！境绦?－1】二叉樹運算的C語言程序。BTNode*NewNode(){

BTNode*p=(BTNode*)malloc(sizeof(BTNode));

if(IS_FULL(p)){

fprintf(stderr,"Thememenyisfull\n");

exit(1);

}

returnp;}voidCreateBT(BTree*Bt){

Bt->Root=NULL; /*創(chuàng)建一棵空二叉樹*/}【程序6－2】二叉樹運算測試程序。voidmain(void){ BTreea,x,y,z;Ke; CreateBT(&a);CreateBT(&x); CreateBT(&y);CreateBT(&z); MakeBT(&y,'E',&a,&a);MakeBT(&z,'F',&a,&a); MakeBT(&x,'C',&y,&z); MakeBT(&y,'D',&a,&a); MakeBT(&z,'B',&y,&x); PreOrder(z,Visit); InOrder(z,Visit); BreakBT(&z,&e,&y,&x); PreOrder(z,Visit); InOrder(z,Visit);}

程序首先定義a、x、y和z四個二叉樹變量，并使用函數(shù)CreateBT將它們初始化為空二叉樹，然后調(diào)用MakeBT函數(shù)逐步構(gòu)造二叉樹。函數(shù)main的詳細執(zhí)行過程見圖6－10所示。請思考圖6－10(e)中，除二叉樹z以外的二叉樹變量a、x和y所包含的二叉樹這時應(yīng)有什么結(jié)構(gòu)。此時，如果執(zhí)行函數(shù)BreakBT，便可以從圖6－10(e)回到圖6－10(c)和(d)的狀態(tài)。圖6－10二叉樹運算應(yīng)用實例

(a)四棵空二叉樹；(b)二叉樹y和z；(c)以根結(jié)點“C”、y和z構(gòu)造二叉樹x；

(d)二叉樹y；(e)以根結(jié)點“B”、y和x構(gòu)造二叉樹6.2.4二叉樹的遍歷在6.2.2節(jié)的ADT6－1中定義了二叉樹的三種遍歷運算：先序遍歷、中序遍歷和后序遍歷。遍歷(traverse)一個有限結(jié)點的集合，意味著對該集合中的每個結(jié)點訪問且僅訪問一次。這里，訪問某個結(jié)點的含義是對該結(jié)點執(zhí)行某個簡單操作，如打印該結(jié)點，或修改該結(jié)點所包含的元素值等等，但一般不影響它所在的數(shù)據(jù)結(jié)構(gòu)。一個最簡單的訪問結(jié)點的函數(shù)的例子見程序6－3。該程序設(shè)元素類型K為char類型，函數(shù)Visit打印結(jié)點*p的元素值?！境绦?－3】訪問結(jié)點程序舉例。typedefcharK;voidVisit(BTNode*p){printf("%c",p->Element);}

二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，對一個非線性的數(shù)據(jù)結(jié)構(gòu)中的每一個結(jié)點毫不遺漏地訪問一遍，需要設(shè)定一種次序。對一個線性表的遍歷，這種次序是很自然的，可以從頭到尾，也可以從尾到頭。在二叉樹的情況下，二叉樹的遞歸定義將一棵二叉樹分成三部分：根和左、右子樹。這樣我們得到六種遍歷次序：VLR、LVR、LRV、VRL、RVL和VRL，其中，L、V和R分別代表遍歷左子樹、訪問根結(jié)點和遍歷右子樹。如果總是先訪問左子樹上全部結(jié)點后，再訪問右子樹上結(jié)點，則有三種遍歷次序：VLR、LVR和LRV，否則還有另外三種遍歷次序：VRL、RVL和RLV。我們在這里只介紹前三種遍歷方法。這三種遍歷二叉樹的遞歸算法可描述如下。(1)先序遍歷(VLR)：若二叉樹為空，則為空操作；否則①訪問根結(jié)點；②先序遍歷左子樹；③先序遍歷右子樹。(2)中序遍歷(LVR)：若二叉樹為空，則為空操作；否則①中序遍歷左子樹；②訪問根結(jié)點；③中序遍歷右子樹。(3)后序遍歷(LRV)：若二叉樹為空，則為空操作；否則①后序遍歷左子樹；②后序遍歷右子樹；③訪問根結(jié)點。圖6－11二叉樹的三種遍歷實例一(a)二叉樹；(b)三種遍歷次序圖6－12二叉樹的三種遍歷實例二

(a)二叉樹；(b)三種遍歷次序二叉樹還可以按層次遍歷。二叉樹的層次遍歷為：首先訪問第一層上的結(jié)點，再訪問第二層上的結(jié)點，依此類推，訪問二叉樹上的全部結(jié)點。我們將實現(xiàn)二叉樹層次遍歷的算法設(shè)計留作作業(yè)。程序6－4是三種遍歷運算的算法。在前面的學(xué)習(xí)中，我們幾乎都用一個C語言函數(shù)來實現(xiàn)一個數(shù)據(jù)結(jié)構(gòu)上的運算。但在程序6－4中我們將看到，有時需要設(shè)計一個以上的C語言函數(shù)來實現(xiàn)一個運算。在實現(xiàn)遍歷運算時，為了向客戶提供便利的界面，我們?yōu)槊總€遍歷運算設(shè)計了一個面向用戶的函數(shù)和一個具體實現(xiàn)遍歷操作的函數(shù)。具體實現(xiàn)遍歷操作的函數(shù)應(yīng)作為該數(shù)據(jù)結(jié)構(gòu)的私有函數(shù)，不被用戶直接使用，它們的實現(xiàn)細節(jié)對外界應(yīng)當(dāng)是隱蔽的。雖然C語言并沒有提供強有力的語言機制實施信息隱蔽，但我們可以不將這些私有函數(shù)包含在頭文件中。在程序6－4的遍歷程序中，我們使用了一個指向函數(shù)的指針Visit。指向函數(shù)的指針變量的一般定義形式為類型名(*指針變量名)(參數(shù)表)PreOrd、InOrd和PostOrd是三個遞歸函數(shù)，它們實現(xiàn)具體的遍歷運算。PreOrder、InOrder和PostOrder是提供給用戶的遍歷運算的接口函數(shù)，他們分別調(diào)用這三個遞歸函數(shù)實現(xiàn)對二叉樹的遍歷。接口函數(shù)必須滿足ADT6－1的規(guī)范。使用接口函數(shù)，可以使用戶無須考慮二叉樹結(jié)構(gòu)是如何實現(xiàn)的。如果我們直接將遞歸函數(shù)PreOrd提供給用戶使用，則用戶必須知道實在參數(shù)Bt.Root，才能使用函數(shù)PreOrd(Visit,Bt.Root)，而Bt.Root是BTree的實現(xiàn)細節(jié)，按照抽象數(shù)據(jù)類型的宗旨，用戶是不必知道的，也是不應(yīng)該知道的。函數(shù)Preorder需要兩個參數(shù)：一棵二叉樹對象和訪問結(jié)點的方式函數(shù)Visit，這些信息與用戶的使用直接相關(guān)?！境绦?－4】二叉樹遍歷程序。voidPreOrd(void(*Visit)(BTNode*u),BTNode*t){ if(t){ (*Visit)(t); PreOrd(Visit,t->LChild); PreOrd(Visit,t->RChild); }}voidInOrd(void(*Visit)(BTNode*u),BTNode*t){ if(t){ InOrd(Visit,t->LChild); (*Visit)(t); InOrd(Visit,t->RChild); }}voidPostOrd(void(*Visit)(BTNode*u),BTNode*t){if(t){ PostOrd(Visit,t->LChild); PostOrd(Visit,t->RChild); (*Visit)(t); }}voidPreOrder(BTreeBt,void(*Visit)(BTNode*u)){ PreOrd(Visit,Bt.Root);}voidInOrder(BTreeBt,void(*Visit)(BTNode*u)){ InOrd(Visit,Bt.Root);}voidPostOrder(BTreeBt,void(*Visit)(BTNode*u)){ PostOrd(Visit,Bt.Root);}

下面我們將舉例說明二叉樹遍歷的遞歸算法的執(zhí)行過程。設(shè)二叉樹對象Bt包括一棵如圖6－11(a)所示的二叉樹。如果要先序遍歷該二叉樹，只需調(diào)用PreOrder(Bt，Visit)，其中，函數(shù)Visit是訪問結(jié)點的函數(shù)。此函數(shù)將調(diào)用PreOrd(Visit,Bt.Root)實現(xiàn)對二叉樹的先序遍歷，這里，Bt.Root是二叉樹Bt中指向根結(jié)點的指針。我們跟蹤函數(shù)PreOrd(Visit,Bt.Root)的執(zhí)行過程，其執(zhí)行過程可以由如下的函數(shù)調(diào)用和訪問序列來描述。我們將以指向根結(jié)點A的指針作為實在參數(shù)的調(diào)用，簡單地寫作PreOrd(A)。圖6－13是先序遍歷遞歸函數(shù)的執(zhí)行過程示意圖。 PreOrd(A)VisitAPreOrd(B)Visit(B)PreOrd(NULL)PreOrd(D)Visit(D)PreOrd(NULL)PreOrd(NULL)圖6－13先序遍歷遞歸函數(shù)的執(zhí)行過程示意圖 PreOrd(C)Visit(C)PreOrd(E)Visit(E)PreOrd(NULL)PreOrd(NULL)PreOrd(F)Visit(F)PreOrd(NULL)PreOrd(NULL)圖6－13先序遍歷遞歸函數(shù)的執(zhí)行過程示意圖6.2.5*二叉樹遍歷的非遞歸算法以上討論了二叉樹遍歷的遞歸算法。遞歸是程序設(shè)計中強有力的工具，遞歸函數(shù)結(jié)構(gòu)清晰，程序易讀。然而在3.4節(jié)的討論中我們也看到了遞歸函數(shù)有不可克服的弱點：時間、空間效率較低，運行代價較高。所以在實際使用中，我們常常希望得到算法的非遞歸版本。下面我們以先序遍歷為例，介紹二叉樹遍歷的非遞歸算法。

為了實現(xiàn)非遞歸遍歷算法，我們需要一個堆棧作為實現(xiàn)算法的輔助數(shù)據(jù)結(jié)構(gòu)，堆棧用于存放在遍歷過程中的待處理的任務(wù)線索。二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，遍歷過程中涉及的每一個結(jié)點，都可能有左、右兩棵子樹，任何時刻程序只能訪問其中之一，所以程序必須保留以后繼續(xù)訪問另一棵子樹的線索。我們使用堆棧來保留繼續(xù)遍歷的線索。事實上，在二叉樹的遞歸遍歷算法中，是系統(tǒng)堆棧(見3.4節(jié))承擔(dān)了此項任務(wù)。

程序6－5是二叉樹先序遍歷的非遞歸或稱迭代(iteration)函數(shù)，它使用與ADT6－1中定義的運算PreOrder完全相同的函數(shù)接口，能夠保證客戶程序可以毫無變動地使用新版本的迭代函數(shù)。這正是封裝和信息隱蔽的目的，因而也是抽象數(shù)據(jù)類型的目的。這里，我們將函數(shù)命名為IPreOrder以區(qū)別于函數(shù)PreOrder。

函數(shù)IPreOrder首先構(gòu)造一個空堆棧，堆棧的元素類型設(shè)定為BTNode*類型，它是指向二叉鏈表的結(jié)點的指針類型。在堆棧的底部壓入一個NULL指針是為了簡化算法而做的。在先序遍歷下，根結(jié)點是首先被訪問的結(jié)點。所以若p!=NULL，則應(yīng)當(dāng)訪問p所指示的結(jié)點，算法執(zhí)行函數(shù)(*Visit)(p)，訪問指針p所指向的結(jié)點中的元素。這之后按照先序遍歷原則，應(yīng)接著訪問*p的左子樹上所有結(jié)點，訪問完畢左子樹，算法才訪問*p的右子樹。所以為了在左子樹訪問完畢后，能獲得右子樹的根結(jié)點的地址，我們應(yīng)當(dāng)先讓右子樹的根結(jié)點的地址進棧，這一點由語句if(p->RChild)Push(&s,p->RChild)實現(xiàn)。

圖6－14顯示了在對圖6－11(a)所示的二叉樹執(zhí)行程序6－5的函數(shù)的過程中堆棧狀態(tài)的變化。(代表空指針，棧中的元素C、D、F等在這里代表指向包含該元素的結(jié)點的指針。我們知道在迭代的遍歷算法中，堆棧中的元素是指向二叉樹中結(jié)點的指針類型(BTNode*)。為簡單起見，圖中直接用該結(jié)點所包含的元素表示，請注意不要混淆。圖6－14堆棧狀態(tài)變化(a)訪問A，C進棧；(b)訪問B，D進棧；(c)D出棧；(d)訪問D，C出棧(e)訪問C，F(xiàn)進棧；(f)訪問E，F(xiàn)出棧；(g)訪問F【程序6－6】中序遍歷的迭代函數(shù)。

voidIInOrder(BTreeBt,void(*Visit)(BTNode*u)){Stacks;BTNode*p=Bt.Root;CreateStack(&s,MaxStack);while(p||!IsEmpty(s)){ if(!p){ StackTop(s,&p);Pop(&s);(*Visit)(p); p=p->RChild;} else{Push(&s,p);p=p->LChild; }}}

在遍歷過程中，每個結(jié)點被訪問且僅被訪問一次，所以遍歷算法的時間復(fù)雜度為O(n)。所需的輔助空間是棧的容量，棧的容量不超過樹的高度，所以其空間復(fù)雜度為O(n)。6.2.6*二叉樹遍歷的應(yīng)用實例

1.計算二叉樹的結(jié)點個數(shù)運用后序遍歷的思想，很容易實現(xiàn)計算一棵二叉樹中結(jié)點總數(shù)的算法。為了計算一棵二叉樹的結(jié)點數(shù)目，可以將二叉樹分解。如果二叉樹是空樹，顯然，其結(jié)點數(shù)目為0。一棵非空的二叉樹的結(jié)點數(shù)目是其左、右子樹的結(jié)點數(shù)目之和再加上一個根結(jié)點。遞歸函數(shù)Size調(diào)用Size(p->LChild)和Size(p->RChild)分別計算左、右子樹的結(jié)點數(shù)目，表達式Size(p->LChild)+Size(p->RChild)+1則計算三部分結(jié)點之和，它是二叉樹上總的結(jié)點個數(shù)，見程序6－7。函數(shù)SizeofBT是向用戶提供的計算一棵二叉樹的結(jié)點數(shù)目的接口函數(shù)。為了幫助讀者認清函數(shù)Size本質(zhì)上是一種后序遍歷算法，程序書寫顯得累贅。函數(shù)Size1較之函數(shù)Size簡潔，其實這兩個函數(shù)是完全相同的?！境绦?－7】求二叉樹的結(jié)點數(shù)。intSize(BTNode*p){ints,s1,s2;if(!p)return0;else{s1=Size(p->LChild);s2=Size(p->RChild);s=s1+s2+1;returns;}}intSizeofBT(BTreeBt){returnSize(Bt.Root);}intSize1(BTNode*p){if(!p)return0;elsereturnSize1(p->LChild)+Size1(p->RChild)+1;}

2.求二叉樹的高度求二叉樹的高度的算法與上面的求結(jié)點數(shù)目的算法的思路基本相同?？斩鏄涞母叨葹?，非空二叉樹的高度是它的左、右子樹中高的那棵子樹的高度加一，見程序6－8。該程序同樣也是后序遍歷?！境绦?－8】求二叉樹的高度。intDepth(BTNode*p){if(!p)return0;elsereturn1+max(Depth(p->LChild),Depth(p->RChild));}intDepthofBT(BTreeBt){returnDepth(Bt.Root);}

3.復(fù)制一棵二叉樹復(fù)制二叉樹使用的是先序遍歷。p指向被復(fù)制的二叉樹的根結(jié)點，對結(jié)點*p，函數(shù)Copy構(gòu)造一個新結(jié)點*q，并將結(jié)點*p的元素值復(fù)制到結(jié)點*q的元素域。遞歸函數(shù)調(diào)用q->LChild=Copy(p->LChild);和q->RChild=Copy(p->RChild);分別復(fù)制結(jié)點*p的左、右子樹，返回這兩棵新子樹的根結(jié)點指針，并將它們分別賦給q->LChild和q->Rchild，這樣結(jié)點*q的元素值是*p的元素值，其左、右子樹是由*p的左、右子樹復(fù)制而成的新子樹，見程序6－9。函數(shù)NewNode見6.2.3節(jié)中程序6－1?！境绦?－9】復(fù)制二叉樹。BTNode*Copy(BTNode*p){ BTNode*q; if(!p)returnNULL; q=NewNode(); q->Element=p->Element; q->LChild=Copy(p->LChild);q->RChild=Copy(p->RChild);returnq;}BTreeCopyofBT(BTreeBt){ BTreea; a.Root=Copy(Bt.Root); returna;}6.2.7*線索二叉樹

1．線索樹的定義我們已經(jīng)知道，一棵有n個結(jié)點的二叉樹有n+1個空子樹。當(dāng)使用二叉鏈表存儲時有n+1個空指針域。如何將這些空指針域利用起來呢？一種做法是利用它們來存放遍歷信息，這樣既能加快遍歷速度，又可不使用堆棧，從而節(jié)省?？臻g。

利用空指針域的具體做法是用它們來保存該結(jié)點在中序、先序或后序遍歷下的前驅(qū)、后繼結(jié)點的地址。這里的前驅(qū)和后繼指的是遍歷過程中，二叉樹中元素被訪問的先后次序。一個空指針域，如果被用于存放指向某種遍歷次序下的前一個結(jié)點或后一個結(jié)點的地址，則被稱為線索(thread)。線索是結(jié)點的地址，但它們不同于二叉鏈表中原有的指針值。原來的非空指針域存放的是它們的左孩子或右孩子結(jié)點的地址。加進了線索的二叉樹稱為二叉線索樹(又稱穿線樹)。在線索二叉樹中，線索就好象一根線，將二叉樹的結(jié)點按中序、先序、或后序的順序連接起來。

圖6－15(a)為圖6－9(a)所示的二叉樹的中序線索樹，圖6－15(b)是它的二叉鏈表形式。圖6－15中，我們用實線表示指向孩子的指針，用虛線表示線索。在二叉鏈表存儲結(jié)構(gòu)中，為了區(qū)分兩者，必須增加兩個標志域：LTag和RTag。這樣，二叉線索樹的每個結(jié)點的結(jié)構(gòu)為：LChildLTagElementRTagRChild

其中，LTag為0，表示LChild域是指向左孩子的指針；LTag為1，表示LChild域是指向(按遍歷次序)前驅(qū)結(jié)點的指針(即線索)或空指針。RTag為0，表示RChild域是指向右孩子的指針；RTag為1，表示RChild域是指向(按遍歷次序)后繼結(jié)點的指針(即線索)或空指針。利用線索樹，我們?nèi)菀讓崿F(xiàn)求二叉樹中某個結(jié)點在指定遍歷次序下的前驅(qū)或后繼結(jié)點的算法。這樣，我們可以不使用堆棧，就能實現(xiàn)遍歷運算。需要說明的是，圖6－15的線索樹既有左線索又有右線索，實際上，在二叉樹的許多應(yīng)用中，可根據(jù)需要只作單邊穿線。圖6－15二叉線索樹及其二叉鏈表表示

(a)二叉線索樹；(b)線索樹的二叉鏈表

2．構(gòu)造中序線索樹假定圖6－15(b)的線索樹的二叉鏈表已經(jīng)按普通二叉樹的方式建立，即除LTag和RTag域外，元素域和左、右指針域已按普通二叉鏈表賦值，現(xiàn)討論如何使用中序遍歷遞歸算法，將其改建成一棵中序線索樹。具體做法是：在中序遍歷過程中，如果某個結(jié)點的左指針域為空，則將該指針域改為指向其中序遍歷次序下的前驅(qū)結(jié)點的地址，并且令Ltag＝1；如果右指針域為空指針域，將該指針域指向中序遍歷次序下后繼結(jié)點的地址，并且令Rtag＝1，見程序6－10。

程序6－10包括兩個函數(shù)：函數(shù)MakeThread和BuildThreadBT，其中，函數(shù)MakeThread是遞歸函數(shù)，它被函數(shù)BuildThreadBT調(diào)用。從根本上看，函數(shù)MakeThread是一個中序遍歷過程。在函數(shù)體中，兩次遞歸函數(shù)調(diào)用語句(MakeThread(t->LChild,ppr)和MakeThread(t->RChild,ppr))之間的代碼段，用于實現(xiàn)對當(dāng)前訪問的結(jié)點穿線?！境绦?－10】構(gòu)造中序線索樹。voidMakeThread(BTNode*t,BTNode*ppr){if(t){MakeThread(t->LChild,ppr);if(*ppr)if(!(*ppr)->RChild){(*ppr)->RTag=1;(*ppr)->RChild=t; } else(*ppr)->RTag=0; if(!t->LChild){ t->LTag=1;t->LChild=*ppr; } elset->LTag=0; *ppr=t; MakeThread(t->RChild,ppr);}}voidBuildThreadBT(BTreeBt){ BTNode*pr=NULL; if(Bt.Root){ pr=NULL; MakeThread(Bt.Root,&pr); pr->RTag=1;}}

在函數(shù)BuildThreadBT中，指針變量pr在遍歷開始時為NULL，它的地址&pr作為實在參數(shù)傳遞給函數(shù)MakeThread。函數(shù)MakeThread中的ppr具有BTNode**類型，所以*ppr才是指向二叉線索樹中結(jié)點的指針。*ppr的初值為NULL，以后總是指向t在中序次序下的前驅(qū)結(jié)點，指針t指向當(dāng)前正在訪問的結(jié)點。每訪問一個結(jié)點t后，便令指針*ppr指向該結(jié)點，在算法訪問下一個結(jié)點時，*ppr已指向其中序次序的前驅(qū)結(jié)點。

對參數(shù)t的每個值，算法完成下列事項：

(1)若*ppr為空指針，表明當(dāng)前訪問的結(jié)點*t是中序遍歷的第一個結(jié)點。如果*t的LChild域為空指針，則只需令*t的Ltag=1。

(2)若*ppr不為空指針，此時*ppr必定指向*t的中序遍歷的前驅(qū)結(jié)點，如果(*ppr)->RChild域為空指針，則應(yīng)修改*ppr指向的結(jié)點的Rchild和RTag域，即令(*ppr)->RChild=t，(*ppr)->Rtag=1，否則只需令(*ppr)->RTag=0。(3)若t->LChild為空指針，則應(yīng)修改結(jié)點*t的LChild和Ltag域，即令t->LTag=1，t->LChild=*ppr，否則只需令t->LTag=0。

(4)令*ppr=t，記錄下當(dāng)前處理的結(jié)點，在中序遍歷訪問下一個結(jié)點時，它將成為前驅(qū)結(jié)點。

(5)執(zhí)行函數(shù)MakeThread后，還留下最后一個結(jié)點的Rtag域未設(shè)置，在函數(shù)BuildThreadBT中設(shè)置成1。

3．在中序線索樹上求中序遍歷的第一個結(jié)點程序6－11是在中序線索樹上求中序遍歷次序下第一個被訪問的結(jié)點。它是二叉樹上從根結(jié)點開始向左子樹走，最左下方的結(jié)點。函數(shù)GoFirst返回指向中序遍歷次序下第一個被訪問的結(jié)點的指針?！境绦?－11】中序遍歷的第一個結(jié)點。BTNode*GoFirst(BTreeBt){BTNode*p＝Bt.Root; if(p)while(p->LChild)p=p->LChild; returnp;}

4.在中序線索樹上求任意結(jié)點*p的后繼結(jié)點程序6－12實現(xiàn)在中序線索樹上求指定結(jié)點*p的下一個被訪問的結(jié)點。如果結(jié)點*p有右子樹，則結(jié)點*p的中序遍歷的后繼結(jié)點是該右子樹上最左下方的結(jié)點，否則p->Rchild域保存的即是該后繼結(jié)點的地址。函數(shù)Next返回*p的中序次序的后繼結(jié)點。如果*p沒有后繼，則返回NULL。【程序6－12】求任意結(jié)點*p的后繼結(jié)點。BTNode*Next(BTNode*p){BTNode*q=p->RChild;if(!p->RTag) while(!q->LTag)q=q->LChild;returnq;}5.遍歷二叉線索樹【程序6－13】遍歷二叉線索樹。voidTInOrder(BTreeBt,void(*Visit)(BTNode*u)){BTNode*p;p=GoFirst(Bt);while(p){(*Visit)(p);p=Next(p); }}

圖6－16后序線索樹的例子

同樣地，我們也可以實現(xiàn)先序和后序線索樹。圖6－16是后序線索樹的例子。線索樹的修改是比較困難的，對于經(jīng)常要做遍歷運算，而又很少需要插入或刪除元素的二叉樹應(yīng)用問題，可以采用線索樹結(jié)構(gòu)。對于需頻繁插入和刪除元素的二叉樹應(yīng)用，線索樹并不是很好的選擇。6.3樹和森林6.3.1森林與二叉樹的轉(zhuǎn)換如果樹和森林能夠用二叉樹表示，那么前面對二叉樹的討論成果便可應(yīng)用于一般樹和森林。事實上，森林(或樹)和二叉樹之間有著一種自然的對應(yīng)關(guān)系，可以容易地將任何森林惟一地表示成一棵二叉樹。具體做法是：將森林中的各樹的根用線連起來，在樹中，凡是兄弟用線連起來，然后去掉從雙親到除了第一個孩子以外的孩子的連線，只保留雙親到第一個孩子的連線，最后，使之稍微傾斜成習(xí)慣的二叉樹形，見圖6－17。樹所對應(yīng)的二叉樹中，一個結(jié)點的左孩子是它在原樹中的第一個孩子，而右孩子則是它在原樹中的位于其右側(cè)的兄弟。單獨一棵樹所對應(yīng)的二叉樹的根結(jié)點的右子樹總是空的，參看圖6－17(a)中T1或T2所分別對應(yīng)的那部分樹形。圖6－17森林與二叉樹的轉(zhuǎn)換

(a)森林F=(T1,T2);(b)F所對應(yīng)的二叉樹B

1.森林轉(zhuǎn)換成二叉樹令F=(T1，T2，...，Tn)是森林，則F所對應(yīng)的二叉樹B(F)為：

(1)若F為空，則B為空二叉樹。

(2)若F非空，則B的根是F中第一棵子樹T1的根R1，B的左子樹是R1的子樹森林(T11，T12，...，T1m)所對應(yīng)的二叉樹，B的右子樹是森林(T2，...，Tn)所對應(yīng)的二叉樹。反之，只要逆轉(zhuǎn)上述過程，任何二叉樹都對應(yīng)于惟一的森林。二叉樹轉(zhuǎn)換成森林的過程定義如下。

2.二叉樹轉(zhuǎn)換成森林令B=(R，LB，RB)是二叉樹，R是根，LB是左子樹，RB是右子樹，則B所對應(yīng)的森林F=(T1，T2，...，Tn)為：

(1)若B為空，則F為空森林。

(2)若B非空，則F的第一棵樹T1的根是二叉樹的根R，T1的根的子樹森林是B的左子樹LB所對應(yīng)的森林，F(xiàn)中的其余樹(T2，...，Tn)是B的右子樹RB所對應(yīng)的森林。

我們可以看到，以上對森林與二叉樹之間的相互轉(zhuǎn)換過程的定義都是遞歸的。它們首先直接定義了一種簡單情況的轉(zhuǎn)換辦法，即若森林為空森林，則對應(yīng)的二叉樹為空二叉樹，反之亦然。對非空二叉樹與森林的轉(zhuǎn)換方法是將二叉樹劃分成三部分：根，左子樹和右子樹，同樣也將森林劃分成三部分：第一棵樹的根，第一棵樹中除去根后得到的子樹組成的森林，以及除去第一棵樹外，其余樹組成的森林。通過在這三部分之間建立一一對應(yīng)關(guān)系，來實現(xiàn)森林與二叉樹之間的轉(zhuǎn)換。如果當(dāng)前轉(zhuǎn)換的二叉樹不是空樹，也就是還不是足夠小，則需進一步按這三部分細分。

遞歸函數(shù)的設(shè)計方法往往采用將大問題化解為較小的問題的做法，這種分解可一直進行，直到問題足夠小可以直接求解為止。較小的問題解決了，在此基礎(chǔ)上，就能解決較大規(guī)模的問題。比如二叉樹與森林的相互轉(zhuǎn)換中，如果一棵二叉樹的左、右子樹都已分別轉(zhuǎn)換成對應(yīng)的森林，則意味著該二叉樹與森林的轉(zhuǎn)換也已實現(xiàn)，即只需按上面所說的三部分一一對應(yīng)起來即可。這就是所謂的算法設(shè)計的分治策略(divideandconquer)。6.3.2樹和森林的存儲表示由于樹是非線性數(shù)據(jù)結(jié)構(gòu)，我們大多采用鏈接方式存儲它們。如果樹結(jié)構(gòu)的大小和形狀改變不大時，也可采取順序方式存儲。

1.多重鏈表表示法在計算機內(nèi)表示一棵樹的最直接的方法是多重鏈表表示法，即每個結(jié)點中包含多個指針域，存放每個孩子結(jié)點的地址。由于一棵樹中每個結(jié)點的子樹數(shù)不盡相同，每個結(jié)點的指針域數(shù)應(yīng)設(shè)定為樹的度數(shù)m，即樹中孩子數(shù)最多的結(jié)點的度。因而，每個結(jié)點的結(jié)構(gòu)如下：ElementChild1Child2…Childm

采用這種有多個指針域且結(jié)點長度固定的鏈表稱為多重鏈表。設(shè)度為m的樹中有n個結(jié)點，每個結(jié)點有m個指針，總共有n*m個指針域，其中，只有n－1個非空指針域，其余n*m－(n－1)=n(m－1)+1個指針域均為空?？梢娺@樣的存儲空間是不經(jīng)濟的，但這種方法的好處是實現(xiàn)運算容易。

2.孩子兄弟表示法孩子兄弟表示法實質(zhì)上就是樹所對應(yīng)的二叉樹的二叉鏈表表示法。這種方法的每個結(jié)點的結(jié)構(gòu)為：LeftChildElementRightSibling

圖6－18給出了這種表示法的一個例子。由圖可見，這種表示法本質(zhì)上等同于將森林轉(zhuǎn)換成二叉樹后以二叉鏈表方式存儲。圖6－18孩子兄弟表示法(a)樹；(b)所對應(yīng)的二叉樹；(c)左孩子右兄弟表示法

3.雙親表示法多重鏈表表示法和孩子兄弟表示法都能方便地從雙親結(jié)點查找孩子結(jié)點，但在有些應(yīng)用場合則要求從孩子結(jié)點能方便地得知雙親結(jié)點的地址，這時可采用雙親表示法。雙親表示法的每個結(jié)點有兩個域：Element和Parent。Parent域是指向該結(jié)點的雙親結(jié)點的指針，根結(jié)點無雙親。圖6－19(b)和(c)是圖6－19(a)的樹的雙親表示法的兩種存儲方式。圖6－19(c)中，使用一個連續(xù)的存儲區(qū)(比如使用C語言數(shù)組)存儲樹，下標代表結(jié)點地址，根結(jié)點的Parent值為－1，其他結(jié)點的Parent值是其雙親結(jié)點的下標，其中，結(jié)點是按自上而下、自左至右的次序存儲的。圖6－19雙親表示法

(a)雙親表示法示意圖；(b)雙親表示法(鏈接存儲)；(c)雙親表示法(順序存儲)

4.三重鏈表表示法為了既能方便地從雙親查找孩子，又能方便地從孩子查找雙親，可以將雙親表示法和孩子兄弟表示法結(jié)合起來，這就是三重鏈表表示法。這種方法中，每個結(jié)點有三個鏈域，形成三重鏈表，每個結(jié)點的結(jié)構(gòu)為：LeftChildElementRightSiblingParent

5.帶右鏈的先序表示法對圖6－17(a)的森林所對應(yīng)的二叉樹(圖6－17(b))的先序遍歷的次序為：A，B，C，K，D，E，H，F(xiàn)，J，G

我們已經(jīng)知道，森林中一個結(jié)點的第一個孩子在二叉樹中成為它的左孩子，它的右側(cè)兄弟在二叉樹中是它的右孩子。森林轉(zhuǎn)換成二叉樹后便可以按二叉樹形式存儲。圖6－20帶右鏈的先序表示法

帶右鏈的先序表示法是將一棵二叉樹中的結(jié)點，按先序遍歷的訪問次序依次存儲在一個連續(xù)的存儲區(qū)中，如圖6－20所示。二叉樹的先序遍歷次序的特點是：一個結(jié)點如果有左孩子，則必定緊隨其后，因此可以省去LChild域，但需增設(shè)一個左標志位LTag。LTag為0表示緊隨其后的結(jié)點是該結(jié)點的左孩子(即第一個孩子)，否則LTag為1。該結(jié)點的右孩子(即右兄弟)由指針Sibling直接指明。進一步觀察可知，LTag域也可以省略，因為它的信息可以從Sibling域間接得知。除最后一個結(jié)點外，Sibling域的箭頭所指示的結(jié)點的前一個結(jié)點的LTag域必為1。圖6－17(a)的森林的帶右鏈的先序表示法如圖6－20所示。6.3.3樹和森林的遍歷

1．按深度方向的遍歷對于樹和森林，我們同樣可以定義各種運算。下面我們僅考察樹和森林的遍歷運算。樹和森林的遍歷可以按深度方向進行，也可以按寬度方向進行。既然森林和二叉樹有著一一對應(yīng)的關(guān)系，那么二叉樹的三種遍歷次序也能對應(yīng)到相應(yīng)森林的三種遍歷次序，即先序、中序和后序。(1)先序遍歷算法：若森林為空，則遍歷結(jié)束；否則訪問第一棵樹的根；按先序遍歷第一棵樹的根結(jié)點的子樹組成的森林；按先序遍歷除第一棵樹外其余樹組成的森林。(2)中序遍歷算法:若森林為空，則遍歷結(jié)束;否則按中序遍歷第一棵樹的根結(jié)點的子樹組成的森林；訪問第一棵樹的根；按中序遍歷除第一棵樹外其余樹組成的森林。(3)后序遍歷算法:若森林為空，則遍歷結(jié)束;否則按后序遍歷第一棵樹的根結(jié)點的子樹組成的森林；按后序遍歷除第一棵樹外其余樹組成的森林;

訪問第一棵樹的根。

由森林和二叉樹的轉(zhuǎn)換方法可知，森林中的第一棵樹的根即二叉樹的根，第一棵樹的子樹組成的森林對應(yīng)于二叉樹的左子樹，而除第一棵樹外其余樹組成的森林是二叉樹的右子樹，所以，對森林的先序遍歷、中序遍歷和后序遍歷的結(jié)果應(yīng)與對應(yīng)二叉樹的先序、中序和后序遍歷的結(jié)果完全相同。例如對圖6－17(a)的森林的先序遍歷的結(jié)果是：ABCKDEHFJG，它等同于對圖6－17(b)的二叉樹的先序遍歷。但是，對森林的后序遍歷在邏輯上不很自然，因為在這種遍歷方式下，對森林中的某一棵樹的結(jié)點的遍歷被割裂成兩部分，對樹根的訪問被推遲到對其余樹上結(jié)點都訪問完畢后才進行，所以不常用。

2．按寬度方向遍歷二叉樹可以按層次遍歷，一般樹和森林也可按層次遍歷。具體做法是：首先訪問處于第一層的全部結(jié)點，然后訪問處于第二層的結(jié)點，再訪問第三層，……，最后訪問最下層的結(jié)點。對圖6－17(a)的森林按寬度方向的遍歷結(jié)果是：ADBCEFGKHJ。顯然對森林的層次遍歷與對應(yīng)二叉樹的層次遍歷之間沒有邏輯的對應(yīng)關(guān)系。6.4*堆和優(yōu)先權(quán)隊列

在很多應(yīng)用中需要一種數(shù)據(jù)結(jié)構(gòu)來存儲元素，元素加到數(shù)據(jù)結(jié)構(gòu)中去的次序是無關(guān)緊要的，但要求每次從數(shù)據(jù)結(jié)構(gòu)取出的元素是具有最高優(yōu)先級的元素，這樣的數(shù)據(jù)結(jié)構(gòu)被稱為優(yōu)先權(quán)隊列。顯然，優(yōu)先權(quán)隊列中的每個元素都應(yīng)有一個優(yōu)先權(quán)，優(yōu)先權(quán)是可以比較高低(大小)的。優(yōu)先權(quán)隊列(priorityqueue)不同于先進先出(FIFO)隊列，優(yōu)先權(quán)隊列中的元素，按其優(yōu)先級的高低而不是按進入隊列的次序，來確定出隊列的次序。

實現(xiàn)優(yōu)先權(quán)隊列可以有多種方法。一種最簡單的做法是用線性表表示優(yōu)先權(quán)隊列。這時，入隊列運算的做法可以是：將元素插在表的最前面(或尾部)；相應(yīng)的出隊列運算的做法是：從隊列中查找具有最高優(yōu)先級的元素，并刪除之。這種實現(xiàn)方法需要在線性表中查找元素，查找線性表的時間復(fù)雜度為O(n)。堆是一種很有用的數(shù)據(jù)結(jié)構(gòu)，它可以高效地實現(xiàn)優(yōu)先權(quán)隊列。另外，在內(nèi)排序一章中，我們將看到，堆還可用于實現(xiàn)時間復(fù)雜度為O(nlbn)的堆排序算法。6.4.1堆

1.堆的定義一個大小為n的堆(heap)是一棵包含n個結(jié)點的完全二叉樹，該樹中每個結(jié)點的關(guān)鍵字值大于等于雙親結(jié)點的關(guān)鍵字值。完全二叉樹的根稱為堆頂，它的關(guān)鍵字值是整棵樹上最小的。這樣定義的堆稱為最小堆(MinHeap)。我們可以用類似的方式定義最大堆(MaxHeap)。

由此看來，一個堆是一棵完全二叉樹。當(dāng)這棵完全二叉樹以順序方式存儲時，事實上排成了結(jié)點序列(k1,k2,…,kn)。所以堆又可以定義為：n個元素的序列(k1,k2,…,kn)，當(dāng)且僅當(dāng)滿足ki≤k2i且ki≤k2i+1,(i=1,2,…,(ln/2()時稱為堆(最小堆)。這時，堆頂元素是序列的第一個元素。圖6－21是堆的例子，其中，圖6－21(a)是最小堆，圖6－21(b)是最大堆，圖6－21(c)是圖6－21(a)的最小堆的順序存儲表示。堆的順序表示即完全二叉樹的順序表示，此處仍從下標1開始存儲元素。圖6－21堆的例子

(a)最小堆；(b)最大堆；(c)(a)的最小堆的順序存儲

2.堆的順序存儲表示現(xiàn)在來定義堆的結(jié)構(gòu)類型。由于我們從下標1開始存儲堆中元素，所以在確定MaxSize的大小時應(yīng)比實際使用值大1。

typedefstructminheap{intSize,MaxHeap;TElements[MaxSize];}MinHeap;堆中元素順序存儲在一維數(shù)組中，數(shù)組元素具有可比較大小的類型。

3.向下調(diào)整和建堆運算在實現(xiàn)建堆運算之前，我們先討論堆的向下調(diào)整運算AdjustDown。AdjustDown運算的定義如下：

voidAdjustDown(Theap[],intr,intn)設(shè)(heap[r+1],…,heap[n])這n－r個位置上的元素已滿足heap[i]≤heap[2i]且heap[i]≤heap[2i+1](i=r+1,r+2,…,

n/2

)的條件，則加入heap[r]后，使(heap[r],heap[r+1],…,heap[n])這n－r+1個位置上的元素滿足堆的條件。

實現(xiàn)運算AdjustDown的方法是：向下調(diào)整heap[r]，設(shè)temp＝heap[r]，如果temp大于其左、右孩子中的較小者(即heap[2r]和heap[2r+1]中的較小的元素)，則將temp與該較小元素交換，調(diào)整后繼續(xù)將temp與它的左、右孩子中較小者比較；如果temp比較小的孩子的值大，再作交換，直到不再需要調(diào)整，或到達堆的底部為止。圖6－22是AdjustDown運算的例子。圖中，heap[3],heap[4],…，heap[9]已滿足堆的條件，即heap[i]不大于heap[2i]和heap[2i+1]中的較小者，i=3，4?，F(xiàn)調(diào)整heap[2]，調(diào)整過程見圖6－22。圖6－22向下調(diào)整算法舉例

(a)調(diào)整前r=2；(b)92與18比較；(c)92與50比較；(d)保存92

建堆運算CreateHeap完成將一個以任意次序排列的元素序列，通過向下調(diào)整運算建成最小堆的功能。由于所有的葉子結(jié)點沒有孩子，它們自然無須調(diào)整。調(diào)整從位置為(n/2(的元素開始，每次被調(diào)整的元素下標減1，重復(fù)調(diào)用AdjustDown函數(shù)，直到下標為1的元素調(diào)整后，建堆運算結(jié)束。向下調(diào)整和建堆運算的C語言程序見程序6－14。建堆運算的例子見表6－1。為了便于理解，讀者也可使用如圖6－22所示的完全二叉樹形式來表示表6－1所描述的建堆過程。表6－1建堆舉例【程序6－14】向下調(diào)整和建堆運算。voidAdjustDown(Theap[],intr,intn){intchild=2*r;Ttemp=heap[r];

while(child<=n){if(child<n&&heap[child]>heap[child+1])child++;if(temp<=heap[child])break;heap[child/2]=heap[child];child*=2;}heap[child/2]=temp;}voidCreateHeap(MinHeap*hp){inti,n=hp->Size;for(i=n/2;i>0;i--)AdjustDown(hp->Elements,i,n);}6.4.2優(yōu)先權(quán)隊列堆是實現(xiàn)優(yōu)先權(quán)隊列的有效的數(shù)據(jù)結(jié)構(gòu)。如果假定最小值是最高優(yōu)先權(quán)，我們使用最小堆，否則使用最大堆。這里使用最小堆。從優(yōu)先權(quán)隊列中刪除最高優(yōu)先權(quán)的元素的操作是容易實現(xiàn)的。由于堆頂元素是堆中具有最小值的元素，我們只需取出和刪除堆頂元素即可。當(dāng)然，刪除堆頂元素后，必須將堆中剩余元素重新調(diào)整成堆。將新元素插入隊列后，也必須重新調(diào)整，使之成為堆。1.優(yōu)先權(quán)隊列ADT我們先來定義優(yōu)先權(quán)隊列的抽象數(shù)據(jù)類型，見ADT6－2PQueue。ADT6－2PQueue{數(shù)據(jù)：

n≥0個元素的MinHeap。運算：

voidCreatePQ(PQueue*pq,intmaxsize);

構(gòu)造一個空優(yōu)先權(quán)隊列。

BOOLIsEmpty(PQueuepq)

若優(yōu)先權(quán)隊列為空，則返回TRUE，否則返回FALSE。

BOOLIsFull(PQueuepq)若優(yōu)先權(quán)隊列已滿，則返回TRUE，否則返回FALSE。

voidAppend(PQueue*pq,T