數(shù)據(jù)結(jié)構(gòu)第4章

第4章樹(shù)

本章學(xué)習(xí)最常用的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)之一—樹(shù)，特別是二叉樹(shù)的基本表示和操作方法。

1JYP4.1樹(shù)和森林的概念及其表示

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

定義：一個(gè)森林是由n≥0個(gè)不相交的樹(shù)T1,…,Tn構(gòu)成的集合。森林和樹(shù)的概念密切相關(guān)，因?yàn)閯h除一棵樹(shù)的根就得到森林，而一棵樹(shù)是一個(gè)森林中的一分子。7JYP可以用和廣義表類(lèi)似的方法表示樹(shù)。例如，圖4.1的樹(shù)可寫(xiě)為A(B(E(K,L),F),C(G),D(H(M),I,J))即，根結(jié)點(diǎn)后面是與其子女對(duì)應(yīng)的森林。該樹(shù)的鏈表表示下圖所示：8JYP度為k的樹(shù)稱(chēng)為k叉樹(shù)?？梢灾苯佑煤琸個(gè)子女字段的結(jié)點(diǎn)結(jié)構(gòu)表示k叉樹(shù)的結(jié)點(diǎn)，每個(gè)子女字段指向相應(yīng)的子女結(jié)點(diǎn)，但這會(huì)造成存儲(chǔ)資源的很大浪費(fèi)。

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

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

LeftChild

RightChild

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

11JYP4.2二叉樹(shù)

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

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

classBinaryTree{//對(duì)象：結(jié)點(diǎn)的有限集合，或?yàn)榭?，? //由根結(jié)點(diǎn)和左、右子BinaryTree構(gòu)成public:

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

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

BinaryTreeLchild();//若IsEmpty()為T(mén)RUE返回出錯(cuò)信 //息，否則返回*this的左子樹(shù)13JYP

Element<Type>Data();//若IsEmpty()為T(mén)RUE返回出錯(cuò)信//息，否則返回*this的根結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)

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

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

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

定義：深度為k（k≥0）的滿(mǎn)二叉樹(shù)是具有2k–1個(gè)結(jié)點(diǎn)的二叉樹(shù)。下圖是一棵深度k=4的滿(mǎn)二叉樹(shù)。19JYP其中，結(jié)點(diǎn)從1到2k–1編號(hào)，從第1層開(kāi)始，后接第2層，直至第k層。每層從左到右。通過(guò)這種編號(hào)方式，可定義完全二叉樹(shù)。

定義：深度為k（k≥0）且結(jié)點(diǎn)個(gè)數(shù)為n的二叉樹(shù)是完全二叉樹(shù)當(dāng)且僅當(dāng)其結(jié)點(diǎn)與深度為k的滿(mǎn)二叉樹(shù)的1到n號(hào)結(jié)點(diǎn)一一對(duì)應(yīng)。根據(jù)引理4.2，具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為log2(n+1)。此外，完全二叉樹(shù)的的葉結(jié)點(diǎn)都在相鄰的層次上。

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

LeftChilddata

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

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

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

27JYP4.3二叉樹(shù)遍歷與樹(shù)游標(biāo)

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

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

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

inorder(CurrentNodeLeftChild);cout<<CurrentNodedata;

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

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

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

preorder(CurrentNodeLeftChild);

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

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

postorder(CurrentNodeLeftChild);

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

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

38JYP1voidTree::NonrecInorder(){//利用棧實(shí)現(xiàn)非遞歸中序遍 //歷，設(shè)模板類(lèi)Stack已定義并實(shí)現(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;//訪(fǎng)問(wèn)結(jié)點(diǎn)12

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

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

Treet;

Stack<TreeNode*>s;

TreeNode*CurrentNode;};41JYP其中，假設(shè)InorderIterator是類(lèi)TreeNode和Tree的友元。數(shù)據(jù)成員變量s和CurrentNode記載游標(biāo)的內(nèi)部狀態(tài)。構(gòu)造函數(shù)使游標(biāo)和需遍歷的二叉樹(shù)相關(guān)聯(lián)，并完成必要的初始化。42JYPNext()的實(shí)現(xiàn)基本與函數(shù)Tree::NonrecInorder()第4到15行的while循環(huán)的一次迭代對(duì)應(yīng)：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; //樹(shù)已遍歷完，沒(méi)有更多元素了}43JYP4.3.5后序游標(biāo)

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

TreeNode*p;

BooleanRCVisited; //RCVisited==TRUE表示回溯到結(jié)點(diǎn)p //時(shí)，其右子女已遍歷};44JYP后序游標(biāo)類(lèi)PostorderIterator的定義如下，其中同樣假設(shè)PostorderIterator是類(lèi)TreeNode和Tree的友元。

classPostorderIterator{public:

char*next();

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

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

item.p=CurrentNode;

item.RCVisited=FALSE;

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

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

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

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

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

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

char&temp=CurrentNodedata;CurrentNode=0;//下次執(zhí)行時(shí)將再?gòu)臈Ｖ袆h取結(jié)點(diǎn)return&temp;}}elsereturn0; //樹(shù)已遍歷完，沒(méi)有更多元素了}47JYP4.3.6按層次遍歷

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

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

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

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

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

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

x1)(x0

x2)

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

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

intdata;SatNode*RightChild;};

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

intn; //變量個(gè)數(shù)BooleanPostOrderEval(SatNode*);BooleanNextCombination();};56JYP函數(shù)NextCombination生成變量的下一個(gè)取值組合，當(dāng)變量取值已全部為T(mén)RUE時(shí)，返回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)全部為T(mén)RUE}

57JYP函數(shù)Satisfiability對(duì)x=(FALSE,FALSE,…,FALSE)，計(jì)算公式的值，若為T(mén)RUE則成功返回。否則繼續(xù)生成下一個(gè)取值組合，直到計(jì)算完取值組合(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; //滿(mǎn)足}}while(NextCombination());58JYPdelete[]x;

x=0;returnFALSE; //不可滿(mǎn)足}59JYP函數(shù)PostOrderEval后序遍歷計(jì)算公式的值。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]; //變量下標(biāo)

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

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

LeftThread

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

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

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

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

ThreadedNode*temp=CurrentNodeRightChild;

if(!CurrentNodeRightThread)

while(!tempLeftThread)temp=tempLeftChild;CurrentNode=temp;if(CurrentNode==t.root)return0; //頭結(jié)點(diǎn)

elsereturn&CurrentNodedata;}

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

cout<<*ch<<endl;}

由于每個(gè)結(jié)點(diǎn)最多被訪(fǎng)問(wèn)兩次，所以對(duì)于n個(gè)結(jié)點(diǎn)的線(xiàn)索二叉樹(shù)，中序遍歷的計(jì)算時(shí)間是O(n)。73JYP4.5.3后序遍歷線(xiàn)索二叉樹(shù)

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

表示結(jié)點(diǎn)處理的不同階段。74JYP訪(fǎng)問(wèn)完結(jié)點(diǎn)p后，必須定位p的雙親q，并確定q所處的處理階段。定位p的雙親q如下圖所示：75JYP

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

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

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

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

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

while(p!=root)

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

if(!pLeftThread)p=pLeftChild;

elsenextaction=GORIGHT;break;78JYP

caseGORIGHT: //遍歷非空右子樹(shù)

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

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

ThreadedPostorderIterator(ThreadedTreetree):t(tree)

{CurrentNode=t.rootLeftChild;};private:

ThreadedTreet;

ThreadedNode*CurrentNode;

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

fromFirst){

//fromFirst==TRUE表示由First()調(diào)用BooleanfirstVisit=TRUE;//用于Next(FALSE)，首次到達(dá) //VISITNODE分枝后置為FALSEActionnextAction=VISITNODE; //通過(guò)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; //無(wú)后繼}

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

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

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

rRightThread=sRightThread;

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

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

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

tempLeftChild=r;}}88JYP4.6選擇樹(shù)

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

89JYP4.6.1勝者樹(shù)

勝者樹(shù)的構(gòu)造與錦標(biāo)賽類(lèi)似，勝者是關(guān)鍵字較小的記錄。每個(gè)非葉結(jié)點(diǎn)表示比賽的勝者，根結(jié)點(diǎn)表示總勝者，即樹(shù)中關(guān)鍵字最小的結(jié)點(diǎn)。

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

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

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

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

intgetKey(inti);//返回結(jié)點(diǎn)i指向的記錄緩沖區(qū)中的關(guān)鍵字

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

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

99JYP建立初始敗者樹(shù)的算法及相應(yīng)輔助函數(shù)的實(shí)現(xiàn)如下：voidLoserTree::Build(){ //假設(shè)記錄緩沖區(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); //自下而上建立勝者樹(shù)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); //自上而下建立敗者樹(shù)}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);}顯然，建立初始敗者樹(shù)的計(jì)算時(shí)間是O(k)。

101JYP4.7森林的二叉樹(shù)表示及遍歷

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

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

104JYP設(shè)T是與森林F對(duì)應(yīng)的二叉樹(shù)。前序遍歷二叉樹(shù)T與前序遍歷森林F存在自然對(duì)應(yīng)，森林F的前序遍歷定義為：（1）若F為空則返回；（2）訪(fǎng)問(wèn)F的第一棵樹(shù)的根；（3）前序遍歷由第一棵樹(shù)的子樹(shù)構(gòu)成的森林；（4）前序遍歷由其余樹(shù)構(gòu)成的森林。105JYP中序遍歷二叉樹(shù)T與中序遍歷森林F存在自然對(duì)應(yīng)，森林F的中序遍歷定義為：（1）若F為空則返回；（2）中序遍歷由F的第一棵樹(shù)的子樹(shù)構(gòu)成的森林；（3）訪(fǎng)問(wèn)第一棵樹(shù)的根；（4）中序遍歷由其余樹(shù)構(gòu)成的森林。106JYP后序遍歷二叉樹(shù)T與后序遍歷森林F不存在自然對(duì)應(yīng)，但我們可人為地將森林F的后序遍歷定義為：（1）若F為空則返回；（2）后序遍歷由F的第一棵樹(shù)的子樹(shù)構(gòu)成的森林；（3）后序遍歷由其余樹(shù)構(gòu)成的森林；（4）訪(fǎng)問(wèn)第一棵樹(shù)的根。107JYP

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

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

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

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

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

n=sz;

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

parent[i]=j;}

116JYP對(duì)SimpleUnion和SimpleFind的分析：

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

parent[i]=j;parent[j]=temp;}else{ //樹(shù)j的結(jié)點(diǎn)少或與樹(shù)i的同樣多

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

123JYP由引理4.5可知，如果一棵樹(shù)有m個(gè)結(jié)點(diǎn)，則一次find操作的時(shí)間最多為O(logm)。執(zhí)行u–1次union操作和f次find操作組成的混合序列的時(shí)間是O(u+flogu)，因?yàn)槊靠脴?shù)的結(jié)點(diǎn)數(shù)不超過(guò)u。當(dāng)然，初始化n棵樹(shù)的森林需要O(n)時(shí)間。問(wèn)題的解決方法還可以作進(jìn)一