數(shù)據(jù)結構第4章

第4章樹

本章學習最常用的非線性數(shù)據(jù)結構之一—樹，特別是二叉樹的基本表示和操作方法。

1JYP4.1樹和森林的概念及其表示

層次關系：家譜中的雙親子女關系組織中的上下級關系計算機文件系統(tǒng)中的目錄與子目錄關系表達式中的括號嵌套關系，等等對這些關系及相關對象進行抽象，就形成了計算機科學中最重要的數(shù)據(jù)結構之一樹。2JYP定義：一棵樹是由一個或多個結點組成的有限集合，且其中（1）存在一個稱為根的特定結點；（2）剩余結點被劃分為n≥0個不相交集合T1,…,Tn，且Ti（1≤i≤n）也是一棵樹。T1,…,Tn稱為根結點的子樹。這里使用了遞歸定義。一棵樹中的每一個結點都是整個樹的某一子樹的根。根結點同其子樹的關系可以通過這些子樹的根描述。3JYP如果允許樹的結點個數(shù)為零個，并將具有零個結點的樹定義為空樹，那么樹的子樹可以有無限個，這顯然是不合理的。一個結點包含數(shù)據(jù)項和指向其它結點的分枝信息。通常將樹根畫在頂層，再逐層畫出子樹，這與自然界生長的樹正好相反。下一頁給出了一棵具有13個結點的樹，為了簡單起見，每個數(shù)據(jù)項用一個字母表示并用該字母標識結點，樹根是A。4JYP5JYP一個結點的子樹個數(shù)稱為該結點的度。結點A的度是3，C的是1，G的是零。度為零的結點稱為葉結點或終端結點。K，L，F(xiàn)，G，M，I，J是葉結點。其它結點為非終端結點。結點X的子樹的根是X的子女。X是其子女的雙親。D的子女是H，I和J；D的雙親是A。同一個雙親的子女是兄弟。H，I和J是兄弟。一個結點的祖先是從根到該結點所經(jīng)過的所有結點。M的祖先是A，D和H。一棵樹的度是樹中結點的度的最大值。圖4.1的樹的度為3。6JYP結點的層次遞歸定義為：根結點的層次為1，任何其它結點的層次為其雙親結點的層次加1。圖4.1給出了樹中各結點的層次。一棵樹的高度或深度定義為樹中結點的層次的最大值。圖4.1的樹的高度為4。

定義：一個森林是由n≥0個不相交的樹T1,…,Tn構成的集合。森林和樹的概念密切相關，因為刪除一棵樹的根就得到森林，而一棵樹是一個森林中的一分子。7JYP可以用和廣義表類似的方法表示樹。例如，圖4.1的樹可寫為A(B(E(K,L),F),C(G),D(H(M),I,J))即，根結點后面是與其子女對應的森林。該樹的鏈表表示下圖所示：8JYP度為k的樹稱為k叉樹。可以直接用含k個子女字段的結點結構表示k叉樹的結點，每個子女字段指向相應的子女結點，但這會造成存儲資源的很大浪費。

引理4.1：如果用含k個子女字段的結點表示一棵具有n（n≥1）個結點的k叉樹，則n(k–1)+1個子女字段的值是0。

證明：由于每個非0子女字段指向一個結點，且除了根結點以外，每個結點正好與一個指針對應，所以具有n個結點的樹中非0子女字段數(shù)是n–1。具有n個結點的k叉樹共有nk個子女字段，因此，0子女字段數(shù)為nk–(n–1)=n(k–1)+1。9JYP將k限定為2，則得到二叉樹。這時，結點的空間代價較小，且有利于深入研究其特性和設計有效算法。二叉樹結點的兩個子女字段：

LeftChild

RightChild

由于k叉樹的每個結點最多只有一個最左子女，且該結點最多只有一個緊鄰右兄弟，因此，可以用LeftChild指向結點的最左子女，用RightChild指向該結點的緊鄰右兄弟，從而可以用二叉樹結點表示一般的k叉樹。10JYP例如，圖4.1的樹可用二叉樹結點表示為右邊的形式：我們將重點研究二叉樹。

11JYP4.2二叉樹

4.2.1二叉樹定義由于二叉樹最多只有兩個分枝，因此可擴展一般樹的概念，允許二叉樹為空，同時區(qū)分左、右子樹，從而簡化二叉樹的遞歸定義。

定義：一棵二叉樹是結點的有限集合，該集合或者為空，或者由一個根結點和兩個互不相交的子二叉樹組成，這兩個子樹分別稱為左、右子樹。注意，由于二叉樹只有左、右兩個子樹，允許二叉樹為空不會導致根結點有無限個子樹。12JYP二叉樹的抽象數(shù)據(jù)類型ADT4.1為：template<classType>

classBinaryTree{//對象：結點的有限集合，或為空，或 //由根結點和左、右子BinaryTree構成public:

BinaryTree(); //創(chuàng)建一個空二叉樹

BooleanIsEmpty();//判斷二叉樹是否為空BinaryTree(BinaryTreebt1,Element<Type>item,BinaryTreebt2);//創(chuàng)建一個二叉樹，其//左子樹為bt1,右子樹為bt2,根結點的數(shù)據(jù)項為item

BinaryTreeLchild();//若IsEmpty()為TRUE返回出錯信 //息，否則返回*this的左子樹13JYP

Element<Type>Data();//若IsEmpty()為TRUE返回出錯信//息，否則返回*this的根結點的數(shù)據(jù)項

BinaryTreeRchild();//若IsEmpty()為TRUE返回出錯信//息，否則返回*this的右子樹};14JYP按定義，非空二叉樹才屬于一般樹。此外，二叉樹區(qū)分子女的順序，而樹卻不區(qū)分。因此，下面的兩棵二叉樹是不同的，第一棵的右子樹為空，而第二棵的左子樹為空。但作為一般樹，兩者是相同的。關于樹的術語也適用于二叉樹。15JYP4.2.2二叉樹性質(zhì)

引理4.2[最大結點數(shù)]：（1）二叉樹第i層的最大結點數(shù)是2i-1，i≥1。（2）深度為k的二叉樹的最大結點數(shù)是2k–1，k≥1。證明：設Mi是第i層的最大結點數(shù)。（1）通過對層次i應用歸納法證明。當i=1，只有根結點，所以，Mi=2i-1=20=1。設i>1，并假設Mi-1=2i-2。二叉樹的每個結點最多有2個子女，因此Mi=2Mi-1，根據(jù)歸納假設，Mi=2*2i-2=2i-1。（2）深度為k的二叉樹的最大結點數(shù)是16JYP（2）深度為k的二叉樹的最大結點數(shù)是17JYP引理4.3[葉結點數(shù)與度為2的結點數(shù)之間的關系]：

對于任何非空二叉樹，若n0為葉結點數(shù)，n2為度為2的結點數(shù)，則n0=n2+1。證明：設n1為度為1的結點數(shù)，n為總結點數(shù)。由于二叉樹的結點度數(shù)最多為2，所以 n=n0+n1+n2 (4.1)設B為分枝數(shù)，由于除了根結點以外，每個結點正好由一個分枝引出，所以n=B+1。所有分枝出自度為1或2的結點，所以B=n1+2n2，從而有 n=n1+2n2+1 (4.2)(4.1)–(4.2)并整理可得n0=n2+118JYP

定義：深度為k（k≥0）的滿二叉樹是具有2k–1個結點的二叉樹。下圖是一棵深度k=4的滿二叉樹。19JYP其中，結點從1到2k–1編號，從第1層開始，后接第2層，直至第k層。每層從左到右。通過這種編號方式，可定義完全二叉樹。

定義：深度為k（k≥0）且結點個數(shù)為n的二叉樹是完全二叉樹當且僅當其結點與深度為k的滿二叉樹的1到n號結點一一對應。根據(jù)引理4.2，具有n個結點的完全二叉樹的高度為log2(n+1)。此外，完全二叉樹的的葉結點都在相鄰的層次上。

20JYP另一種特殊的二叉樹是偏斜樹，包括左、右兩種。下面分別是左偏斜樹和完全二叉樹的例子：21JYP4.2.3二叉樹表示1數(shù)組表示按照完全二叉樹的編號規(guī)則，可以用一維數(shù)組存儲二叉樹的結點。引理4.4：如果順序表示具有n個結點的完全二叉樹，那么對于任何下標為i（1≤i≤n）的結點，有（1）若i1，則結點i的雙親位于i/2；若i=1，則結點i是根，無雙親。（2）若2i≤n，則結點i的左子女位于2i，否則i沒有左子女。（3）若2i+1≤n，則i的右子女位于2i+1，否則i沒有右子女。22JYP證明：只需證明（2）。由（2）和在同一層從左到右編號的規(guī)則即可推出（3）。（1）是（2）和（3）的自然結論。下面仍然通過對i應用歸納法證明（2）。當i=1，顯然結點i的左子女位于2，除非2>n，而這時結點i沒有左子女。假設對所有j（1≤j≤i），結點j的左子女位于2j。由于緊排在結點i+1的左子女前面的是結點i的右、左子女，根據(jù)歸納假設，結點i的左子女位于2i，因此，結點i+1的左子女位于2i+2=2(i+1)，除非2(i+1)>n，而這時結點i+1沒有左子女。23JYP這種表示方法可用于所有二叉樹，但大多數(shù)情況下空間利用率較低。顯然，數(shù)組表示對完全樹是最理想的，對于偏斜樹，空間利用率最低。最壞情況下，深度為k的右偏斜樹需要2k–1個空間單元，但其中只有k個用于存放數(shù)據(jù)。24JYP2鏈接表示數(shù)組表示法對于很多二叉樹空間浪費過大，而且還存在順序表示的固有缺點，即在樹的中間插入和刪除結點需要移動大量其它結點。在鏈接表示中，每個結點有三個字段：

LeftChilddata

RightChild。25JYPclassTree; //向前聲明classTreeNode{friendclassTree;private:

TreeNode*LeftChild;chardata;TreeNode*RightChild;};classTree{public:

//二叉樹操作…private:TreeNode*root; //樹的根結點指針};26JYP上一小節(jié)的左偏斜樹和完全二叉樹的鏈表表示如下所示：

27JYP4.3二叉樹遍歷與樹游標

二叉樹遍歷是最基本的操作。一次完整的遍歷可產(chǎn)生樹中結點的一個線性序列。設L，V和R分別表示在位于一個結點時移到左子女、訪問結點數(shù)據(jù)和移到右子女，并規(guī)定從左到右遍歷。存在三種遍歷：LVR，VLR和LRV，分別稱為中序、前序和后序遍歷。例如，在前序中，先訪問結點再遍歷其左、右子樹，而在后序中，先遍歷結點的左、右子樹再訪問結點。28JYP考慮下面的二叉樹，該樹表示表達式A/B*C+D。29JYP其中，每個含操作符的結點的左、右子樹分別表示該操作符的左、右操作數(shù)。下面將以此樹為例，說明各種遍歷產(chǎn)生的結果。30JYP4.3.1中序遍歷

設T為一棵二叉樹，T的中序遍歷可遞歸定義為：（1）若T為空，返回；（2）中序遍歷T的左子樹；（3）訪問T的根結點；（4）中序遍歷T的右子樹。由此可得中序遍歷的遞歸算法，如下一頁所示。31JYPvoidTree::inorder(){//驅(qū)動器，作為Tree的公有成員函數(shù)

inorder(root);}voidTree::inorder(TreeNode*CurrentNode){//遞歸核心， //作為Tree的私有成員函數(shù)if(CurrentNode){

inorder(CurrentNodeLeftChild);cout<<CurrentNodedata;

inorder(CurrentNodeRightChild);}}32JYP對圖4.10的二叉樹調(diào)用inorder(TreeNode*)的執(zhí)行過程如下，輸出是：A/B*C+D，這正好是表達式的中綴。33JYP4.3.2前序遍歷

設T為一棵二叉樹，T的前序遍歷可遞歸定義為：（1）若T為空，返回；（2）訪問T的根結點；（3）前序遍歷T的左子樹；（4）前序遍歷T的右子樹。由此可得前序遍歷的遞歸算法，如下一頁所示。對圖4.10的二叉樹，其輸出是：+*/ABCD，這正好是表達式的前綴。34JYPvoidTree::preorder(){//驅(qū)動器，作為Tree的公有成員函數(shù)

preorder(root);}voidTree::preorder(TreeNode*CurrentNode){//遞歸核心， //作為Tree的私有成員函數(shù)if(CurrentNode){cout<<CurrentNodedata;

preorder(CurrentNodeLeftChild);

preorder(CurrentNodeRightChild);}}35JYP4.3.3后序遍歷

設T為一棵二叉樹，T的后序遍歷可遞歸定義為：（1）若T為空，返回；（2）后序遍歷T的左子樹；（3）后序遍歷T的右子樹；（4）訪問T的根結點。由此可得后序遍歷的遞歸算法，如下一頁所示。對圖4.10的二叉樹，其輸出是：AB/C*D+，這正好是表達式的后綴。36JYPvoidTree::postorder(){//驅(qū)動器，作為Tree的公有成員函數(shù)postorder(root);}voidTree::postorder(TreeNode*CurrentNode){//遞歸核心， //作為Tree的私有成員函數(shù)if(CurrentNode){

postorder(CurrentNodeLeftChild);

postorder(CurrentNodeRightChild);cout<<CurrentNodedata;}}37JYP4.3.4中序游標

樹作為一種容器類也可以通過游標遍歷。為此，首先需要將遍歷算法轉(zhuǎn)變?yōu)榉沁f歸型的。觀察中序遍歷的過程，CurrentNode從樹根一直沿著左子女下移，直到CurrentNode為空為止。接著回溯到雙親結點，“訪問”結點，然后轉(zhuǎn)移到右子女，再繼續(xù)上述過程。因此，可以在沿著左子女下移過程中用棧保存所經(jīng)歷的結點，實現(xiàn)遞歸到非遞歸的轉(zhuǎn)換，所得非遞歸中序遍歷算法如下一頁所示。

38JYP1voidTree::NonrecInorder(){//利用棧實現(xiàn)非遞歸中序遍 //歷，設模板類Stack已定義并實現(xiàn)Stack<TreeNode*>s;//聲明并初始化棧3TreeNode*CurrentNode=root;4while(1){ 5while(CurrentNode){ //沿著左子女下移6

s.Add(CurrentNode); //加入棧中7

CurrentNode=CurrentNodeLeftChild;8}9If(!s.IsEmpty()){ //棧不空10

CurrentNode=*s.Delete(CurrentNode);//從棧中刪除11

cout

<<CurrentNodedata<<endl;//訪問結點12

CurrentNode=CurrentNodeRightChild;//轉(zhuǎn)到右子女13}39JYP14elsebreak;15}16}分析：設樹中結點個數(shù)為n。每個結點進棧一次，所以第6到7行和第10到12行共執(zhí)行n次。對于每個0指針，CurrentNode將成為0一次，共2n0+n1=n0+n1+n2+1=n+1次。因此，算法的時間復雜性是O(n)。所需要的棧空間與樹的深度成線性關系。40JYP函數(shù)Tree::NonrecInorder第4到15行的while循環(huán)的每次迭代都產(chǎn)生中序遍歷的下一個元素，由此很容易實現(xiàn)中序遍歷二叉樹的游標。中序游標類InorderIterator的定義如下：classInorderIterator{public:char*next();

InorderIterator(Treetree):t(tree){CurrentNode=t.root;};private:

Treet;

Stack<TreeNode*>s;

TreeNode*CurrentNode;};41JYP其中，假設InorderIterator是類TreeNode和Tree的友元。數(shù)據(jù)成員變量s和CurrentNode記載游標的內(nèi)部狀態(tài)。構造函數(shù)使游標和需遍歷的二叉樹相關聯(lián)，并完成必要的初始化。42JYPNext()的實現(xiàn)基本與函數(shù)Tree::NonrecInorder()第4到15行的while循環(huán)的一次迭代對應：char*InorderIterator::Next(){while(CurrentNode){

s.Add(CurrentNode);

CurrentNode=CurrentNodeLeftChild;}if(!s.IsEmpty()){

CurrentNode=*s.Delete(CurrentNode);char&temp=CurrentNodedata;

CurrentNode=CurrentNodeRightChild;return&temp;}elsereturn0; //樹已遍歷完，沒有更多元素了}43JYP4.3.5后序游標

后序游標可在中序游標的基礎上實現(xiàn)。但后序遍歷與中序遍歷不同，從左子女回溯時還不能訪問結點元素，只有從右子女回溯時才能訪問結點元素。因此，需要標識棧內(nèi)結點的右子女是否被遍歷。為此，可將棧模板實例化為如下類型：structStackItem{

TreeNode*p;

BooleanRCVisited; //RCVisited==TRUE表示回溯到結點p //時，其右子女已遍歷};44JYP后序游標類PostorderIterator的定義如下，其中同樣假設PostorderIterator是類TreeNode和Tree的友元。

classPostorderIterator{public:

char*next();

PostorderIterator(Treetree):t(tree){CurrentNode=t.root;};private:Treet;Stack<StackItem>s;TreeNode*CurrentNode;};45JYP實現(xiàn)Next()需注意標識棧內(nèi)結點的右子女是否被遍歷，且只返回右子女已被遍歷的結點的元素，如下所示：char*PostorderIterator::Next(){

StackItemitem;while(1){while(CurrentNode){ //沿著左子女下移

item.p=CurrentNode;

item.RCVisited=FALSE;

s.Add(item); //首次進棧

CurrentNode=CurrentNodeLeftChild;}if(!s.IsEmpty()){ //棧不空

item=*s.Delete(item); //從棧中刪除46JYP

CurrentNode=item.p;if(item.RCVisited=FLASE){ //從左子女回溯

item.RCVisited=TRUE;//下次回溯時，右子女已遍歷

s.Add(item); //再次進棧CurrentNode=CurrentNodeRightChild;//轉(zhuǎn)向右子女}else{ //從右子女回溯

char&temp=CurrentNodedata;CurrentNode=0;//下次執(zhí)行時將再從棧中刪取結點return&temp;}}elsereturn0; //樹已遍歷完，沒有更多元素了}47JYP4.3.6按層次遍歷

按層次遍歷按照完全二叉樹編號順序訪問結點，即，先訪問根，接著訪問根的左、右子女，如此繼續(xù)，在每一層，都從最左結點到最右結點進行訪問。從樹根開始，將所訪問結點的左、右子女存入隊列，再逐個取出處理，即可實現(xiàn)按層次遍歷。48JYPvoidTree::LevelOrder(){ //按層次遍歷二叉樹，設模板類 //Queue已定義并實現(xiàn)

Queue<TreeNode*>q; //聲明并初始化隊列

TreeNode*CurrentNode=root;while(CurrentNode){cout<<CurrentNodedata<<endl;if(CurrentNodeLeftChild)q.Add(CurrentNodeLeftChild);if(CurrentNodeRightChild)q.Add(CurrentNodeRightChild);

CurrentNode=*q.Delete(CurrentNode);}}49JYP

由于一個結點的子女處于下一層，且左子女先于右子女存入隊列，所以結點元素以按層次遍歷的順序輸出。對于圖4.10的二叉樹，該算法輸出的結點數(shù)據(jù)序列是：+*D/CAB。50JYP4.4滿足性問題

給定一個由布爾變量x0,x1,…,xn-1（n≥1）構成的命題演算的公式f(x0,x1,…,xn-1)，滿足性問題要求判斷是否存在x0,x1,…,xn-1的一個賦值，使得f為TRUE。假設公式已表示為二叉樹，例如，(x0

x1)(x0

x2)

x2可表示為下一頁的二叉樹。51JYP52JYP求解滿足性問題的最直接方法是對x0,x1,…,xn-1的每一個取值組合，計算公式的值。如果用布爾數(shù)組x存放x0,x1,…,xn-1，則借助例1.11中BinaryAddOne的思想，可生成n個變量的2n種取值組合。計算公式的值可通過后序遍歷相應的二叉樹實現(xiàn)。為便于得到變量當前取值，樹的葉結點改為存放變量的下標。如下一頁所示。

53JYP54JYP為了簡化設計，分別用–3，–2和–1表示，和，于是樹結點和樹可定義如下：enumBoolean{FALSE,TRUE};classSatTree; //向前聲明classSatNode{friendclassSatTree;private:SatNode*LeftChild;

intdata;SatNode*RightChild;};

55JYPclassSatTree{public:BooleanSatisfiability();//公式可滿足則返回TRUE，并打 //印變量的取值組合，否則返回FALSEprivate:SatNode*root;Boolean*x;

intn; //變量個數(shù)BooleanPostOrderEval(SatNode*);BooleanNextCombination();};56JYP函數(shù)NextCombination生成變量的下一個取值組合，當變量取值已全部為TRUE時，返回FALSE，否則返回TRUE。BooleanSatTree::NextCombination(){inti=n-1;

while(x[i]==TRUE&&i>=0){x[i]=FALSE;i--;

}

if(i>=0){x[i]=TRUE;

returnTRUE;}

elsereturnFALSE; //變量取值已經(jīng)全部為TRUE}

57JYP函數(shù)Satisfiability對x=(FALSE,FALSE,…,FALSE)，計算公式的值，若為TRUE則成功返回。否則繼續(xù)生成下一個取值組合，直到計算完取值組合(TRUE,TRUE,…,TRUE)為止。BooleanSatTree::Satisfiability(){ inti;

x=newBoolean[n];

for(i=0;i<n;i++)x[i]=FALSE;do{ //由于n≥1，所以此循環(huán)至少迭代2次

if(PostOrderEval(root)==TRUE){for(i=0;i<n;i++)cout<<x[i]; //輸出取值組合

delete[]x;x=0;returnTRUE; //滿足}}while(NextCombination());58JYPdelete[]x;

x=0;returnFALSE; //不可滿足}59JYP函數(shù)PostOrderEval后序遍歷計算公式的值。BooleanSatTree::PostOrderEval(SatNode*s){BooleanleftValue,rightValue;if(s){leftValue=PostOrderEval(sLeftChild);rightValue=PostOrderEval(sRightChild);switch(sdata){case-3:return!rightValue; //操作符case-2:returnleftValue&&rightValue;//操作符

case-1:returnleftValue||rightValue; //操作符

default:returnx[sdata]; //變量下標

}}returnFALSE; //空樹的值為FALSE}60JYP由于有2n種取值組合，每次計算公式的時間為O(n)，生成下一個取值組合的平均時間為O(1)，所以最壞情況下，算法的時間復雜性是O(n2n)。61JYP4.5線索二叉樹

4.5.1線索在二叉樹的鏈接表示中，0指針的個數(shù)為2n0+n1=n+1，占總指針數(shù)2n的一半還多。可用一種稱為線索的指向樹中其它結點的指針取代0指針。這些線索的構造規(guī)則為：（1）若結點p的RightChild字段值為0，則令其指向p的中序后繼；（2）若結點p的LeftChild字段值為0，則令其指向p的中序前趨。將二叉樹中的0指針替換為線索（用虛線表示）后得到線索二叉樹。62JYP下面是一個線索二叉樹的例子，其中結點E的左線索和右線索分別指向其中序前趨B和中序后繼A。圖4.1463JYP為了區(qū)分線索和普通指針，在結點中增加兩個Boolean字段：

LeftThread

RightThread對于結點t，若tLeftThread==TRUE，則tLeftChild存放線索，否則存放左子女指針。右子女情況也類似。64JYP線索二叉樹及其結點和中序游標的類定義：classThreadedTree;classThreadedInorderIterator;classThreadedNode{friendclassThreadedTree;friendclassThreadedInorderIterator;private:BooleanLeftThread;ThreadedNode*LeftChild;chardata;ThreadedNode*RightChild;BooleanRightThread;};65JYPclassThreadedTree{friendclassThreadedInorderIterator;public://樹操作…private:ThreadedNode*root;};66JYPclassThreadedInorderIterator{public:char*Next();voidInorder();ThreadedInorderIterator(ThreadedTreetree):t(tree)

{CurrentNode=t.root;};private:ThreadedTreet;ThreadedNode*CurrentNode;};67JYP由于中序第一結點沒有前趨，最后一個結點沒有后繼，致使這兩個結點的左、右線索無定義，如圖4.14中結點H和G所示。為此，引入一個頭結點，使原樹作為其左子樹，并使頭結點的RightChild作為普通指針指向其本身。圖4.15表示帶頭結點的空樹。68JYP圖4.14的線索二叉樹加頭結點后如圖4.16:69JYP不難看出，原樹的中序第一個結點是頭結點的后繼，最后一個結點是頭結點的前趨。70JYP4.5.2中序遍歷線索二叉樹

通過線索，可以不用?；蜻f歸實現(xiàn)中序遍歷。對于二叉樹的任何結點x，若xRightThread==TRUE，則x的中序后繼是xRightChild。否則，x的中序后繼可沿x的右子女的LeftChild鏈尋找，找到字段LeftThread==TRUE的結點即可。函數(shù)Next（程序4.14）返回線索二叉樹中結點CurrentNode的中序后繼。

71JYP函數(shù)Next返回線索二叉樹中結點CurrentNode的中序后繼：char*ThreadedInorderIterator::Next(){

ThreadedNode*temp=CurrentNodeRightChild;

if(!CurrentNodeRightThread)

while(!tempLeftThread)temp=tempLeftChild;CurrentNode=temp;if(CurrentNode==t.root)return0; //頭結點

elsereturn&CurrentNodedata;}

72JYP利用Next函數(shù)，并注意到原樹的中序第一個結點是頭結點的后繼，很容易得到線索二叉樹的中序遍歷函數(shù)Inorder：voidThreadedInorderIterator::Inorder(){CurrentNode=t.root;for(char*ch=Next();ch;ch=Next())//注意，當 //CurrentNode==t.root,Next()返回中序第一元素

cout<<*ch<<endl;}

由于每個結點最多被訪問兩次，所以對于n個結點的線索二叉樹，中序遍歷的計算時間是O(n)。73JYP4.5.3后序遍歷線索二叉樹

不用棧或遞歸后序遍歷線索二叉樹比其它遍歷更復雜一些。在后序遍歷中，當首次到達一個結點時，先遍歷其左子樹；接著返回該結點再遍歷其右子樹；只有在第三次到達該結點的時候，才真正訪問結點的數(shù)據(jù)。為此，使用enumAction{GOLEFT,GORIGHT,VISITNODE};

表示結點處理的不同階段。74JYP訪問完結點p后，必須定位p的雙親q，并確定q所處的處理階段。定位p的雙親q如下圖所示：75JYP

由上圖可得函數(shù)Parent：ThreadedNode*ThreadedTree::Parent(ThreadedNode*p, Action*nextaction){ //假設p0 //返回p的雙親q；若p是q的左子女，*nextaction= //GORIGHT；否則*nextaction=VISITNODEThreadeNode*q=p;doq=qRightChild;while(!qRightThread); //定位p子樹 //最右結點的中序后繼

if(q==root)*nextaction=VISITNODE;//無后繼，p不可 //能是左子女

elseif(qLeftChild==p)*nextaction=GORIGHT;//p是q //的左子女

else*nextaction=VISITNODE;//p是其雙親的右子女76JYP

if(*nextaction==VISITNODE&&q!=root){ //p不是q的 //左子女，尋找以p為根的子樹最左結點 //的中序前趨，該前趨即p的雙親q=p;doq=qLeftChild;while(!qLeftThread);}returnq;}77JYP利用函數(shù)Parent，可得到后序遍歷線索二叉樹的算法：voidThreadedTree::PostOrder(){Actionnextaction=GOLEFT;ThreadedNode*p=rootLeftChild; //頭結點的左子女 //是原樹的根

while(p!=root)

switch(nextaction){caseGOLEFT: //遍歷非空左子樹

if(!pLeftThread)p=pLeftChild;

elsenextaction=GORIGHT;break;78JYP

caseGORIGHT: //遍歷非空右子樹

if(!pRightThread){p=pRightChild;nextaction=GOLEFT;}elsenextaction=VISITNODE;break;caseVISITNODE:

cout<<pdata;p=Parent(p,&nextaction);break;}}79JYP在線索二叉樹的后序遍歷基礎上，也可以定義后序遍歷游標：classThreadedPostorderIterator{public:char*First();char*Next(Boolean);voidPostorder();

ThreadedPostorderIterator(ThreadedTreetree):t(tree)

{CurrentNode=t.rootLeftChild;};private:

ThreadedTreet;

ThreadedNode*CurrentNode;

ThreadedNode*Parent(ThreadedNode*,Action*);//同前};80JYP其中，假設ThreadedPostorderIterator是類ThreadedNode和ThreadedTree的友元。函數(shù)Next的設計：為了利用后序遍歷的控制結構尋找CurrentNode的后序后繼，需將CurrentNode的處理階段設置為VISITNODE。當首次到達switch控制的VISITNODE分枝時，需通過Parent和循環(huán)迭代尋找CurrentNode的后序后繼。再次到達VISITNODE分枝時，CurrentNode的后序后繼已確定。81JYP實現(xiàn)函數(shù)First可利用函數(shù)Next，但從First調(diào)用Next時的處理與一般處理不同，因此在函數(shù)Next中用參數(shù)fromfirst表示是否由First調(diào)用。函數(shù)Next的實現(xiàn)如下：char*ThreadedPostorderIterator::Next(Boolean

fromFirst){

//fromFirst==TRUE表示由First()調(diào)用BooleanfirstVisit=TRUE;//用于Next(FALSE)，首次到達 //VISITNODE分枝后置為FALSEActionnextAction=VISITNODE; //通過VISITNODE分枝尋 //找CurrentNode的后序后繼

if(fromFirst==TRUE){ //由First()調(diào)用，特殊處理

nextAction=GOLEFT;

firstVisit=FALSE;}

82JYPwhile(CurrentNode!=t.root)

switch(nextaction){caseGOLEFT:

if(!CurrentNodeLeftThread)CurrentNode=CurrentNodeLeftChild;

elsenextAction=GORIGHT;break;

caseGORIGHT:

if(!CurrentNodeRightThread){

CurrentNode=CurrentNodeRightChild;

nextAction=GOLEFT;}elsenextAction=VISITNODE;break;83JYP

caseVISITNODE:

if(firstVisit==TRUE){CurrentNode=Parent(CurrentNode,&nextaction);firstVisit=FALSE;

}elsereturn&CurrentNodedata;break;}}return0; //無后繼}

84JYP通過調(diào)用函數(shù)Next，很容易實現(xiàn)函數(shù)First和Postorder，如下所示：char*ThreadedPostorderIterator::First(){ //若原樹為空，返 //回0，否則將CurrentNode設置為后序第一結點

CurrentNode=t.rootLeftChild;returnNext(TRUE);}voidThreadedPostorderIterator::Postorder(){for(char*ch=First();ch;ch=Next(FALSE))cout<<*ch<<endl;}85JYP4.5.4將結點插入線索二叉樹

插入結點是構造線索二叉樹的主要途徑。此處將只研究將結點r作為結點s的右子女插入的情況。這又分兩種情況：（1）s的右子樹為空，插入比較簡單，如下圖：86JYP（2）s的右子樹不空，插入后該右子樹成為r的右子樹。s原來的中序后繼變?yōu)閞的中序后繼，如下圖：87JYP假設函數(shù)InorderSucc(r)返回r的中序后繼，函數(shù)InsertRight實現(xiàn)了上述插入過程：voidThreadedTree::InsertRight(ThreadedNode*s, ThreadedNode*r){//r作為s的右子女插入rRightChild=sRightChild;//見前圖(1)，注意s!=t.root

rRightThread=sRightThread;

rLeftChild=s;rLeftThread=TRUE; //見前圖(2)

sRightChild=r;sRightThread=FALSE;//見前圖(3)if(!rRightThread){

ThreadedNode*temp=InorderSucc(r); //見前圖(4)

tempLeftChild=r;}}88JYP4.6選擇樹

歸并段是記錄的有限序列，且這些記錄按關鍵字的非遞減順序排列。假設需要將k個歸并段歸并為一個，這可通過反復輸出關鍵字最小的記錄完成。最小關鍵字可能在k個歸并段的前端記錄的任何一個之中，因此需要從k種可能中選出最小。最直接的方法是作k–1次比較。但對于k>2，如果利用上一次比較獲得的知識，就可以使本次及以后比較的次數(shù)減少。選擇樹就是一種能夠記載上一次比較獲得的知識的數(shù)據(jù)結構。選擇樹是一棵完全二叉樹，有勝者樹和敗者樹兩種。

89JYP4.6.1勝者樹

勝者樹的構造與錦標賽類似，勝者是關鍵字較小的記錄。每個非葉結點表示比賽的勝者，根結點表示總勝者，即樹中關鍵字最小的結點。

作為完全樹，勝者樹可用順序方法表示。每個葉結點表示相應歸并段的第一個記錄。由于記錄一般較大，每個結點實際存放的是其所表示記錄的緩沖區(qū)下標。設buf[i]存放歸并段i（0≤i<k）的第一個記錄，則buf[i]對應的葉結點編號是k+i，這意味著葉結點存放的下標可推算得到，不必用空間存儲。90JYP下圖是一棵k=8的勝者樹：91JYP其中，每個結點旁的數(shù)字是該結點的順序編號。雖然每個非葉結點實際存放勝者記錄下標，但為便于直觀比較，圖中也給出了勝者的關鍵字。葉結點直接用buf[i]代替。由根結點指向的記錄（buf[3]）的關鍵字最小，可輸出。歸并段3的下一個記錄進入buf[3]，其關鍵字為15。為了重構勝者樹，需要沿buf[3]對應的葉結點到根結點進行一系列比賽。結點10和11比賽的勝者又是結點11（15<20），結點4和5比賽的勝者是結點4（9<15），結點2和3比賽的勝者是結點3（8<9）。92JYP新的勝者樹如下圖：93JYP其中，粗體字結點是發(fā)生了變化的結點?？梢姡荣愂窃谛值芙Y點之間進行，結果存放在它們的雙親結點中。新一輪比賽在下一個更靠近根的層次進行。分析：除去葉結點層，樹的層數(shù)為log2(k+1)，所以重構樹的時間為O(log2k)。對于每一個歸并到輸出文件的記錄都需要重構樹，歸并n個記錄的時間是O(nlog2k)。建立初始勝者樹的時間是O(k)。因此，歸并k個歸并段的總時間是O(nlog2k)。94JYP4.6.2敗者樹

勝者樹重構的比賽是沿上次輸出的記錄緩沖區(qū)對應的葉結點到根的路徑，與兄弟結點進行的?？梢粤罘侨~結點指向比賽的敗者記錄而不是勝者記錄，從而簡化重構過程。非葉結點存放敗者記錄下標的選擇樹稱為敗者樹。實際上，結點p中的敗者是與結點p的兩個子女對應的比賽的勝者比賽的敗者。下一頁是與前面第一棵勝者樹對應的敗者樹。其中增加了結點0，用于表示整個比賽的勝者。95JYP與前面第一棵勝者樹對應的敗者樹96JYP輸出總勝者之后，重構可通過從結點11到結點1進行比賽實現(xiàn)。而且，雙親結點直接指明了需要比賽的對手?？赏ㄟ^先建立勝者樹構造初始敗者樹。假設記錄類型的定義為：structRec{intkey;其它數(shù)據(jù)部分;};97JYP敗者樹的類定義如下：classLoserTree{public:LoserTree(intk); //構造函數(shù)

voidBuild(); //建立初始敗者樹… //其它操作private:

intk;int*l; //非葉結點Rec*buf; //記錄緩沖區(qū)

intgetKey(inti);//返回結點i指向的記錄緩沖區(qū)中的關鍵字

intgetIndex(inti); //返回結點i存放的記錄緩沖區(qū)指針};98JYP構造函數(shù)的實現(xiàn)如下：LoserTree::LoserTree(intk){

l=newint[k]; //非葉結點空間buf=newRec[k]; //記錄緩沖區(qū)空間}

99JYP建立初始敗者樹的算法及相應輔助函數(shù)的實現(xiàn)如下：voidLoserTree::Build(){ //假設記錄緩沖區(qū)已輸入數(shù)據(jù)

inti;for(i=k–1;i>0;i--)

if(getKey(2*i)>getKey(2*i+1)l[i]=getIndex(2*i+1);

elsel[i]=getIndex(2*i); //自下而上建立勝者樹l[0]=l[1]; //總勝者

for(i=1;i<k;i++)

if(l[i]==getIndex(2*i)l[i]=getIndex(2*i+1);

elsel[i]=getIndex(2*i); //自上而下建立敗者樹}100JYPintLoserTree::getKey(inti){

if(i<k)returnbuf[l[i]].key;

elsereturnbuf[i-k].key;}intLoserTree::getIndex(inti){

if(i<k)returnl[i];

elsereturn(i–k);}顯然，建立初始敗者樹的計算時間是O(k)。

101JYP4.7森林的二叉樹表示及遍歷

下面是一個由三棵樹構成的森林：如果用二叉樹表示森林中的每一棵樹，再用根結點的RightChild字段將這些二叉樹鏈接起來，則可將整個森林表示為一棵二叉樹。102JYP例如，前面的森林可表示為下面的二叉樹。103JYP此轉(zhuǎn)換可形式化定義為：

定義：如果T1,…,Tn是一個森林，則與該森林對應的二叉樹（記為B(T1,…,Tn)）（1）若n=0則為空二叉樹。（2）具有與root(T1)等同的根，其左子樹為B(T11,T12,…,T1m)，其中T11,T12,…,T1m是root(T1)的子樹；其右子樹為B(T2,…,Tn)。

104JYP設T是與森林F對應的二叉樹。前序遍歷二叉樹T與前序遍歷森林F存在自然對應，森林F的前序遍歷定義為：（1）若F為空則返回；（2）訪問F的第一棵樹的根；（3）前序遍歷由第一棵樹的子樹構成的森林；（4）前序遍歷由其余樹構成的森林。105JYP中序遍歷二叉樹T與中序遍歷森林F存在自然對應，森林F的中序遍歷定義為：（1）若F為空則返回；（2）中序遍歷由F的第一棵樹的子樹構成的森林；（3）訪問第一棵樹的根；（4）中序遍歷由其余樹構成的森林。106JYP后序遍歷二叉樹T與后序遍歷森林F不存在自然對應，但我們可人為地將森林F的后序遍歷定義為：（1）若F為空則返回；（2）后序遍歷由F的第一棵樹的子樹構成的森林；（3）后序遍歷由其余樹構成的森林；（4）訪問第一棵樹的根。107JYP

森林的按層次遍歷從森林的所有樹的根所在層開始，逐層訪問，在每一層內(nèi)按照從左到右的順序訪問。這里森林作為一個整體看待，而不是遍歷完一棵樹再遍歷另一棵。顯然，按層次遍歷二叉樹T與按層次遍歷森林F一般不存在對應關系。108JYP4.8集合表示

4.8.1并查集假設集合元素為0,1,2,3,…,n–1。還假設所表示的集合之間互不相交，即，若Si和Sj（ij）是集合，則Si

Sj=。例如，當n=10，元素可劃分為三個不相交的集合：S1={0,6,7,8}，S2={1,4,9}和S3={2,3,5}。需要在這些集合上進行的操作是：（1）union(Si,Sj)：求Si和Sj的并（）。Si和Sj不再獨立存在，將被SiSj所取代。（2）find(i)：查找含元素i的集合。109JYP為了高效率實現(xiàn)以上操作，用樹表示集合。S1，S2和S3的表示如下：其中，每個集合用一棵樹表示，且分枝由子女指向雙親。110JYP實現(xiàn)并操作可直接使兩棵樹之一成為另一棵樹的子樹，這樣S1

S2可表示為下列兩種形式之一：111JYP如果每個集合名對應一個指針，使之指向表示該集合的樹的根，則上述操作很容易完成。此外，每個根也存放一個指向集合名的指針，這樣，當需要判斷一個元素屬于哪個集合時，可沿著子女到雙親的鏈接，定位于根，并確定集合名。112JYP集合S1，S2和S3的數(shù)據(jù)表示如下：以后將直接用樹根表示集合。于是，操作find(i)變?yōu)椋捍_定含元素i的樹的根；操作union(i,j)需要連接以i為根和以j為根的兩棵樹。113JYP由于集合元素為0,1,2,3,…,n–1，可以用數(shù)組parent[MaxElements]表示樹結點。數(shù)組的第i個位置表示元素i對應的樹結點。數(shù)組元素存放相應樹結點的雙親指針。下面是S1，S2和S3的數(shù)組表示，注意根結點的parent為–1。114JYP基于上述表示的集合的類定義和構造函數(shù)：classSets{public:

//集合操作…private:int*parent;intn; //集合元素個數(shù)};Sets::Sets(intsz=DefaultSize){

n=sz;

parent=newint[sz];for(inti=0;i<n;i++)parent[i]=-1;}115JYP實現(xiàn)find(i)只需簡單地沿著結點i的parent向上移動，直至到達parent值為–1的結點：intSets::SimpleFind(inti){ //找到含元素i的樹的根while(parent[i]>=0)i=parent[i];returni;}union(i,j)也很簡單，這里假設采用令第一棵樹為第二棵的子樹的策略：voidSets::SimpleUnion(inti,intj){//用以i為根和以j //（i!=j）為根的兩個不相交集合的并取代它們

parent[i]=j;}

116JYP對SimpleUnion和SimpleFind的分析：

這兩個算法雖然簡單，但性能卻不夠好。例如，假設一開始各集合只含一個元素，即Si={i}，0≤i<n。執(zhí)行以下操作序列：union(0,1),union(1,2),union(2,3),…,union(n–2,n–1),find(0),find(1),…,find(n–1)將生成下一頁所示的退化樹。117JYP該序列中的n–1個union共需O(n)時間。然而，每個find都需要從相應元素所在結點出發(fā)，沿parent指針找到根。從位于第i層的結點找到根結點需要O(i)時間，完成n個find共需O()O(n2)時間。118JYP可以通過避免生成退化樹來改善union和find操作的性能。為此，可以對union(i,j)操作應用以下權重規(guī)則：若以i為根的樹中結點數(shù)小于以j為根的樹中結點數(shù)，則令j成為i的雙親，否則令i成為j的雙親。當應用權重規(guī)則時，執(zhí)行前述union操作序列生成的樹如下一頁所示。其中，對union操作的參數(shù)作了適當修改，使其與樹根對應。119JYP120JYP為了實現(xiàn)權重規(guī)則，可利用根結點的parent字段以負數(shù)的形式存儲計數(shù)數(shù)據(jù)。由此可得基于權重規(guī)則的union算法：voidSets::WeightedUnion(inti,intj){//基于權重規(guī)則構造以i //和j為根的集合的并inttemp=parent[i]+parent[j];if(parent[j]<parent[i]){ //樹i的結點少

parent[i]=j;parent[j]=temp;}else{ //樹j的結點少或與樹i的同樣多

parent[j]=i;parent[i]=temp;}}121JYP對WeightedUnion和SimpleFind的分析：一次union操作的時間仍然是O(1)。find操作未變，其一次執(zhí)行所需要的最長時間可由以下引理4.5確定。引理4.5：假設開始時森林是由一組只含單個結點的樹構成的，并令T為一棵具有m個結點，且通過執(zhí)行一系列WeightedUnion函數(shù)構成的樹，則T的高度不高于log2m+1。證明：當m=1，引理顯然正確。假設對于所有具有i（i≤m–1）個結點的樹引理正確。下面需要證明對于i=m引理也正確。122JYP設T是由函數(shù)WeightedUnion構建的，有m個結點的樹。考慮最后一次并操作union(k,j)。設a為樹j的結點數(shù)，那么樹k的結點數(shù)為m–a。不失一般性，設1≤a≤m/2，則T的根為k。因此，T的高度或者與原樹kkjam-a的相同或者比原樹j的多一級。若是前一種情況，T的高度≤log2(m–a)+1≤log2m+1；若是后一種情況，T的高度≤log2a+2≤log2m+1。

123JYP由引理4.5可知，如果一棵樹有m個結點，則一次find操作的時間最多為O(logm)。執(zhí)行u–1次union操作和f次find操作組成的混合序列的時間是O(u+flogu)，因為每棵樹的結點數(shù)不超過u。當然，初始化n棵樹的森林需要O(n)時間。問題的解決方法還可以作進一