第六章 樹(shù)_修改

1、第六章 樹(shù)1 繼續(xù)本章介紹非線性結(jié)構(gòu)樹(shù)。 一般樹(shù)和森林 其特點(diǎn)是每一個(gè)元素可以有唯一的直接前驅(qū)和任意的直接后繼。2樹(shù)（Tree） 定義 樹(shù)(tree)是包括 n 個(gè)結(jié)點(diǎn)的有限集合 T (n1)，使得：n有一個(gè)特別標(biāo)出的稱作根（root）的結(jié)點(diǎn)；n除根以外的其它結(jié)點(diǎn)被分成m個(gè)(m0)不相交的集合T1, T2, , Tm，而且這些集合的每一個(gè)又都是樹(shù)。 其中，樹(shù)T1, T2, , Tm稱作這個(gè)根的子樹(shù)(subtree)。3樹(shù)（Tree） 例：4ABCJDEILDEKG樹(shù)（Tree） 邏輯定義 包含n個(gè)結(jié)點(diǎn)的有窮集合K (n0)，且在K上定義了一個(gè)關(guān)系N，關(guān)系N滿足以下條件： 有且僅有一個(gè)結(jié)點(diǎn)k0K

2、，它對(duì)于關(guān)系N來(lái)說(shuō)沒(méi)有前驅(qū)。結(jié)點(diǎn)k0稱作樹(shù)的根； 除結(jié)點(diǎn)k0外，K中的每個(gè)結(jié)點(diǎn)對(duì)于關(guān)系N來(lái)說(shuō)都有且僅有一個(gè)前驅(qū) ；5樹(shù)（Tree） 邏輯定義 包含n個(gè)結(jié)點(diǎn)的有窮集合K (n0)，且在K上定義了一個(gè)關(guān)系N，關(guān)系N滿足以下條件： 除結(jié)點(diǎn)k0外的任何結(jié)點(diǎn)kK，都存在一個(gè)結(jié)點(diǎn)序列k0，k1，ks，使得k0就是樹(shù)根，且ks=k，其中有序?qū)(1is)。這樣的結(jié)點(diǎn)序列稱為從根到結(jié)點(diǎn)k的一條路徑。6樹(shù)（Tree）的表示 樹(shù)的形式化表示邏輯表示： 結(jié)點(diǎn)集合K=A，B，C，D，E，F(xiàn)，G，H，I，J K上的關(guān)系N= ， ， ， 7樹(shù)（Tree）的表示 樹(shù)的樹(shù)形表示：8ABCJDEILDEKG樹(shù)（Tree）的表示

3、 樹(shù)的凹入表示法：9樹(shù)（Tree）的表示 樹(shù)的文氏圖表示：10樹(shù)（Tree）的表示 樹(shù)的嵌套括號(hào)表示：(A(B(D)(E(I)(J)(F)(C(G)(H)11樹(shù)的基本術(shù)語(yǔ) 樹(shù)的基本術(shù)語(yǔ)和二叉樹(shù)中大體相同，但有一點(diǎn)要注意有序無(wú)序： 二叉樹(shù)是有序樹(shù)； 根據(jù)其子樹(shù)是否有序可分為是無(wú)序樹(shù)（交換子樹(shù)還是同一個(gè)樹(shù)）和有序樹(shù)，除非特殊說(shuō)明一般提到的樹(shù)都是無(wú)序樹(shù)。森林(forest) 森林(forest) 森林是零棵或多棵不相交的樹(shù)的集合(通常是有序集合)。 注意： 自然界的樹(shù)和森林是不同的概念，而數(shù)據(jù)結(jié)構(gòu)的樹(shù)和森林只有微小的差別。 刪去樹(shù)根，樹(shù)就變成森林。加上一個(gè)結(jié)點(diǎn)作樹(shù)根，森林就變成樹(shù)。/樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)

4、類型templateclass TreeNode public: TreeNode(const T& value);/拷貝構(gòu)造函數(shù) virtual TreeNode( ) /析構(gòu)函數(shù) bool isLeaf( ); /如果結(jié)點(diǎn)是葉，返回true T Value( ); /返回結(jié)點(diǎn)的值 TreeNode* LeftMostChild( ); /返回第一個(gè)左孩子 TreeNode* RightSibling( ); /返回右兄弟void setValue(T&);/設(shè)置結(jié)點(diǎn)的值 /設(shè)置左子結(jié)點(diǎn) void setChild(TreeNode* pointer); /設(shè)置右兄弟 voi

5、d setSibling(TreeNode* pointer); /以第一個(gè)左子結(jié)點(diǎn)身份插入結(jié)點(diǎn) void InsertFirst(TreeNode* node); /以右兄弟的身份插入結(jié)點(diǎn) void InsertNext(TreeNode* node);14/樹(shù)結(jié)點(diǎn)的抽象數(shù)據(jù)類型templateclass TreeNode public: TreeNode(const T& value);/拷貝構(gòu)造函數(shù) virtual TreeNode( ) /析構(gòu)函數(shù) bool isLeaf( ); /如果結(jié)點(diǎn)是葉，返回true T Value( ); /返回結(jié)點(diǎn)的值 TreeNode* Left

6、MostChild( ); /返回第一個(gè)左孩子 TreeNode* RightSibling( ); /返回右兄弟void setValue(T&);/設(shè)置結(jié)點(diǎn)的值 /設(shè)置左子結(jié)點(diǎn) void setChild(TreeNode* pointer); /設(shè)置右兄弟 void setSibling(TreeNode* pointer); /以第一個(gè)左子結(jié)點(diǎn)身份插入結(jié)點(diǎn) void InsertFirst(TreeNode* node); /以右兄弟的身份插入結(jié)點(diǎn) void InsertNext(TreeNode* node);15/樹(shù)的抽象數(shù)據(jù)類型template class Tree pu

7、blic:Tree();/構(gòu)造函數(shù)virtual Tree();/析構(gòu)函數(shù)/返回樹(shù)中的根結(jié)點(diǎn)TreeNode* getRoot();/創(chuàng)建樹(shù)中的根結(jié)點(diǎn)，使根結(jié)點(diǎn)元素的值為rootValuevoid CreateRoot(const T& rootValue);/判斷是否為空樹(shù)，如果是則返回truebool isEmpty();/返回current結(jié)點(diǎn)的父結(jié)點(diǎn)TreeNode* Parent(TreeNode* current); /返回current結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)TreeNode* PrevSibling(TreeNode* current); /刪除以subroot為根的子樹(shù)的

8、所有結(jié)點(diǎn)void DeleteSubTree(TreeNode* subroot); /先根深度優(yōu)先周游樹(shù)void RootFirstTraverse(TreeNode* root); /后根深度優(yōu)先周游樹(shù)void RootLastTraverse(TreeNode* root); /寬度優(yōu)先周游樹(shù)void WidthTraverse(TreeNode* root);16/樹(shù)的抽象數(shù)據(jù)類型template class Tree public:Tree();/構(gòu)造函數(shù)virtual Tree();/析構(gòu)函數(shù)/返回樹(shù)中的根結(jié)點(diǎn)TreeNode* getRoot();/創(chuàng)建樹(shù)中的根結(jié)點(diǎn)，使根結(jié)點(diǎn)元素

9、的值為rootValuevoid CreateRoot(const T& rootValue);/判斷是否為空樹(shù)，如果是則返回truebool isEmpty();/返回current結(jié)點(diǎn)的父結(jié)點(diǎn)TreeNode* Parent(TreeNode* current); /返回current結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)TreeNode* PrevSibling(TreeNode* current); /刪除以subroot為根的子樹(shù)的所有結(jié)點(diǎn)void DeleteSubTree(TreeNode* subroot); /先根深度優(yōu)先周游樹(shù)void RootFirstTraverse(TreeNo

10、de* root); /后根深度優(yōu)先周游樹(shù)void RootLastTraverse(TreeNode* root); /寬度優(yōu)先周游樹(shù)void WidthTraverse(TreeNode* root);17樹(shù)的物理實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu)： 順序存儲(chǔ)方式（無(wú)法實(shí)現(xiàn)） 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)非連續(xù)空間（指針） 連續(xù)空間（下標(biāo)） 樹(shù)運(yùn)算： 樹(shù)的查找遍歷（深度和廣度）18樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 轉(zhuǎn)換基礎(chǔ) 在樹(shù)或森林與二叉樹(shù)之間有一個(gè)自然的一一對(duì)應(yīng)的關(guān)系。 條件： 各樹(shù)或子樹(shù)有序， 如果無(wú)序自定義一個(gè)順序19樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 把F看作樹(shù)的有序集合，F(xiàn)=( T1, T2, , Tn )，F(xiàn)可按如下規(guī)則轉(zhuǎn)換為二叉樹(shù)

11、B(F)： 若n=0，則B（F）為空； 若n0，則B(F)的根是T1的根W1，B(F)的左子樹(shù)是B( T11, T12, , T1m )，其中T11, T12, , T1m是W1的子樹(shù)；B(F)的右子樹(shù)是B( T2, , Tn )。20樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 簡(jiǎn)單的講，樹(shù)和森林到二叉樹(shù)的轉(zhuǎn)換可用連線、切線和旋轉(zhuǎn)三步來(lái)說(shuō)明： 連線：將兄弟用線連起來(lái)； 切線：保留父結(jié)點(diǎn)與其第一個(gè)子結(jié)點(diǎn)的連線，將父結(jié)點(diǎn)到其它子結(jié)點(diǎn)的連線切斷； 旋轉(zhuǎn)：以根為軸，平面下順時(shí)針?lè)较蛐D(zhuǎn)一定角度。美觀21ABCHEFILDJKGM 樹(shù)轉(zhuǎn)二叉樹(shù)實(shí)例（初始）ABCHEFILDJKGM 樹(shù)轉(zhuǎn)二叉樹(shù)實(shí)例（連線）ABCHEFILDJ

12、KGM 樹(shù)轉(zhuǎn)二叉樹(shù)實(shí)例（切線）：ABCHEFILDJKGM 樹(shù)轉(zhuǎn)二叉樹(shù)（切線）ABCHEFILDJKGM 樹(shù)轉(zhuǎn)二叉樹(shù)（旋轉(zhuǎn)）BCHEFILDJKGM 森林轉(zhuǎn)二叉樹(shù)增加一個(gè)虛擬的根即可ABCHEFILDJKGM 森林轉(zhuǎn)二叉樹(shù)增加一個(gè)虛擬的根即可 森林轉(zhuǎn)二叉樹(shù)（旋轉(zhuǎn)）BCHEFILDJKGM樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 特點(diǎn) 樹(shù)轉(zhuǎn)換而得的二叉樹(shù)根無(wú)右枝 森林轉(zhuǎn)換而得的二叉樹(shù)根有右枝（兩棵樹(shù)以上）30樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 設(shè)：B是一棵二叉樹(shù)，rt是B的根，L是rt的左子樹(shù)，R是rt的右子樹(shù)，則對(duì)應(yīng)于B的森林 F(B)的定義是： 若B為空，則F(B)是空的森林。 若B不為空，則F(B)是一棵樹(shù)T1加上森林

13、F(R)，其中樹(shù)T1的根為rt，rt的子樹(shù)為F(L)31樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 簡(jiǎn)單的講，二叉樹(shù)到樹(shù)和森林的轉(zhuǎn)換可用加線抹線和調(diào)整三步來(lái)說(shuō)明： 加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)； 抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線； 調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)。32 二叉樹(shù)轉(zhuǎn)樹(shù)/森林（初始）ABCDEFGHI 二叉樹(shù)轉(zhuǎn)樹(shù)/森林（加線）ABCDEFGHI 二叉樹(shù)轉(zhuǎn)樹(shù)/森林（抹線）ABCDEFGHI 二叉樹(shù)轉(zhuǎn)樹(shù)/森林（抹線）ABCDEFGHI 二叉樹(shù)轉(zhuǎn)樹(shù)/森林（調(diào)整）ABCDEFGHI樹(shù)和森林與二叉樹(shù)的轉(zhuǎn)換 結(jié)論 樹(shù)和

14、森林可以以二叉樹(shù)的結(jié)構(gòu)存儲(chǔ) 下面給出樹(shù)的動(dòng)態(tài)二叉鏈表存儲(chǔ)方式，由于表示的是一般樹(shù)轉(zhuǎn)換成的二叉樹(shù)，所以其結(jié)構(gòu)叫做動(dòng)態(tài)“左孩子右兄弟”表示法。38動(dòng)態(tài)“左子/右兄”存儲(chǔ)方式 特點(diǎn) 本質(zhì)上，我們使用二叉樹(shù)來(lái)替換樹(shù)。 新的結(jié)構(gòu)中左子結(jié)點(diǎn)在樹(shù)中是結(jié)點(diǎn)的最左子結(jié)點(diǎn)。右子結(jié)點(diǎn)是結(jié)點(diǎn)原來(lái)的右側(cè)兄弟結(jié)點(diǎn) ； 可以很容易的把這種轉(zhuǎn)化推廣到森林，因?yàn)樯种忻靠脴?shù)的根結(jié)點(diǎn)可以看成互為兄弟結(jié)點(diǎn) 39動(dòng)態(tài)“左子/右兄”存儲(chǔ)方式 特點(diǎn) 結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn) 由于樹(shù)的每個(gè)結(jié)點(diǎn)均包含固定數(shù)目的指針，而且樹(shù)的ADT的每個(gè)函數(shù)均能有效實(shí)現(xiàn)。 因此動(dòng)態(tài)“左子結(jié)點(diǎn)/右兄弟”表示法比其他方法更為常用。40/樹(shù)結(jié)點(diǎn)類實(shí)現(xiàn)樹(shù)結(jié)點(diǎn)類實(shí)現(xiàn)temp

15、lateclass TreeNode private:T m_Value; /樹(shù)結(jié)點(diǎn)的值樹(shù)結(jié)點(diǎn)的值TreeNode*pChild; /左子結(jié)點(diǎn)左子結(jié)點(diǎn)TreeNode*pSibling;/右兄弟結(jié)點(diǎn)右兄弟結(jié)點(diǎn) public: 41/拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)templateTreeNode:TreeNode(const T& value) m_Value = value;pChild = NULL;pSibling = NULL;/返回結(jié)點(diǎn)的值返回結(jié)點(diǎn)的值template T TreeNode:Value( )return m_Value;42/返回第一個(gè)左子結(jié)點(diǎn)返回第一個(gè)左子結(jié)點(diǎn)tem

16、plateTreeNode*TreeNode:LeftMostChild( ) return pChild;/返回右兄弟返回右兄弟templateTreeNode* TreeNode:RightSibling( ) return pSibling;43/設(shè)置結(jié)點(diǎn)的值設(shè)置結(jié)點(diǎn)的值templatevoid TreeNode:setValue ( T& value ) m_Value = value;/設(shè)置左子結(jié)點(diǎn)設(shè)置左子結(jié)點(diǎn)templatevoid TreeNode:setChild ( TreeNode * pointer ) pChild = pointer;44/設(shè)置右兄弟設(shè)置右兄弟

17、templatevoid TreeNode:setSibling ( TreeNode * pointer ) pSibling = pointer;/如果當(dāng)前結(jié)點(diǎn)是葉子，返回如果當(dāng)前結(jié)點(diǎn)是葉子，返回truetemplatebool TreeNode:isLeaf( ) if ( pChild = NULL)/左指針指向孩子左指針指向孩子return true;return false;45/InsertFirst實(shí)現(xiàn)實(shí)現(xiàn)以第一個(gè)子結(jié)點(diǎn)的身份插入結(jié)點(diǎn)以第一個(gè)子結(jié)點(diǎn)的身份插入結(jié)點(diǎn)template void TreeNode:InsertFirst ( TreeNode* node ) if (

18、! pChild )pChild = node;else node-pSibling = pChild;pChild = node;46/InsertNext實(shí)現(xiàn)實(shí)現(xiàn)以右兄弟的身份插入結(jié)點(diǎn)以右兄弟的身份插入結(jié)點(diǎn)templatevoid TreeNode:InsertNext ( TreeNode* node ) if( ! pSibling )pSibling = node;else node - pSibling = pSibling;pSibling = node;47/樹(shù)類實(shí)現(xiàn)樹(shù)類實(shí)現(xiàn)template class Tree private:TreeNode * root;void Des

19、toryNodes ( TreeNode* root ); TreeNode* getParent( TreeNode* root, TreeNode* current ); public:48/構(gòu)造函數(shù)構(gòu)造函數(shù)template Tree:Tree( ) root=NULL;/析構(gòu)函數(shù)析構(gòu)函數(shù)template Tree:Tree()while ( root )DeleteSubTree( root );49/返回樹(shù)中的根結(jié)點(diǎn)返回樹(shù)中的根結(jié)點(diǎn)template TreeNode * Tree:getRoot( ) return root;/創(chuàng)建樹(shù)中的根結(jié)點(diǎn)創(chuàng)建樹(shù)中的根結(jié)點(diǎn)，使根結(jié)點(diǎn)元素的值為使根結(jié)

20、點(diǎn)元素的值為rootValuetemplate void Tree:CreateRoot ( const T& rootValue ) if( !root )root = new TreeNode ( rootValue );50/判斷是否為空樹(shù)，如果是則返回判斷是否為空樹(shù)，如果是則返回truetemplate bool Tree:isEmpty ( )if ( root )return false;return true;51/私有成員函數(shù)，私有成員函數(shù)，返回返回current的父節(jié)點(diǎn)的父節(jié)點(diǎn)，由函數(shù)由函數(shù)Parent調(diào)用調(diào)用TreeNode* Tree:getParent( Tre

21、eNode* root, TreeNode* current )TreeNode* temp;if ( root = NULL )return NULL;if ( root-LeftMostChild ( ) = current ) return root;temp = getParent ( root-LeftMostChild( ), current );if( temp != NULL ) return temp;else return getParent ( root-RightSibling( ), current );52/Parent實(shí)現(xiàn)實(shí)現(xiàn)(遞歸遞歸)template /返回返

22、回current結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)TreeNode* Tree : Parent ( TreeNode* current )TreeNode* pointer = current; if ( pointer = NULL )return NULL;/查找查找current結(jié)點(diǎn)最左側(cè)的兄弟結(jié)點(diǎn)最左側(cè)的兄弟TreeNode* leftmostChild = NULL;leftmostChild = PrevSibling ( pointer ); while ( leftmostChild != NULL) pointer = leftmostChild;leftmostChild = Pr

23、evSibling ( pointer ); leftmostChild = pointer;pointer = root;if ( leftmostChild = root )return NULL;elsereturn getParent ( pointer , leftmostChild );53/Parent實(shí)現(xiàn)實(shí)現(xiàn)(遞歸遞歸)template /返回返回current結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)TreeNode* Tree : Parent ( TreeNode* current )TreeNode* pointer = current; if ( pointer != NULL )re

24、turn NULL;/查找查找current結(jié)點(diǎn)最左側(cè)的兄弟結(jié)點(diǎn)最左側(cè)的兄弟TreeNode* leftmostChild = NULL;leftmostChild = PrevSibling ( pointer ); while ( leftmostChild != NULL) pointer = leftmostChild;leftmostChild = PrevSibling ( pointer ); leftmostChild = pointer;pointer = root;if ( leftmostChild = root )return NULL;elsereturn getPa

25、rent ( pointer , leftmostChild );54/Parent實(shí)現(xiàn)實(shí)現(xiàn)(非遞歸非遞歸)template /返回返回current結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)TreeNode* Tree : Parent ( TreeNode* current )using std : queue;/使用使用STL隊(duì)列隊(duì)列queue TreeNode * aQueue;TreeNode * pointer = root; /指向其父結(jié)點(diǎn)指向其父結(jié)點(diǎn)TreeNode * upperlevelpointer = NULL;if ( current != NULL & pointer !=

26、NULL ) /待查找結(jié)點(diǎn)不空，也不是空樹(shù)或空森林待查找結(jié)點(diǎn)不空，也不是空樹(shù)或空森林while ( pointer != NULL ) /森林的所有根入隊(duì)森林的所有根入隊(duì)if ( current = pointer ) /待查結(jié)點(diǎn)為根待查結(jié)點(diǎn)為根return NULL;aQueue.push ( pointer );pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );aQueue.pop ( );upperlevelpointer = pointer;/指向上層

27、結(jié)點(diǎn)指向上層結(jié)點(diǎn)pointer = pointer - LeftMostChild ( ); while ( pointer ) if ( current = pointer ) return upperlevelpointer; else aQueue.push ( pointer ); pointer = pointer - RightSibling ( ); return NULL;55/Parent實(shí)現(xiàn)實(shí)現(xiàn)(非遞歸非遞歸)template /返回返回current結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)TreeNode* Tree : Parent ( TreeNode* current )using

28、 std : queue;/使用使用STL隊(duì)列隊(duì)列queue TreeNode * aQueue;TreeNode * pointer = root; /指向其父結(jié)點(diǎn)指向其父結(jié)點(diǎn)TreeNode * upperlevelpointer = NULL;if ( current != NULL & pointer != NULL ) /待查找結(jié)點(diǎn)不空，也不是空樹(shù)或空森林待查找結(jié)點(diǎn)不空，也不是空樹(shù)或空森林while ( pointer != NULL ) /森林的所有根入隊(duì)森林的所有根入隊(duì)if ( current = pointer ) /待查結(jié)點(diǎn)為根待查結(jié)點(diǎn)為根return NULL;aQ

29、ueue.push ( pointer );pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );aQueue.pop ( );upperlevelpointer = pointer;/指向上層結(jié)點(diǎn)指向上層結(jié)點(diǎn)pointer = pointer - LeftMostChild ( ); while ( pointer ) if ( current = pointer ) return upperlevelpointer; else aQueue.push ( po

30、inter ); pointer = pointer - RightSibling ( ); return NULL;56/Parent實(shí)現(xiàn)實(shí)現(xiàn)(非遞歸非遞歸)template /返回返回current結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)TreeNode* Tree : Parent ( TreeNode* current )using std : queue;/使用使用STL隊(duì)列隊(duì)列queue TreeNode * aQueue;TreeNode * pointer = root; /指向其父結(jié)點(diǎn)指向其父結(jié)點(diǎn)TreeNode * upperlevelpointer = NULL;if ( current

31、 != NULL & pointer != NULL ) /待查找結(jié)點(diǎn)不空，也不是空樹(shù)或空森林待查找結(jié)點(diǎn)不空，也不是空樹(shù)或空森林while ( pointer != NULL ) /森林的所有根入隊(duì)森林的所有根入隊(duì)if ( current = pointer ) /待查結(jié)點(diǎn)為根待查結(jié)點(diǎn)為根return NULL;aQueue.push ( pointer );pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );aQueue.pop ( );upperle

32、velpointer = pointer;/指向上層結(jié)點(diǎn)指向上層結(jié)點(diǎn)pointer = pointer - LeftMostChild ( ); while ( pointer ) if ( current = pointer ) return upperlevelpointer; else aQueue.push ( pointer ); pointer = pointer - RightSibling ( ); return NULL;57/樹(shù)類樹(shù)類PrevSibling實(shí)現(xiàn)實(shí)現(xiàn)template /返回返回current結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)TreeNode* Tree:

33、PrevSibling ( TreeNode* current )using std:queue; /使用使用STL隊(duì)列隊(duì)列queueTreeNode* aQueue;TreeNode* pointer=root; /標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)/標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)的前一個(gè)兄弟結(jié)點(diǎn)標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)的前一個(gè)兄弟結(jié)點(diǎn)TreeNode* prev=NULL; /當(dāng)前結(jié)點(diǎn)為空，樹(shù)為空或所求結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)，返回當(dāng)前結(jié)點(diǎn)為空，樹(shù)為空或所求結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)，返回NULLif ( ( current = NULL ) | ( pointer = NULL ) | ( current = pointer ) )return N

34、ULL;while ( pointer )if ( pointer = current )return prev; /找到當(dāng)前結(jié)點(diǎn)找到當(dāng)前結(jié)點(diǎn)aQueue.push ( pointer );prev = pointer;/沿當(dāng)前結(jié)點(diǎn)右兄弟鏈尋找沿當(dāng)前結(jié)點(diǎn)右兄弟鏈尋找pointer = pointer - pSibling;while ( ! aQueue.empty ( ) ) prev = NULL;pointer = aQueue.front ( );aQueue.pop ( ); /出隊(duì)出隊(duì)pointer = pointer-LeftMostChild( ); /下到左子結(jié)點(diǎn)下到左子結(jié)點(diǎn)

35、while ( pointer ) if ( pointer = current )return prev;aQueue.push ( pointer );prev = pointer; /沿當(dāng)前結(jié)點(diǎn)右鏈尋找沿當(dāng)前結(jié)點(diǎn)右鏈尋找pointer = pointer - pSibling; /end while /end whilereturn NULL;58/樹(shù)類樹(shù)類PrevSibling實(shí)現(xiàn)實(shí)現(xiàn)template /返回返回current結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)TreeNode* Tree:PrevSibling ( TreeNode* current )using std:que

36、ue; /使用使用STL隊(duì)列隊(duì)列queueTreeNode* aQueue;TreeNode* pointer=root; /標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)/標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)的前一個(gè)兄弟結(jié)點(diǎn)標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)的前一個(gè)兄弟結(jié)點(diǎn)TreeNode* prev=NULL; /當(dāng)前結(jié)點(diǎn)為空，樹(shù)為空或所求結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)，返回當(dāng)前結(jié)點(diǎn)為空，樹(shù)為空或所求結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)，返回NULLif ( ( current = NULL ) | ( pointer = NULL ) | ( current = pointer ) )return NULL;while ( pointer )if ( pointer = current )r

37、eturn prev; /找到當(dāng)前結(jié)點(diǎn)找到當(dāng)前結(jié)點(diǎn)aQueue.push ( pointer );prev = pointer;/沿當(dāng)前結(jié)點(diǎn)右兄弟鏈尋找沿當(dāng)前結(jié)點(diǎn)右兄弟鏈尋找pointer = pointer - pSibling;while ( ! aQueue.empty ( ) ) prev = NULL;pointer = aQueue.front ( );aQueue.pop ( ); /出隊(duì)出隊(duì)pointer = pointer-LeftMostChild( ); /下到左子結(jié)點(diǎn)下到左子結(jié)點(diǎn)while ( pointer ) if ( pointer = current )retu

38、rn prev;aQueue.push ( pointer );prev = pointer; /沿當(dāng)前結(jié)點(diǎn)右鏈尋找沿當(dāng)前結(jié)點(diǎn)右鏈尋找pointer = pointer - pSibling; /end while /end whilereturn NULL;59/樹(shù)類樹(shù)類PrevSibling實(shí)現(xiàn)實(shí)現(xiàn)template /返回返回current結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)結(jié)點(diǎn)的前一個(gè)鄰居結(jié)點(diǎn)TreeNode* Tree:PrevSibling ( TreeNode* current )using std:queue; /使用使用STL隊(duì)列隊(duì)列queueTreeNode* aQueue;TreeNode

39、* pointer=root; /標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)/標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)的前一個(gè)兄弟結(jié)點(diǎn)標(biāo)識(shí)當(dāng)前結(jié)點(diǎn)的前一個(gè)兄弟結(jié)點(diǎn)TreeNode* prev=NULL; /當(dāng)前結(jié)點(diǎn)為空，樹(shù)為空或所求結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)，返回當(dāng)前結(jié)點(diǎn)為空，樹(shù)為空或所求結(jié)點(diǎn)為根結(jié)點(diǎn)時(shí)，返回NULLif ( ( current = NULL ) | ( pointer = NULL ) | ( current = pointer ) )return NULL;while ( pointer )if ( pointer = current )return prev; /找到當(dāng)前結(jié)點(diǎn)找到當(dāng)前結(jié)點(diǎn)aQueue.push ( pointer

40、 );prev = pointer;/沿當(dāng)前結(jié)點(diǎn)右兄弟鏈尋找沿當(dāng)前結(jié)點(diǎn)右兄弟鏈尋找pointer = pointer - pSibling;while ( ! aQueue.empty ( ) ) prev = NULL;pointer = aQueue.front ( );aQueue.pop ( ); /出隊(duì)出隊(duì)pointer = pointer-LeftMostChild( ); /下到左子結(jié)點(diǎn)下到左子結(jié)點(diǎn)while ( pointer ) if ( pointer = current )return prev;aQueue.push ( pointer );prev = pointer

41、; /沿當(dāng)前結(jié)點(diǎn)右鏈尋找沿當(dāng)前結(jié)點(diǎn)右鏈尋找pointer = pointer - pSibling; /end while /end whilereturn NULL;60/樹(shù)類樹(shù)類DestroyNodes實(shí)現(xiàn)實(shí)現(xiàn)template void Tree:DestroyNodes ( TreeNode* root )/刪除以刪除以root為根的子樹(shù)的所有結(jié)點(diǎn)為根的子樹(shù)的所有結(jié)點(diǎn)if ( root ) /遞歸刪除第一子樹(shù)遞歸刪除第一子樹(shù)DestroyNodes ( root - LeftMostChild ( ) );/遞歸刪除其他子樹(shù)遞歸刪除其他子樹(shù)DestroyNodes ( root - Ri

42、ghtSibling ( ) ); delete root;/刪除根結(jié)點(diǎn)刪除根結(jié)點(diǎn)61/樹(shù)類DeleteSubTree實(shí)現(xiàn)template void Tree:DeleteSubTree ( TreeNode* subroot )/刪除以subroot為根的子樹(shù)的所有結(jié)點(diǎn)TreeNode* pointer;if ( subroot = NULL ) return;pointer = Parent ( subroot );if ( pointer = NULL ) /subroot為森林的第一個(gè)樹(shù)根 root = subroot - RightSibling ( );else /subroot為

43、最靠左子結(jié)點(diǎn) if ( pointer-LeftMostChild ( ) = subroot ) pointer-setChild( subroot-RightSibling( ) ); else /subroot有兄弟 pointer = pointer-LeftMostChild ( ); while ( pointer - RightSibling ( ) != subroot ) pointer = pointer - RightSibling ( ); pointer-setSibling( subroot-RightSibling( ) ); subroot-setSibling

44、( NULL ); DestroyNodes(subroot); /銷毀以subroot為根的子樹(shù)62/樹(shù)類DeleteSubTree實(shí)現(xiàn)template void Tree:DeleteSubTree ( TreeNode* subroot )/刪除以subroot為根的子樹(shù)的所有結(jié)點(diǎn)TreeNode* pointer;if ( subroot = NULL ) return;pointer = Parent ( subroot );if ( pointer = NULL ) /subroot為森林的第一個(gè)樹(shù)根 root = subroot - RightSibling ( );else /

45、subroot為最靠左子結(jié)點(diǎn) if ( pointer-LeftMostChild ( ) = subroot ) pointer-setChild( subroot-RightSibling( ) ); else /subroot有兄弟 pointer = pointer-LeftMostChild ( ); while ( pointer - RightSibling ( ) != subroot ) pointer = pointer - RightSibling ( ); pointer-setSibling( subroot-RightSibling( ) ); subroot-se

46、tSibling( NULL ); DestroyNodes(subroot); /銷毀以subroot為根的子樹(shù)63樹(shù)和森林的周游 樹(shù)和森林的周游分類 深度優(yōu)先周游 廣度優(yōu)先周游64深度優(yōu)先周游樹(shù) 深度優(yōu)先周游算法的基本思想是 盡可能的沿分支向深度方向進(jìn)行周游。 對(duì)樹(shù)和森林的周游可以有兩種： 先根次序周游 后根次序周游65深度優(yōu)先周游樹(shù)和森林 先根次序周游 訪問(wèn)頭一棵樹(shù)的根； 在先根次序下周游頭一棵樹(shù)根的子樹(shù)森林； 在先根次序下周游其它樹(shù)構(gòu)成的森林。 得到的結(jié)點(diǎn)有序序列稱為樹(shù)/森林的先根序列。66深度優(yōu)先周游樹(shù)和森林 后根次序周游 在后根次序下周游頭一棵樹(shù)根的子樹(shù)森林； 訪問(wèn)森林中第一顆樹(shù)的

47、根結(jié)點(diǎn)； 在后根次序下周游其它樹(shù)構(gòu)成的森林。 得到的結(jié)點(diǎn)有序序列稱為樹(shù)/森林的后根序列。67深度優(yōu)先周游二叉樹(shù) 例：先根次序遍歷：ABEFCGKLDHIJM后根次序遍歷：EFBKLGCHIMJDA68深度優(yōu)先周游二叉樹(shù) 例：69前序遍歷：ABEFCGKLDHIJM中序遍歷：EFBKLGCHIMJDA深度優(yōu)先周游樹(shù)和森林 結(jié)論 按先根次序周游森林正好等同于按前序法周游對(duì)應(yīng)的二叉樹(shù) 按后根次序周游森林正好等同于按中序法周游對(duì)應(yīng)的二叉樹(shù) 深度優(yōu)先周游樹(shù)和森林 補(bǔ)充 有的書(shū)把后根周游叫做中根周游，而后根周游則被定義為： 后根次序遍歷第一棵樹(shù)的子樹(shù)森林； 后根次序遍歷其它樹(shù)的構(gòu)成的森林； 訪問(wèn)第一棵樹(shù)的

48、根結(jié)點(diǎn)。71/先根遍歷樹(shù)和森林(遞歸實(shí)現(xiàn))templatevoid Tree: RootFirstTraverse ( TreeNode * root ) while ( root != NULL ) Visit ( root - value ( ) );/訪問(wèn)當(dāng)前結(jié)點(diǎn)/遍歷第一顆樹(shù)樹(shù)根的子樹(shù)RootFirstTraverse ( root - leftMostChild ( ) );root = root - RightSibling ( ) );/遍歷其它樹(shù)72/后根遍歷樹(shù)和森林(遞歸實(shí)現(xiàn))templatevoid Tree: RootLastTraverse ( TreeNode * r

49、oot ) while ( root != NULL ) RootLastTraverse ( root - leftMostChild ( ) );Visit ( root - value ( ) );root = root - RightSibling ( ) );73深度優(yōu)先周游樹(shù)和森林 作業(yè)： 給出深度優(yōu)先周游樹(shù)和森林的非遞歸算法， 給出其復(fù)雜度分析。74廣度優(yōu)先周游樹(shù)/森林 廣度優(yōu)先（寬度/層次）遍歷基本思想： 從樹(shù)的第一層（根結(jié)點(diǎn)）開(kāi)始，自上至下逐層遍歷； 在同一層中，按照從左到右的順序?qū)Y(jié)點(diǎn)逐一訪問(wèn)。 對(duì)于森林，把不同樹(shù)的根看作同層兄弟75/廣度優(yōu)先周游樹(shù)/森林template

50、void Tree:WidthTraverse ( TreeNode* root ) using std:queue;/使用STL隊(duì)列queueTreeNode* aQueue;TreeNode* pointer = root;while ( pointer != NULL ) aQueue.push ( pointer ); pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );/取隊(duì)首結(jié)點(diǎn) aQueue.pop ( ); Visit ( pointer - V

51、alue ( ) );/訪問(wèn)當(dāng)前結(jié)點(diǎn) pointer = pointer - LeftMostChild ( ); while ( pointer != NULL ) /當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn)入隊(duì) aQueue.push( pointer );pointer - RightSibling ( ); 76/廣度優(yōu)先周游樹(shù)/森林template void Tree:WidthTraverse ( TreeNode* root ) using std:queue;/使用STL隊(duì)列queueTreeNode* aQueue;TreeNode* pointer = root;while ( pointer !

52、= NULL ) aQueue.push ( pointer ); pointer = pointer - RightSibling ( );while ( ! aQueue.empty ( ) ) pointer = aQueue.front ( );/取隊(duì)首結(jié)點(diǎn) aQueue.pop ( ); Visit ( pointer - Value ( ) );/訪問(wèn)當(dāng)前結(jié)點(diǎn) pointer = pointer - LeftMostChild ( ); while ( pointer != NULL ) /當(dāng)前結(jié)點(diǎn)的子結(jié)點(diǎn)入隊(duì) aQueue.push( pointer );pointer - Ri

53、ghtSibling ( ); 77 算法分析 時(shí)間復(fù)雜度 如果訪問(wèn)函數(shù)處理時(shí)間是常數(shù)，則任何一種遍歷時(shí)間復(fù)雜度都為O(n)。 空間復(fù)雜度 所需輔助空間為遍歷時(shí)隊(duì)列的最大容量，即樹(shù)/森林的寬度（有最多結(jié)點(diǎn)的層）。最壞情況出現(xiàn)在有n個(gè)樹(shù)的森林中，所以空間復(fù)雜度為O(n)。廣度優(yōu)先周游二叉樹(shù)78樹(shù)/森林的其它存儲(chǔ)方式 “子結(jié)點(diǎn)表”表示法 靜態(tài)“左子/右兄”表示法 動(dòng)態(tài)表示法多重鏈表 父指針表示法 帶右鏈的先根次序表示 帶雙標(biāo)記的先根次序表示 帶度數(shù)的后根次序表示 帶雙標(biāo)記的層次次序表示子結(jié)點(diǎn)表表示法（帶雙親）612345789acdefghibdatafc 2 3 4 5 9 7 8 601223

54、5551parentabcdefhgi子結(jié)點(diǎn)表表示法（不帶雙親）6012345789acdefghibdata fc 2 3 4 5 9 7 8 6abcdefhgi靜態(tài)“左子/右兄”表示法 使用連續(xù)空間表示“左子/右兄”表示法LeftChildElementRightSiblingabcdefhgi靜態(tài)“左子/右兄”表示法135-16-1-1-1-1abcdefghi-12-14-1-178-1012345678LeftChildElement RightSibling靜態(tài)“左子/右兄”表示法 三重鏈表表示法 為了既能方便地從雙親查找孩子，又能方便地從孩子查找雙親，可以將雙親表示法和孩子兄弟

55、表示法結(jié)合起來(lái)，這就是三重鏈表表示法。這種方法中，每個(gè)結(jié)點(diǎn)有三個(gè)鏈域，形成三重鏈表，每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)為：LeftChildElementRightSiblingParent動(dòng)態(tài)表示法多重鏈表ABCDEFGABCDEFG data degreechild1child2childDdata child1child2childd父指針表示法 雙親表示：以一組連續(xù)空間存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在結(jié)點(diǎn)中附設(shè)一個(gè)指針，存放雙親結(jié)點(diǎn)在鏈表中的位置。ABCDEFGdataparentGFEDCBA311000-16543210靜態(tài)表示父指針表示法 (a) 雙親表示法示意圖；(b) 雙親表示法(鏈接存儲(chǔ))父指針表示法 作

56、業(yè) 實(shí)現(xiàn)并查集 思考： 為什么并查集適合使用父指針表示法實(shí)現(xiàn)？并給出理由。帶右鏈的先根次序表示 存儲(chǔ)方式 結(jié)點(diǎn)按先根次序順序存儲(chǔ)在一片連續(xù)的存儲(chǔ)單元中。 每個(gè)結(jié)點(diǎn)除包括結(jié)點(diǎn)本身數(shù)據(jù)外，還附加兩個(gè)表示結(jié)構(gòu)的信息字段，結(jié)點(diǎn)的形式為:帶右鏈的先根次序表示 存儲(chǔ)方式 各結(jié)點(diǎn)域含義為： info是結(jié)點(diǎn)的數(shù)據(jù)； rlink是右指針，指向結(jié)點(diǎn)的下一個(gè)兄弟、即對(duì)應(yīng)的二叉樹(shù)中結(jié)點(diǎn)的右子結(jié)點(diǎn)； ltag是一個(gè)左標(biāo)記，當(dāng)結(jié)點(diǎn)沒(méi)有子結(jié)點(diǎn)，即對(duì)應(yīng)的二叉樹(shù)中結(jié)點(diǎn)沒(méi)有左子結(jié)點(diǎn)時(shí)，ltag為1，否則為0。CDEF GIJ K LX 評(píng)價(jià)： 這種表示法與llinkrlink表示法相比，用ltag代替了llink，占用的存儲(chǔ)單元

57、要少些，但并不丟失信息； 可以從結(jié)點(diǎn)的次序和ltag的值完全可以推知llink； ltag為0的結(jié)點(diǎn)有左子結(jié)點(diǎn)，它的llink指向存儲(chǔ)區(qū)中該結(jié)點(diǎn)順序的下一個(gè)結(jié)點(diǎn) ltag為1的結(jié)點(diǎn)沒(méi)有左子結(jié)點(diǎn)，它的llink為空帶雙標(biāo)記的先根次序表示 基本思想 帶右鏈的先根次序表示法中每個(gè)結(jié)點(diǎn)都包括ltag和rlink字段，事實(shí)上rlink也不是必需的。代之以一位的rtag就足以表示出整個(gè)森林的結(jié)構(gòu)信息 規(guī)定：當(dāng)結(jié)點(diǎn)沒(méi)有下一個(gè)兄弟，即對(duì)應(yīng)的二叉樹(shù)中結(jié)點(diǎn)沒(méi)有右子結(jié)點(diǎn)時(shí)rtag為1，否則為0 帶雙標(biāo)記的先根次序表示1000010111infoltagH FD ECKA BJ G1010110011rtag 如何確

58、定結(jié)點(diǎn)的下一個(gè)兄弟？ 由結(jié)點(diǎn)的排列次序和ltag，rtag的值就可推知rlink的值。 當(dāng)結(jié)點(diǎn)x的rtag為1時(shí)，它的rlink顯然應(yīng)為空； 當(dāng)結(jié)點(diǎn)x的rtag為0時(shí)，它的rlink應(yīng)指向結(jié)點(diǎn)序列中排在結(jié)點(diǎn)x的子樹(shù)結(jié)點(diǎn)后面的那個(gè)結(jié)點(diǎn)y。帶雙標(biāo)記的先根次序表示 如何確定這個(gè)結(jié)點(diǎn)y呢？ 分析先根序列的特征 任何結(jié)點(diǎn)的子樹(shù)結(jié)點(diǎn)在先根序列中都排在該結(jié)點(diǎn)之后； 并且，任何結(jié)點(diǎn)的子樹(shù)結(jié)點(diǎn)，在先根序列中排在最后的一個(gè)結(jié)點(diǎn)一定沒(méi)有子結(jié)點(diǎn)，所以它的ltag為1帶雙標(biāo)記的先根次序表示 如何確定這個(gè)結(jié)點(diǎn)y呢？ 查找y的基本思想 在順序掃描帶雙標(biāo)記位的先根次序表示，試圖確定各結(jié)點(diǎn)的rlink值的過(guò)程中， 當(dāng)遇到一個(gè)r

59、tag為0的結(jié)點(diǎn)x時(shí)，要繼續(xù)往后掃描，在結(jié)點(diǎn)x的子樹(shù)結(jié)點(diǎn)中找ltag為1的、該子樹(shù)的最后一個(gè)結(jié)點(diǎn)， 序列中排在這個(gè)結(jié)點(diǎn)后面的那個(gè)結(jié)點(diǎn)就是結(jié)點(diǎn)x的rlink應(yīng)該指向的結(jié)點(diǎn)y 帶雙標(biāo)記的先根次序表示 最后一個(gè)問(wèn)題 由于先根次序表示的樹(shù)結(jié)構(gòu)是嵌套的，因此在掃描結(jié)點(diǎn)x的子樹(shù)結(jié)點(diǎn)序列找最后一個(gè)結(jié)點(diǎn)的過(guò)程中，極有可能遇到一棵更小的子樹(shù)的根結(jié)點(diǎn)x，它的rtag也等于0 即：如何確定x結(jié)點(diǎn)子樹(shù)的最后結(jié)點(diǎn)？帶雙標(biāo)記的先根次序表示 如何確定x結(jié)點(diǎn)子樹(shù)的最后結(jié)點(diǎn)？ 處理過(guò)程中需要用一個(gè)棧來(lái)記錄待配置rlink的結(jié)點(diǎn)， 其使用方法為： 掃描到一個(gè)rtag為0的結(jié)點(diǎn)就將其入棧； 掃描到一個(gè)ltag為1的結(jié)點(diǎn)就從棧頂彈出

60、一個(gè)結(jié)點(diǎn)并為其設(shè)置rling帶雙標(biāo)記的先根次序表示1000010111infoltagH FD ECKA BJ G1010110011rtag帶雙標(biāo)記的先根次序表示帶雙標(biāo)記的先根次序表示 評(píng)價(jià) 帶雙標(biāo)記位的先根次序表示法雖然比帶右鍵的先報(bào)次序表示法進(jìn)一步節(jié)省了存儲(chǔ)空間， 但由于需要額外的處理來(lái)推導(dǎo)失去的信息， 所以采用得更多的還是帶右鍵的先根次序表示法 /雙標(biāo)記位先根次序樹(shù)結(jié)點(diǎn)類templateclass DualTagTreeNode public:Tinfo;/樹(shù)結(jié)點(diǎn)信息intltag;/左標(biāo)記int rtag;/右標(biāo)記DualTagTreeNode();virtual DualTagTreeNode();/構(gòu)造templateDualTagTreeNode:DualTagT