樹(shù)二叉樹(shù)和森林

1、第6章樹(shù)與森林第 6章樹(shù)與森林6- 1 寫(xiě)出用廣義表表示法表示的樹(shù)的類(lèi)聲明，并給出如下成員函數(shù)的實(shí)現(xiàn)：(1) operator >> ( ) 接收用廣義表表示的樹(shù)作為輸入，建立廣義表的存儲(chǔ)表示；(2) 復(fù)制構(gòu)造函數(shù) 用另一棵表示為廣義表的樹(shù)初始化一棵樹(shù)；(3) operator = ( ) 測(cè)試用廣義表表示的兩棵樹(shù)是否相等；(4) operator << ( ) 用廣義表的形式輸出一棵樹(shù)；(5) 析構(gòu)函數(shù) 清除一棵用廣義表表示的樹(shù)?！窘獯稹?include <iostream.h>#define maxSubTreeNum 20;/最大子樹(shù) ( 子表 ) 個(gè)

2、數(shù)class GenTree;/GenTree 類(lèi)的前視聲明class GenTreeNode /廣義樹(shù)結(jié)點(diǎn)類(lèi)的聲明friend class GenTree;private:int utype;/結(jié)點(diǎn)標(biāo)志： =0, 數(shù)據(jù) ; =1, 子女GenTreeNode * nextSibling ;/utype=0, 指向第一個(gè)子女;/utype=1 或 2, 指向同一層下一兄弟union /聯(lián)合char RootData;/utype=0, 根結(jié)點(diǎn)數(shù)據(jù)char Childdata ;/utype=1, 子女結(jié)點(diǎn)數(shù)據(jù)GenTreeNode *firstChild ;/utype=2, 指向第一個(gè)子女的

3、指針public:GenTreeNode ( int tp, char item ) : utype (tp), nextSibling (NULL) if ( tp = 0 ) RootData = item ;else ChildData = item ; / 構(gòu)造函數(shù)：構(gòu)造廣義表表示的樹(shù)的數(shù)據(jù)結(jié)點(diǎn)GenTreeNode ( GenTreeNode *son = NULL ): utype (2), nextSibling (NULL), firstChild ( son ) / 構(gòu)造函數(shù)：構(gòu)造廣義表表示的樹(shù)的子樹(shù)結(jié)點(diǎn)int nodetype ( ) return utype ; char

4、 GetData ( ) return data; GenTreeNode * GetFchild ( ) return firstChild ; GenTreeNode * GetNsibling ( ) return nextSibling ; void setInfo ( char item ) data = item ; void setFchild ( GenTreeNode * ptr ) firstChild = ptr ; void setNsinbilg ( GenTreeNode * ptr ) nextSibling = ptr ; ;/返回結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型/返回?cái)?shù)據(jù)結(jié)點(diǎn)的

5、值/返回子樹(shù)結(jié)點(diǎn)的地址/返回下一個(gè)兄弟結(jié)點(diǎn)的地址/將結(jié)點(diǎn)中的值修改為item/將結(jié)點(diǎn)中的子樹(shù)指針修改為ptrclass GenTree /廣義樹(shù)類(lèi)定義private:GenTreeNode *first ;/根指針66第6章樹(shù)與森林char retValue;/建樹(shù)時(shí)的停止輸入標(biāo)志GenTreeNode *Copy ( GenTreeNode * ptr ) ;/復(fù)制一個(gè)ptr 指示的子樹(shù)void Traverse ( GenListNode * ptr ) ;/對(duì) ptr 為根的子樹(shù)遍歷并輸出void Remove ( GenTreeNode *ptr ) ;/將以 ptr 為根的廣義樹(shù)結(jié)構(gòu)

6、釋放friend int Equal ( GenTreeNode *s, GenTreeNode *t ) ;/比較以 s 和 t 為根的樹(shù)是否相等public:GenTree ( );/構(gòu)造函數(shù)GenTree ( GenTree& t ) ;/復(fù)制構(gòu)造函數(shù)GenTree ( );/析構(gòu)函數(shù)friend int operator = ( GenTree& t1, GenTree& t2 ) ;/判兩棵樹(shù)t1 與 t2 是否相等f(wàn)riend istream& operator >> ( istream& in, GenTree& t )

7、;/輸入friend ostream& operator << ( ostream& out, GenTree& t );/輸出(1) operator >> ( ) 接收用廣義表表示的樹(shù)作為輸入，建立廣義表的存儲(chǔ)表示istream& operator >> ( istream& in, GenTree& t ) / 友元函數(shù) , 從輸入流對(duì)象in 接受用廣義表表示的樹(shù)，建立廣義表的存儲(chǔ)表示t。t.ConstructTree ( in, retValue ) ;return in ;void GenTree :

8、 ConstructTree ( istream& in, char& value ) / 從輸入流對(duì)象 in 接受用廣義表表示的非空樹(shù)，建立廣義表的存儲(chǔ)表示t。Stack <GenTreeNode* > st (maxSubTreeNum) ;/用于建表時(shí)記憶回退地址GenTreeNode * p, q, r ;Type ch;cin >> value;/廣義樹(shù)停止輸入標(biāo)志數(shù)據(jù)cin >> ch ;first = q = new GenTreeNode ( 0, ch );/建立整個(gè)樹(shù)的根結(jié)點(diǎn)cin >> ch ;if ( ch

9、 = ( ) st.Push; ( q )/接著應(yīng)是 ( 進(jìn),棧cin >> ch;while ( ch != value ) /逐個(gè)結(jié)點(diǎn)加入switch ( ch ) case (: p = new GenTreeNode <Type> ( q );/建立子樹(shù) , p-> firstChild = qr = st.GetTop( ) ; st.Pop( );/從棧中退出前一結(jié)點(diǎn)r-> nextSibling = p ;/插在前一結(jié)點(diǎn) r 之后st.Push( p ); st.Push( q );/子樹(shù)結(jié)點(diǎn)及子樹(shù)根結(jié)點(diǎn)進(jìn)棧break;case ): q-&g

10、t; nextSibling = NULL; st.pop( ) ;/子樹(shù)建成 , 封閉鏈 , 退到上層if ( st.IsEmpty ( ) = 0 )q = st.GetTop( );/棧不空 , 取上層鏈子樹(shù)結(jié)點(diǎn)else return 0;/?？?, 無(wú)上層鏈 , 算法結(jié)束break;case ,: break;default : p = q;if ( isupper (ch) ) q = new GenTreeNode ( 0, ch );/大寫(xiě)字母 , 建根結(jié)點(diǎn)67第6章樹(shù)與森林else q = new GenTreeNode ( 1, ch );/非大寫(xiě)字母 , 建數(shù)據(jù)結(jié)點(diǎn)p-&g

11、t; nextSibling = q ;/鏈接cin >> ch;(2) 復(fù)制構(gòu)造函數(shù) 用另一棵表示為廣義表的樹(shù)初始化一棵樹(shù)；GenTree : GenTree ( const GenTree& t ) /共有函數(shù)first = Copy ( t.first ) ;GenTreeNode* GenTree : Copy ( GenTreeNode *ptr ) / 私有函數(shù)，復(fù)制一個(gè) ptr 指示的用廣義表表示的子樹(shù)GenTreeNode *q = NULL ;if ( ptr != NULL )q = new GenTreeNode ( ptr-> utype, N

12、ULL ) ;switch ( ptr ->utype ) /根據(jù)結(jié)點(diǎn)類(lèi)型utype 傳送值域case 0 : q-> RootData = ptr -> RootData;break;/傳送根結(jié)點(diǎn)數(shù)據(jù)case 1 : q-> ChildData = ptr -> ChildData ;break;/傳送子女結(jié)點(diǎn)數(shù)據(jù)case2 : q-> firstChild = Copy (ptr -> firstChild ) ;break;/遞歸傳送子樹(shù)信息q-> nextSibling = Copy ( ptr -> nextSibling ) ;

13、/復(fù)制同一層下一結(jié)點(diǎn)為頭的表return q;(3) operator = ( ) 測(cè)試用廣義表表示的兩棵樹(shù)是否相等int operator = ( GenTree & t1, GenTree& t2 ) / 友元函數(shù) : 判兩棵樹(shù) t1 與 t2 是否相等 , 若兩表完全相等 , 函數(shù)返回 1, 否則返回 0。return Equal ( t1.first, t2.first ) ;int Equal ( GenTreeNode *t1, GenTreeNode *t2 ) / 是 GenTreeNode 的友元函數(shù) int x;ifif( t1= NULL&&

14、; t2 = NULL ) return 1;/表 t1 與表 t2 都是空樹(shù) , 相等( t1!= NULL&& t2 != NULL && t1-> utype = t2 -> utype ) /兩子樹(shù)都非空且結(jié)點(diǎn)類(lèi)型相同switch ( t1-> utype ) /比較對(duì)應(yīng)數(shù)據(jù)case0 : x = ( t1-> RootData = t2 -> RootData ) ? 1 : 0;/根數(shù)據(jù)結(jié)點(diǎn)break;case1 : x = ( t1 -> ChildData = t2 -> ChildData ) ? 1

15、: 0;/子女?dāng)?shù)據(jù)結(jié)點(diǎn)break;68第6章樹(shù)與森林case2 : x = Equal ( t1 -> firstChild,t2-> firstChild ) ;/遞歸比較其子樹(shù)if ( x ) return Equal ( t1-> nextSibling,t2-> nextSibling ) ;/相等 , 遞歸比較同一層的下一個(gè)結(jié)點(diǎn); 不等 , 不再遞歸比較return 0;(4) operator << ( ) 用廣義表的形式輸出一棵樹(shù)ostream& operator << ( ostream& out, GenTree

16、& t ) / 友元函數(shù) , 將樹(shù) t 輸出到輸出流對(duì)象 out。t.traverse ( out, t.first ) ;return out;void GenTree : traverse ( ostream& out, GenTreeNode * ptr ) / 私有函數(shù) , 廣義樹(shù)的遍歷算法if ( ptr != NULL )if ( ptr -> utype = 0 ) out << ptr -> RootData << ( /根數(shù)據(jù)結(jié)點(diǎn)else if ( ptr -> utype = 1 ) /子女?dāng)?shù)據(jù)結(jié)點(diǎn)out <&

17、lt; ptr -> ChildData ;if ( ptr-> nextSibling != NULL ) out << , else /子樹(shù)結(jié)點(diǎn)traverse ( ptr-> firstChild ) ;/向子樹(shù)方向搜索if ( ptr-> nextSibling != NULL ) out << , traverse ( ptr-> nextSibling ) ;/向同一層下一兄弟搜索else out << ) (5) 析構(gòu)函數(shù) 清除一棵用廣義表表示的樹(shù)GenTree : GenTree ( ) / 用廣義表表示的樹(shù)的析

18、構(gòu)函數(shù) , 假定 first NULL Remove ( first ) ;void GenTree : Remove ( GenTreeNode *ptr ) GenTreeNode * p;while ( ptr != NULL )p = ptr-> nextSibling ;if ( p-> utype = 2 ) Remove ( p -> firstChild ) ;/在子樹(shù)中刪除69第6章樹(shù)與森林ptr-> nextSibling = p -> nextSibling ;delete ( p );/釋放結(jié)點(diǎn)p6- 2 列出右圖所示二叉樹(shù)的葉結(jié)點(diǎn)、分支結(jié)

19、點(diǎn)和每個(gè)結(jié)點(diǎn)的層次。【解答】二叉樹(shù)的葉結(jié)點(diǎn)有、。分支結(jié)點(diǎn)有、。結(jié)點(diǎn)的層次為 0；結(jié)點(diǎn)、的層次為 1；結(jié)點(diǎn)、的層次為 2；結(jié)點(diǎn)、的層次為 3；結(jié)點(diǎn)的層次為 4。6- 3 使用(1) 順序表示和(2) 二叉鏈表表示法，分別畫(huà)出右圖所示二叉樹(shù)的存儲(chǔ)表示?！窘獯稹?123456789 1011121314151617 18 順序表示 二叉鏈表表示6- 4 用嵌套類(lèi)寫(xiě)出用鏈表表示的二叉樹(shù)的類(lèi)聲明?！窘獯稹?include <iostream.h>template <class Type> classBinaryTree private:template <class Typ

20、e> classBinTreeNode public:BinTreeNode< Type> *leftChild , *rightChild ;Type data;Type RefValue;BinTreeNode< Type> * root ;BinTreeNode< Type> *Parent ( BinTreeNode< Type> *start, BinTreeNode< Type> *current ) ; int Insert ( BinTreeNode< Type> *current, const Ty

21、pe& item );int Find ( BinTreeNode< Type> *current, const Type& item ) const;void destroy ( BinTreeNode< Type> *current ) ;void Traverse ( BinTreeNode< Type> *current, ostream& out ) const;public:BinaryTree ( ) : root ( NULL ) BinaryTree ( Type value ) : RefValue ( value

22、 ), root ( NULL ) BinaryTree ( ) destroy (root) ; BinTreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) BinTreeNode ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL ) 70第6章樹(shù)與森林Type& GetData ( ) const return data; BinTreeNode< Type>* GetLeft ( )const return leftChild

23、 ; BinTreeNode< Type>* GetRight ( )const return rightChild ; void SetData ( const Type& item ) data = item; void SetLeft ( BinTreeNode< Type> *L ) leftChild = L ; void SetRight ( BinTreeNode< Type> *R ) RightChild =R ; int IsEmpty ( ) return root = NULL? 1 : 0; BinTreeNode<

24、Type> *Parent ( BinTreeNode< Type> *current ) return root = NULL | root = current ? NULL : Parent ( root, current ) ; BinTreeNode< Type> * LeftChild ( BinTreeNode< Type> *current ) return current != NULL ? current-> leftChild : NULL ; BinTreeNode< Type> * RighttChild (

25、BinTreeNode<Type> *current ) return current != NULL? current-> rightChild : NULL ; int Insert ( const Type& item ) ;BinTreeNode< Type> * Find (const Type& item );BinTreeNode< Type> * GetRoot ( ) const return root; friend istream& operator >> ( istream& in,

26、BinaryTree< Type>& Tree );/輸入二叉樹(shù)friend ostream& operator << ( ostream& out, BinaryTree< Type>& Tree );/輸出二叉樹(shù)6- 5 在結(jié)點(diǎn)個(gè)數(shù)為n (n>1) 的各棵樹(shù)中， 高度最小的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？【解答】結(jié)點(diǎn)個(gè)數(shù)為 n 時(shí)，高度最小的樹(shù)的高度為 1，有 2 層；它有 n- 1 個(gè)葉結(jié)點(diǎn)， 1 個(gè)分支結(jié)點(diǎn)；高度最大的樹(shù)的高度為 n-

27、1，有 n 層；它有 1 個(gè)葉結(jié)點(diǎn)， n- 1 個(gè)分支結(jié)點(diǎn)。66試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。-【解答】具有 3 個(gè)結(jié)點(diǎn)的樹(shù)具有 3 個(gè)結(jié)點(diǎn)的二叉樹(shù)6- 7 如果一棵樹(shù)有n1 個(gè)度為 1 的結(jié)點(diǎn) , 有 n2 個(gè)度為 2 的結(jié)點(diǎn) , nm 個(gè)度為 m 的結(jié)點(diǎn) , 試問(wèn)有多少個(gè)度為 0 的結(jié)點(diǎn) ? 試推導(dǎo)之?！窘獯稹靠偨Y(jié)點(diǎn)數(shù) n = n 0 + n1 + n2 + n m總分支數(shù) e = n- 1 = n0 + n1 + n 2 + n m- 1= m*n m + (m - 1)*n m- 1 + 2*n 2 + n 1m則有n0(i1)ni1i271第6章樹(shù)與森林

28、6- 8 試分別找出滿足以下條件的所有二叉樹(shù):(1) 二叉樹(shù)的前序序列與中序序列相同;(2) 二叉樹(shù)的中序序列與后序序列相同;(3) 二叉樹(shù)的前序序列與后序序列相同。【解答】(1) 二叉樹(shù)的前序序列與中序序列相同：空樹(shù)或缺左子樹(shù)的單支樹(shù)；(2) 二叉樹(shù)的中序序列與后序序列相同：空樹(shù)或缺右子樹(shù)的單支樹(shù)；(3) 二叉樹(shù)的前序序列與后序序列相同：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。6- 9 若用二叉鏈表作為二叉樹(shù)的存儲(chǔ)表示，試針對(duì)以下問(wèn)題編寫(xiě)遞歸算法：(1) 統(tǒng)計(jì)二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)。(2) 以二叉樹(shù)為參數(shù)，交換每個(gè)結(jié)點(diǎn)的左子女和右子女?！窘獯稹?1) 統(tǒng)計(jì)二叉樹(shù)中葉結(jié)點(diǎn)個(gè)數(shù)int BinaryTree &l

29、t;Type> : leaf ( BinTreeNode <Type> * ptr ) if ( ptr = NULL )return 0;else if ( ptr -> leftChild = NULL && ptr-> rightChild = NULL ) return 1; else return leaf ( ptr -> leftChild ) + leaf ( ptr -> rightChild ) ;(2) 交換每個(gè)結(jié)點(diǎn)的左子女和右子女void BinaryTree <Type> : exchange (

30、BinTreeNode<Type> * ptr ) BinTreeNode <Type> * temp ;if ( ptr -> leftChild != NULL|ptr -> rightChild != NULL )temp = ptr -> leftChild ;ptr-> leftChild = ptr -> rightChild ;ptr-> rightChild = temp ;exchange ( ptr-> leftChild ) ;exchange ( ptr-> rightChild ) ;6- 10

31、一棵高度為 h 的滿 k 叉樹(shù)有如下性質(zhì) : 第 h 層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn), 其余各層上每個(gè)結(jié)點(diǎn)都有k 棵非空子樹(shù) , 如果按層次自頂向下, 同一層自左向右 , 順序從 1 開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào), 試問(wèn):(1)各層的結(jié)點(diǎn)個(gè)數(shù)是多少?(2)編號(hào)為 i 的結(jié)點(diǎn)的父結(jié)點(diǎn) ( 若存在 )的編號(hào)是多少 ?(3)編號(hào)為 i 的結(jié)點(diǎn)的第 m 個(gè)孩子結(jié)點(diǎn) (若存在 )的編號(hào)是多少 ?(4)編號(hào)為 i 的結(jié)點(diǎn)有右兄弟的條件是什么? 其右兄弟結(jié)點(diǎn)的編號(hào)是多少 ?(5)若結(jié)點(diǎn)個(gè)數(shù)為 n, 則高度 h 是 n 的什么函數(shù)關(guān)系 ?【解答】(1)ki( i = 0, 1, h )(2)ik2k72第6章樹(shù)與森林(3)

32、( i- 1)*k + m + 1(4)( i- 1 ) % k 0或 ii k 2 * k 時(shí)有右兄弟，右兄弟為 i + 1 。k(5)h = log k (n*(k -1)+1) - 1(n = 0 時(shí) h = - 1 )6- 11 試用判定樹(shù)的方法給出在中序線索化二叉樹(shù)上：【解答】(1) 搜索指定結(jié)點(diǎn)的在中序下的后繼。設(shè)指針 q 指示中序線索化二叉樹(shù)中的指定結(jié)點(diǎn)，指針p 指示其后繼結(jié)點(diǎn)。q-> rightThread = 1?=q-> rightChild = NULL ?q 的后繼為 q 的右子樹(shù)中=中序下的第一個(gè)結(jié)點(diǎn)q 無(wú)后繼q 的后繼為 q-> rightChil

33、d找 q 的右子樹(shù)中在中序下的第一個(gè)結(jié)點(diǎn)的程序?yàn)椋簆 = q-> rightChild ;while ( p-> leftThread = 1 ) p = p -> leftChild ;/ p 即為 q 的后繼(2) 搜索指定結(jié)點(diǎn)的在前序下的后繼。q-> leftThread = 0 ?=q 的后繼為 q-> leftChildq 的后繼為q-> rightThread = 0 ?=q-> rightChildp = q;while ( p-> rightThread =1 &&p-> rightChild ! = NUL

34、L ) p = p -> rightChild ;if ( p-> rightChild =NULL ) q無(wú)后繼 ;else的后繼為 p-> rightChild(3) 搜索指定結(jié)點(diǎn)的在后序下的后繼。( p = parent (q ) ) = NULL ?=q 無(wú)后繼p-> rightThread =1 |p-> rightChild = q ?=q 的后繼為pq 的后繼為 p 的右子樹(shù)中后序下的第一個(gè)結(jié)點(diǎn)可用一段遍歷程序來(lái)實(shí)現(xiàn)尋找p 的右子樹(shù)中后序下的第一個(gè)結(jié)點(diǎn)：即該子樹(shù)第一個(gè)找到的葉結(jié)點(diǎn)。找到后立即返回它的地址。6- 12 已知一棵完全二叉樹(shù)存放于一個(gè)一維數(shù)

35、組Tn 中， Tn 中存放的是各結(jié)點(diǎn)的值。試設(shè)計(jì)一個(gè)算法，從 T0 開(kāi)始順序讀出各結(jié)點(diǎn)的值，建立該二叉樹(shù)的二叉鏈表表示?！窘獯稹縯emplate <class Type>/ 建立二叉樹(shù)istream& operator >> ( istream& in, BinaryTree< Type>& t ) int n;cout << "Please enter the number of node : "in >> n ;73第6章樹(shù)與森林Type *A = new Typen+1 ;for (

36、int i = 0 ; i < n ; i+ ) in >> Ai;t. ConstructTree( T, n, 0, ptr ) ;/ 以數(shù)組建立一棵二叉樹(shù)delete A ;return in;template <class Type>void BinaryTree< Type> : ConstructTree ( Type T , int n, int i, BinTreeNode< Type> * & ptr ) / 私有函數(shù): 將用 Tn 順序存儲(chǔ)的完全二叉樹(shù), 以 i 為根的子樹(shù)轉(zhuǎn)換成為用二叉鏈表表示的/ 以 ptr

37、為根的完全二叉樹(shù)。利用引用型參數(shù)ptr 將形參的值帶回實(shí)參。if ( i >= n ) ptr = NULL ;else ptr = new BinTreeNode< Type> ( Ti ) ;/建立根結(jié)點(diǎn)ConstructTree ( T, n, 2*i+1, ptr -> leftChild ) ;ConstructTree ( T, n, 2*i+2, ptr -> rightChild ) ;6- 13 試編寫(xiě)一個(gè)算法，把一個(gè)新結(jié)點(diǎn)l 作為結(jié)點(diǎn)s 的左子女插入到一棵中序線索化二叉樹(shù)中，s 原來(lái)的左子女變成l 的左子女?！窘獯稹縯emplate<cl

38、ass Type>void ThreadTree<Type> : leftInsert ( ThreadNode< Type> *s, ThreadNode< Type> * l ) if ( s != NULL && l != NULL )l -> leftChild = s -> leftChild ;l -> leftThread = s-> leftThread ;/預(yù)先鏈接l -> rightChild = s ;l -> rightThread = 1 ;/ 新插入結(jié)點(diǎn) *l 的后繼為 *

39、ss-> leftChild = l ;s-> leftThread = 0 ;/*l 成為 *s 的左子女if ( l -> leftThread = 0 ) /*l 的左子女存在ThreadNode<Type> * p = l -> leftChild ;while ( p-> rightThread = 0 )/找 *l 的左子樹(shù)中序下最后一個(gè)結(jié)點(diǎn)p = p-> rightChild ;p-> rightChild = l ;/ 該結(jié)點(diǎn)的后繼為*l6- 14 寫(xiě)出向堆中加入數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 14 時(shí)，每加

40、入一個(gè)數(shù)據(jù)后堆的變化?！窘獯稹恳宰钚《褳槔?422222445454588374第6章樹(shù)與森林222235353535848468461084610146- 16 請(qǐng)畫(huà)出右圖所示的樹(shù)所對(duì)應(yīng)的二叉樹(shù)?！窘獯稹?1223對(duì)應(yīng)二叉樹(shù)434556768876- 17 在森林的二叉樹(shù)表示中，用llink 存儲(chǔ)指向結(jié)點(diǎn)第一個(gè)子女的指針，用 rlink 存儲(chǔ)指向結(jié)點(diǎn)下一個(gè)兄弟的指針，用 data 存儲(chǔ)結(jié)點(diǎn)的值。如果我們采用靜態(tài)二叉鏈表作為森林的存儲(chǔ)表示，同時(shí)按森林的先根次序依次安放森林的所有結(jié)點(diǎn)，則可以在它們的結(jié)點(diǎn)中用只有一個(gè)二進(jìn)位的標(biāo)志ltag 代替 llink ，用 rtag代替 rlink 。并設(shè)定

41、若 ltag =0 ，則該結(jié)點(diǎn)沒(méi)有子女，若ltag 0，則該結(jié)點(diǎn)有子女；若rtag = 0 ，則該結(jié)點(diǎn)沒(méi)有下一個(gè)兄弟，若rtag0，則該結(jié)點(diǎn)有下一個(gè)兄弟。試給出這種表示的結(jié)構(gòu)定義，并設(shè)計(jì)一個(gè)算法，將用這種表示存儲(chǔ)的森林轉(zhuǎn)換成用llink- rlink表示的森林?！窘獯稹緼AFHBFBCDGIJ對(duì)應(yīng)二叉樹(shù)CGHEKDI012345678910EKJllink1-1-14-16-189-1-1dataABCDEFGHIKJ森林的左子女 - 右兄弟rlink523-1-17-1-110-1-1表示的靜態(tài)二叉鏈表012345678910ltag10010101100dataABCDEFGHIKJ森林的

42、雙標(biāo)記表示rtag11100100100(1)結(jié)構(gòu)定義template <class Type> classLchRsibNode /左子女 - 右兄弟鏈表結(jié)點(diǎn)類(lèi)的定義protected:Type data;/結(jié)點(diǎn)數(shù)據(jù)int llink, rlink ;/結(jié)點(diǎn)的左子女、右兄弟指針75第6章樹(shù)與森林public:LchRsibNode ( ) : llink(NULL), rlink(NULL) LchRsibNode ( Type x ) : llink(NULL), rlink(NULL), data(x) template <class Type> classDou

43、blyTagNode /雙標(biāo)記表結(jié)點(diǎn)類(lèi)的定義protected:Type data;/結(jié)點(diǎn)數(shù)據(jù)int ltag, rtag ;/結(jié)點(diǎn)的左子女、右兄弟標(biāo)記public:DoublyTagNode ( ) : ltag(0), rtag(0) DoublyTagNode ( Type x ) : ltag(0), rtag(0), data(x) template <class Type> classstaticlinkList/靜態(tài)鏈表類(lèi)定義: public LchRsibNode <Type>, public DoublyTagNode <Type> pri

44、vate:LchRsibNode< Type> *V ;/存儲(chǔ)左子女 - 右兄弟鏈表的向量DoublyTagNode <Type> *U ;/存儲(chǔ)雙標(biāo)記表的向量int MaxSize , CurrentSize;/向量中最大元素個(gè)數(shù)和當(dāng)前元素個(gè)數(shù)public:dstaticlinkList ( int Maxsz ) : MaxSize ( Maxsz ), CurrentSize (0) V = new LchRsibNode < Type> Maxsz ;U = new DoublyTagNode < Type> Maxsz ;(2) 森林的

45、雙標(biāo)記先根次序表示向左子女- 右兄弟鏈表先根次序表示的轉(zhuǎn)換void staticlinkList< Type> : DtagF - LchRsibF ( ) Stack<int> st;int k ;for ( int i = 0 ;i < CurrentSize ;i+ ) switch ( Ui.ltag ) case 0 : switch ( Ui.rtag ) case 0 :Vi.llink = Vi.rlink =- 1;if ( st.IsEmpty ( ) = 0 ) k = st.GetTop ( );st.Pop ( );Vk.rlink =

46、i + 1; break;case 1 :Vi.llink =- 1;Vi.rlink = i + 1;break;break;case 1 : switch ( Ui.rtag ) case 0 :Vi.llink = i + 1case 1 :Vi.llink = i + 1;Vi.rlink =- 1;break;st.Push ( i );76第6章樹(shù)與森林6- 18 二叉樹(shù)的雙序遍歷 (Double - order traversal)是指：對(duì)于二叉樹(shù)的每一個(gè)結(jié)點(diǎn)來(lái)說(shuō)，先訪問(wèn)這個(gè)結(jié)點(diǎn)，再按雙序遍歷它的左子樹(shù)，然后再一次訪問(wèn)這個(gè)結(jié)點(diǎn)，接下來(lái)按雙序遍歷它的右子樹(shù)。試寫(xiě)出執(zhí)行這種雙序遍歷的算法?！窘獯稹縯emplate <class Type>void BinaryTree< Type> : Double_order ( BinTreeNode< Type>