數(shù)據(jù)結(jié)構(gòu)與算法b-2014年5月07日課堂treemay

數(shù)據(jù)結(jié)構(gòu)與算法

—樹主講教員:段凌宇2014年5月07日

北京大學(xué)信息科學(xué)與技術(shù)學(xué)院，轉(zhuǎn)載或翻印必究大綱5.1樹的概念5.2樹的鏈?zhǔn)酱鎯?chǔ)5.3樹的順序存儲(chǔ)5.4K叉樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page2北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page35.1樹的概念5.1.1樹和森林5.1.2 森林與二叉樹的等價(jià)轉(zhuǎn)換5.1.3樹的抽象數(shù)據(jù)類型5.1.4樹的周游北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page4樹的邏輯結(jié)構(gòu)包含n個(gè)結(jié)點(diǎn)的有窮集合K(n>0)，且在K上定義了一個(gè)關(guān)系N，關(guān)系N滿足以下條件：

有且僅有一個(gè)結(jié)點(diǎn)k0∈K，它對(duì)于關(guān)系N來說沒有前驅(qū)，

結(jié)點(diǎn)k0稱作樹的根；除結(jié)點(diǎn)k0外，K中每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系N都有且僅有一個(gè)前驅(qū)；除結(jié)點(diǎn)k0外的任何結(jié)點(diǎn)k∈K，都存在一個(gè)結(jié)點(diǎn)序列k0，k1，…，ks，使得k0就是樹根，且ks=k，

其中有序?qū)?lt;ki-1，ki>∈N(1≤i≤s)。

這樣的結(jié)點(diǎn)序列稱為從根到結(jié)點(diǎn)k的一條路徑。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page5樹的遞歸定義樹是包括n個(gè)結(jié)點(diǎn)的有限集合T（n≥1），使得：有一個(gè)特別標(biāo)出的稱作根的結(jié)點(diǎn)除根以外的其它結(jié)點(diǎn)被分成m個(gè)(m≥0)不相交的集合T1，T2，…，Tm，而且這些集合的每一個(gè)又都是樹；

樹T1，T2，…，Tm稱作這個(gè)根的子樹。只包含一個(gè)結(jié)點(diǎn)的樹必然僅由根組成，包含n>1個(gè)結(jié)點(diǎn)的樹借助于少于n個(gè)結(jié)點(diǎn)的樹來定義。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page6樹結(jié)構(gòu)中的概念若有序?qū)?lt;

k，k′>

∈N，則稱k是k′的父結(jié)點(diǎn)（或“父母”），而k′則是k的子結(jié)點(diǎn)(或“兒子”、“子女”)若有序?qū)?lt;k，k′>及<k，k″>

∈N，則稱k′和k″互為兄弟若有一條由k到達(dá)ks的路徑，則稱k是ks的祖先，ks

是k的子孫樹形結(jié)構(gòu)中，兩個(gè)結(jié)點(diǎn)的有序?qū)ΓQ作連接這兩結(jié)點(diǎn)的一條邊北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page7沒有子樹的結(jié)點(diǎn)稱作樹葉或終端結(jié)點(diǎn)非終端結(jié)點(diǎn)稱為分支結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的子樹的個(gè)數(shù)稱為度數(shù)根結(jié)點(diǎn)的層數(shù)為0，其它任何結(jié)點(diǎn)的層數(shù)等于它的父結(jié)點(diǎn)結(jié)點(diǎn)的層數(shù)加1樹T中如果子樹T1，T2，…，Tm的相對(duì)次序是重要的，則稱樹T為有向有序樹，簡稱有序樹?？梢苑QT1是根的第一棵子樹，T2是根的第二棵子樹，等等。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page8森林與樹森林(forest):零棵或多棵不相交的樹的集合。(通常是有序集合)自然界的樹和森林是不同的概念，而數(shù)據(jù)結(jié)構(gòu)的樹和森林只有微小的差別。刪去樹根，樹就變成森林；加上一個(gè)結(jié)點(diǎn)作樹根，森林就變成樹。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page95.1樹的概念5.1.1樹和森林5.1.2 森林與二叉樹的等價(jià)轉(zhuǎn)換5.1.3樹的抽象數(shù)據(jù)類型5.1.4樹的周游北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page10森林與二叉樹的等價(jià)轉(zhuǎn)換×××北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page11森林與二叉樹的等價(jià)轉(zhuǎn)換樹或森林與二叉樹之間存在一個(gè)自然的一一對(duì)應(yīng)的關(guān)系任何森林都唯一地對(duì)應(yīng)到一棵二叉樹；反過來，任何二叉樹也都唯一地對(duì)應(yīng)到一個(gè)森林。樹所對(duì)應(yīng)的二叉樹里結(jié)點(diǎn)n的左子結(jié)點(diǎn)是結(jié)點(diǎn)n在原來樹里的第一個(gè)子結(jié)點(diǎn)結(jié)點(diǎn)n的右子結(jié)點(diǎn)是結(jié)點(diǎn)n在原來樹里的下一個(gè)兄弟北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page12森林到二叉樹等價(jià)轉(zhuǎn)換

的精確定義森林F看作樹的有序集合，F(xiàn)=(T1，T2，…，Tn)，對(duì)應(yīng)于F的二叉樹B(F)的定義是：若n=0，則B(F)為空若n>0，則B(F)的根是T1的根W1，B(F)的左子樹是B(T11，T12，…，T1m)，其中T11，T12，…，T1m是W1的子樹；B(F)的右子樹是B(T2，…，Tn)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page13二叉樹到森林的等價(jià)轉(zhuǎn)換設(shè)B是一棵二叉樹，r是B的根，L是r的左子樹，

R是r的右子樹，則對(duì)應(yīng)于B的森林F(B)的定義：若B為空，則F(B)是空的森林；若B不為空，則F(B)是一棵樹T1

+森林F(R)，其中樹T1的根為r，r的子樹為F(L)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page145.1樹的概念5.1.1樹和森林5.1.2 森林與二叉樹的等價(jià)轉(zhuǎn)換5.1.3樹的抽象數(shù)據(jù)類型5.1.4樹的周游北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page15樹/森林的

結(jié)點(diǎn)抽象數(shù)據(jù)類型 template<classT> classTreeNode {

public: TreeNode(constT&);//拷貝構(gòu)造函數(shù)

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

boolisLeaf(); //如果結(jié)點(diǎn)是葉，返回true TValue(); //返回結(jié)點(diǎn)的值

TreeNode<T>*LeftMostChild();//返回第一個(gè)左孩子

TreeNode<T>*RightSibling();//返回右兄弟北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page16

//設(shè)置結(jié)點(diǎn)的值

voidsetValue(T&);

//設(shè)置左子結(jié)點(diǎn)

voidsetChild(TreeNode<T>*pointer);

//設(shè)置右兄弟

voidsetSibling(TreeNode<T>*pointer);

//以第一個(gè)左子結(jié)點(diǎn)身份插入結(jié)點(diǎn)

voidInsertFirst(TreeNode<T>*node);

//以右兄弟的身份插入結(jié)點(diǎn)

voidInsertNext(TreeNode<T>*node);};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page17樹/森林的抽象數(shù)據(jù)類型 template<classT> classTree {

public: Tree(); //構(gòu)造函數(shù)

virtual~Tree(); //析構(gòu)函數(shù)

TreeNode<T>*getRoot();

//返回樹中的根結(jié)點(diǎn)

//創(chuàng)建樹中的根結(jié)點(diǎn)，使根結(jié)點(diǎn)元素的值為rootValue voidCreateRoot(constT&rootValue);

//判斷是否為空樹，如果是則返回true boolisEmpty();

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page18//返回current結(jié)點(diǎn)的父結(jié)點(diǎn) TreeNode<T>*Parent(TreeNode<T>*current);

//返回current結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)

TreeNode<T>*PrevSibling(TreeNode<T>*current);

//刪除以subroot為根的子樹的所有結(jié)點(diǎn) voidDeleteSubTree(TreeNode<T>*subroot);

//先根深度優(yōu)先周游樹 voidRootFirstTraverse(TreeNode<T>*root);

//后根深度優(yōu)先周游樹 voidRootLastTraverse(TreeNode<T>*root); //寬度優(yōu)先周游樹

voidWidthTraverse(TreeNode<T>*root);};北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page195.1樹的概念5.1.1樹和森林5.1.2 森林與二叉樹的等價(jià)轉(zhuǎn)換5.1.3樹的抽象數(shù)據(jù)類型5.1.4樹的周游北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page20森林的深度優(yōu)先周游

先根次序

a)訪問頭一棵樹的根

b)在先根次序下周游頭一棵樹樹根的所有子樹

c)在先根次序下依次周游其他的樹

后根次序

a)在后根次序下周游頭一棵樹樹根的所有子樹

b)訪問頭一棵樹的根

c)在后根次序下依次周游其他的樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page21森林的周游

示例ABCKDEFGHJ先根次序周游：A

B

C

K

D

E

H

F

J

G后根次序周游：BKCAHEJFGD廣度優(yōu)先周游：ADBCEFGKHJ北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page22先根深度優(yōu)先

周游樹程序?qū)崿F(xiàn)template<classT>voidTree<T>::RootFirstTraverse(TreeNode<T>*root){if(root!=NULL){Visit(root->Value());//訪問當(dāng)前結(jié)點(diǎn)root=root->LeftMostChild(); while(root!=NULL){

RootFirstTraverse(root); root=root->RightSibling();//周游其他的子樹

}}}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page23后根深度優(yōu)先

周游樹程序?qū)崿F(xiàn)template<classT>voidTree<T>::RootLastTraverse(TreeNode<T>*root){TreeNode<T>*pointer=root;if(root!=NULL){pointer=root->LeftMostChild(); while(pointer!=NULL){

RootLastTraverse(pointer); pointer=pointer->RightSibling();//周游其他的子樹

}Visit(root->Value());//訪問當(dāng)前結(jié)點(diǎn)}}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page24寬度優(yōu)先

周游樹的程序?qū)崿F(xiàn)template<classT>voidTree<T>::WidthTraverse(TreeNode<T>*root){ usingstd::queue; //使用STL隊(duì)列

queue<TreeNode<T>*>aQueue; TreeNode<T>*pointer=root; if(pointer)

aQueue.push(pointer); while(!aQueue.empty()){pointer=aQueue.front();//取隊(duì)列首結(jié)點(diǎn)指針Visit(pointer->Value());//訪問當(dāng)前結(jié)點(diǎn)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page25

pointer=pointer->LeftMostChild();

while(pointer){aQueue.push(pointer);pointer=pointer->RightSibling();};aQueue.pop(); //出隊(duì)列}}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page26深度優(yōu)先周游森林

versus

深度優(yōu)先周游等價(jià)的二叉樹按先根次序周游森林等同按前序法周游對(duì)應(yīng)的二叉樹按后根次序周游森林等同按中序法周游對(duì)應(yīng)的二叉樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page27先根深度優(yōu)先

周游森林程序?qū)崿F(xiàn)template<classT>voidTree<T>::RootFirstTraverse(TreeNode<T>*root){while(root!=NULL){Visit(root->Value());//訪問當(dāng)前結(jié)點(diǎn)

RootFirstTraverse(root->LeftMostChild()root=root->RightSibling();//周游其他的樹}}template<classT>voidTree<T>::RootLastTraverse(TreeNode<T>*root){ while(root!=NULL){

RootLastTraverse(root->LeftMostChild()); Visit(root->Value());//訪問當(dāng)前結(jié)點(diǎn)

root=root->RightSibling();//周游其他的樹

}}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page28后根深度優(yōu)先

周游森林程序?qū)崿F(xiàn)大綱5.1樹的概念5.2樹的鏈?zhǔn)酱鎯?chǔ)5.3樹的順序存儲(chǔ)5.4K叉樹北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page29北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page305.2樹的鏈?zhǔn)酱鎯?chǔ)5.2.1子結(jié)點(diǎn)表表示法5.2.2左子結(jié)點(diǎn)/右兄弟結(jié)點(diǎn)表示法5.2.3動(dòng)態(tài)結(jié)點(diǎn)表示法5.2.4動(dòng)態(tài)“左子結(jié)點(diǎn)/右兄弟結(jié)點(diǎn)”二叉鏈表表示法5.2.5父指針表示法北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page315.2.1子結(jié)點(diǎn)表表示法“子結(jié)點(diǎn)表”表示法在數(shù)組中存儲(chǔ)樹的結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)包括結(jié)點(diǎn)值、一個(gè)父指針以及一個(gè)指向子結(jié)點(diǎn)鏈表的指針。每個(gè)分支結(jié)點(diǎn)均存儲(chǔ)其子結(jié)點(diǎn)信息，子結(jié)點(diǎn)按照從左至右的順序形成一個(gè)鏈表(葉子結(jié)點(diǎn)的子結(jié)點(diǎn)鏈表指針為空)。結(jié)點(diǎn)的最左子結(jié)點(diǎn)可由鏈表的第一個(gè)表項(xiàng)直接找到。找到結(jié)點(diǎn)的右側(cè)兄弟結(jié)點(diǎn)要困難一些。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page325.2.2左子結(jié)點(diǎn)/右兄弟結(jié)點(diǎn)

表示法每個(gè)結(jié)點(diǎn)存儲(chǔ)結(jié)點(diǎn)值，指向父結(jié)點(diǎn)、最左子結(jié)點(diǎn)、右側(cè)兄弟結(jié)點(diǎn)的指針。ADT的基本操作可通過讀取結(jié)點(diǎn)中的一個(gè)值來實(shí)現(xiàn)。如果兩棵樹存儲(chǔ)在同一個(gè)數(shù)組中，那么把其中一個(gè)添加為另一棵樹的子樹只需簡單設(shè)置三個(gè)指針值即可。這種表示法比子結(jié)點(diǎn)表表示法空間效率更高，而且結(jié)點(diǎn)數(shù)組中的每個(gè)結(jié)點(diǎn)僅需要固定大小的存儲(chǔ)空間。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page335.2.3動(dòng)態(tài)結(jié)點(diǎn)表示法為每個(gè)結(jié)點(diǎn)分配可變的存儲(chǔ)空間。每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)基于數(shù)組的子結(jié)點(diǎn)指針表。子結(jié)點(diǎn)的數(shù)目不變時(shí)，這種方法效果最佳；如果子結(jié)點(diǎn)的數(shù)目發(fā)生變動(dòng)（特別是增加），就必須提供一種專門的校正機(jī)制來改變子結(jié)點(diǎn)指針數(shù)組的大小每個(gè)結(jié)點(diǎn)存儲(chǔ)一條子結(jié)點(diǎn)指針鏈表，動(dòng)態(tài)地分配指針空間。本質(zhì)上與“子結(jié)點(diǎn)表”表示法相同(少了指向父結(jié)點(diǎn)的指針，且鏈表中指針不是數(shù)組中的整數(shù)下標(biāo)索引)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page345.2.4動(dòng)態(tài)“左子結(jié)點(diǎn)/右兄弟結(jié)點(diǎn)”

二叉鏈表表示法本質(zhì)上，我們使用二叉樹來替換樹。左子結(jié)點(diǎn)在樹中是結(jié)點(diǎn)的最左子結(jié)點(diǎn)，右子結(jié)點(diǎn)是結(jié)點(diǎn)原來的右側(cè)兄弟結(jié)點(diǎn)。由于樹的每個(gè)結(jié)點(diǎn)均包含固定數(shù)目的指針，而且樹的ADT的每個(gè)函數(shù)均能有效實(shí)現(xiàn)，因此動(dòng)態(tài)“左子結(jié)點(diǎn)/右兄弟結(jié)點(diǎn)”表示法比以上介紹的其他方法更為常用。可以很容易地把這種轉(zhuǎn)化推廣到森林，因?yàn)樯种忻靠脴涞母Y(jié)點(diǎn)可以看成互為兄弟結(jié)點(diǎn)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page355.2.4動(dòng)態(tài)“左子結(jié)點(diǎn)/右兄弟結(jié)點(diǎn)”

二叉鏈表表示法本質(zhì)上，我們使用二叉樹來替換樹。左子結(jié)點(diǎn)在樹中是結(jié)點(diǎn)的最左子結(jié)點(diǎn)，右子結(jié)點(diǎn)是結(jié)點(diǎn)原來的右側(cè)兄弟結(jié)點(diǎn)。由于樹的每個(gè)結(jié)點(diǎn)均包含固定數(shù)目的指針，而且樹的ADT的每個(gè)函數(shù)均能有效實(shí)現(xiàn)，因此動(dòng)態(tài)“左子結(jié)點(diǎn)/右兄弟結(jié)點(diǎn)”表示法比以上介紹的其他方法更為常用。可以很容易地把這種轉(zhuǎn)化推廣到森林，因?yàn)樯种忻靠脴涞母Y(jié)點(diǎn)可以看成互為兄弟結(jié)點(diǎn)。北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page36樹結(jié)點(diǎn)抽象數(shù)據(jù)類型

的程序?qū)崿F(xiàn)//補(bǔ)充與具體實(shí)現(xiàn)相關(guān)的私有成員變量申明…private: Tm_Value; //樹結(jié)點(diǎn)的值

TreeNode<T>* pChild; //第一個(gè)左子結(jié)點(diǎn)

TreeNode<T>* pSibling; //右兄弟結(jié)點(diǎn)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page37樹結(jié)點(diǎn)抽象數(shù)據(jù)類型

的程序?qū)崿F(xiàn)

//公有成員函數(shù)的具體實(shí)現(xiàn)

template<classT>

TreeNode<T>::TreeNode(constT&value)

{

m_Value=value; pChild=NULL; pSibling=NULL; }

template<classT>

TTreeNode<T>::Value()

{

returnm_Value;

}

template<classT>

boolTreeNode<T>::isLeaf()

{

if(pChild==NULL)

returntrue;

returnfalse;

}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page38template<classT>void

TreeNode<T>::setValue(T&value) {

m_Value=value;

//設(shè)置結(jié)點(diǎn)的值}template<classT>TreeNode<T>*

TreeNode<T>::LeftMostChild(){

returnpChild;

//返回第一個(gè)左子結(jié)點(diǎn)}template<classT>TreeNode<T>*

TreeNode<T>::RightSibling(){

returnpSibling;

//返回右兄弟}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page39template<classT>voidTreeNode<T>::setChild(TreeNode<T>*pointer){

pChild=pointer;

//設(shè)置左子結(jié)點(diǎn)}template<classT>voidTreeNode<T>::setSibling(TreeNode<T>*pointer){

pSibling=pointer;

//設(shè)置右兄弟}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page40template<classT>voidTreeNode<T>::InsertFirst(TreeNode<T>*node){

if

(!pChild)

pChild=node;

//若當(dāng)前結(jié)點(diǎn)原先無子女 else

{

//若當(dāng)前結(jié)點(diǎn)原先已有子女

node->pSibling=pChild;

pChild=node; }}以當(dāng)前結(jié)點(diǎn)TreeNode第一個(gè)子結(jié)點(diǎn)的身份插入結(jié)點(diǎn)北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page41以當(dāng)前結(jié)點(diǎn)TreeNode右兄弟的身份插入結(jié)點(diǎn)template<classT>voidTreeNode<T>::InsertNext(TreeNode<T>*node){

if(!pSibling) pSibling=node;//若當(dāng)前結(jié)點(diǎn)原先無右兄弟 else{

//若當(dāng)前結(jié)點(diǎn)原先已有右兄弟

node->pSibling=pSibling; pSibling=node; }}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page42樹抽象數(shù)據(jù)類型的

程序?qū)崿F(xiàn)private: TreeNode<T>*root;

//樹根結(jié)點(diǎn)

//返回current的父結(jié)點(diǎn)，由函數(shù)Parent調(diào)用

TreeNode<T>*getParent(TreeNode<T>*root,

TreeNode<T>*current);

//刪除以root為根的子樹的所有結(jié)點(diǎn)

voidDeleteNodes(TreeNode<T>*root); 北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page43template<classT>Tree<T>::Tree() {

root=NULL;}template<classT>Tree<T>::~Tree()

{

while(root)

DeleteSubTree(root);}template<classT>TreeNode<T>*Tree<T>::getRoot()

{

returnroot;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page44template<classT>voidTree<T>::CreateRoot(constT&rootValue){//創(chuàng)建樹中的根結(jié)點(diǎn)，使根結(jié)點(diǎn)元素的值為rootValue

if(!root)

root=newTreeNode<T>(rootValue);}template<classT>boolTree<T>::isEmpty(){//判斷是否為空樹，如果是則返回true if(root)

returnfalse; returntrue;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page45返回current結(jié)點(diǎn)的

前一個(gè)鄰居結(jié)點(diǎn)的程序?qū)崿F(xiàn)template<classT>TreeNode<T>*

Tree<T>::PrevSibling

(TreeNode<T>*current){

usingstd::queue;

//使用STL隊(duì)列

queue<

TreeNode<T>*

>aQueue;

//標(biāo)識(shí)當(dāng)前結(jié)點(diǎn) TreeNode<T>*pointer=root;

//標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)的前一個(gè)兄弟結(jié)點(diǎn)

TreeNode<T>*prev=NULL;

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page46if

((current==NULL)||(pointer==NULL)

||(current==pointer))

//當(dāng)前結(jié)點(diǎn)為空、樹為空、當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn) returnNULL; while(pointer){//找到當(dāng)前結(jié)點(diǎn) if(pointer==current) returnprev;

aQueue.push(pointer); prev=pointer;//沿當(dāng)前結(jié)點(diǎn)右兄弟結(jié)點(diǎn)鏈尋找 pointer=pointer->pSibling;}//以廣度優(yōu)先周游方式尋找前一鄰結(jié)點(diǎn)

while(!aQueue.empty()){ prev=NULL; pointer=aQueue.front(); //出隊(duì)列 aQueue.pop();

//下降到左子結(jié)點(diǎn)

pointer=pointer->LeftMostChild();

北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page47北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page48while(pointer){ if(pointer==current)returnprev; aQueue.push(pointer); prev=pointer; pointer=pointer->pSibling;

} } returnNULL;}北京大學(xué)信息學(xué)院，轉(zhuǎn)載或翻印必究Page49

template<classT> voidTree<T>::DeleteNodes(TreeNode<T>*root) {

if(root){

//遞歸刪除第一子樹

DeleteNodes(root->LeftMostChild());

//遞歸刪除其他子樹

DeleteNodes(root->RightSibling()); //刪除根結(jié)點(diǎn)

deleteroot;

} }刪除以root為根的子樹的所有結(jié)點(diǎn)

template<classT> voidTree<T>::

DeleteSubTree(TreeNode<T>*subroot) {

TreeNode<T>*pointer=PrevSibling(subroot); if(pointer==NULL) {//subroot為最左子結(jié)點(diǎn)的情況

pointer=Parent(subroot); if(pointer){ pointer->pChild=subroo