樹二叉樹和森林

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

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

3、ype (tp), nextSibling (NULL) if ( tp = 0 ) RootData = item ; elseChildData = item ; /構(gòu)造函數(shù)：構(gòu)造廣義表表示的樹的數(shù)據(jù)結(jié)點GenTreeNode ( GenTreeNode *son = NULL ) : utype (2), nextSibling (NULL), firstChild ( son ) /構(gòu)造函數(shù)：構(gòu)造廣義表表示的樹的子樹結(jié)點/返回結(jié)點的數(shù)據(jù)類型/返回數(shù)據(jù)結(jié)點的值/返回子樹結(jié)點的地址/返回下一個兄弟結(jié)點的地址/將結(jié)點中的值修改為itemII將結(jié)點中的子樹指針修改為ptrII廣義樹類定義II根

4、指針int nodetype ( ) return utype;char 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 ) next

5、Sibling = ptr; ；classGenTree private:GenTreeNode *first ；建樹時的停止輸入標(biāo)志復(fù)制一個ptr指示的子樹對ptr為根的子樹遍歷并輸出/將以ptr為根的廣義樹結(jié)構(gòu)釋放/比較以s和t為根的樹是否相等/構(gòu)造函數(shù)復(fù)制構(gòu)造函數(shù)析構(gòu)函數(shù)判兩棵樹t1與t2是否相等/輸入/輸岀char retValue;GenTreeNode *Copy ( GenTreeNode * ptr );void Traverse ( GenListNode * ptr )；void Remove ( GenTreeNode *ptr )；friend int Equal (

6、GenTreeNode *s, GenTreeNode *t );public:GenTree ();GenTree ( GenTree& t );GenTree ();friend int operator = ( GenTree& t1, GenTree& t2 );friend istream& operator >> ( istream& in, GenTree& t ); friend ostream& operator << ( ostream& out, GenTree& t );(1

7、) operator >> ()接收用廣義表表示的樹作為輸入，建立廣義表的存儲表示istream& operator >> ( istream& in, GenTree& t ) /友元函數(shù)，從輸入流對象in接受用廣義表表示的樹，建立廣義表的存儲表示tt.ConstructTree ( in, retValue );return in;void GenTree : ConstructTree ( istream& in, char& value ) /從輸入流對象in接受用廣義表表示的非空樹，建立廣義表的存儲表示tStack &l

8、t;GenTreeNode* > st (maxSubTreeNum);/用于建表時記憶回退地址GenTreeNode * p, q, r; Type ch;cin >> value;/廣義樹停止輸入標(biāo)志數(shù)據(jù)cin >> ch; first = q = new GenTreeNode ( 0, ch );建立整個樹的根結(jié)點cin >> ch; if ( ch = (' ) st.Push ( q )/接著應(yīng)是(進棧cin >> ch;while ( ch != value ) /逐個結(jié)點加入switch ( ch ) case (:

9、' p = new GenTreeNode vType> ( q );/建立子樹,p-> firstChild = qr = st.GetTop( ); st.Pop();/從棧中退出前一結(jié)點r-> nextSibling = p ;/插在前一結(jié)點r之后st.Push( p );st.Push( q );子樹結(jié)點及子樹根結(jié)點進棧break;case ):' q-> nextSibling = NULL ; st.pop();子樹建成，封閉鏈，退到上層if ( st.IsEmpty ( ) = 0 ) q = st.GetTop();/棧不空，取上層鏈子樹

10、結(jié)點else return 0;/?？?，無上層鏈，算法結(jié)束break;case ；' break;default : p = q;if ( isupper (ch) ) q = new GenTreeNode ( 0, ch );/大寫字母，建根結(jié)點else q = new GenTreeNode ( 1, ch ); p-> nextSibling = q ;cin >> ch;非大寫字母，建數(shù)據(jù)結(jié)點/鏈接(2) 復(fù)制構(gòu)造函數(shù)用另一棵表示為廣義表的樹初始化一棵樹；GenTree : GenTree ( const GenTree& t ) / 共有函數(shù)fir

11、st = Copy ( t.first );GenTreeNode* GenTree : Copy ( GenTreeNode *ptr ) /私有函數(shù)，復(fù)制一個ptr指示的用廣義表表示的子樹GenTreeNode *q = NULL ;if ( ptr != NULL ) q = new GenTreeNode ( ptr-> utype, NULL );switch ( ptr->utype ) case。: q-> RootData = ptr-> RootData； break;case1 : q-> ChildData = ptr -> Child

12、Data; break;case2 : q->firstChild = Copy ( ptr-> firstChild ) ; break;q-> nextSibling = Copy ( ptr -> nextSibling )；return q;(3) operator =()測試用廣義表表示的兩棵樹是否相等 int operator = ( GenTree & t1, GenTree& t2 ) 函數(shù)返回1,否則返回0。/友元函數(shù)：判兩棵樹t1與t2是否相等，若兩表完全相等return Equal ( tl.first, t2.first ); i

13、nt Equal ( GenTreeNode *t1, GenTreeNode *t2 ) /是GenTreeNode的友元函數(shù)int x;if ( t1 = NULL && t2 = NULL ) return 1;if ( t1 != NULL && t2 != NULL && t1-> utype = t2 -> utype ) switch (t1 -> utype ) caseO : x = ( t1-> RootData = t2-> RootData ) ? 1 : 0;break;case1 : x

14、= ( t1 -> ChildData = t2 -> ChildData ) ? 1 : 0;/根據(jù)結(jié)點類型utype傳送值域/傳送根結(jié)點數(shù)據(jù)/傳送子女結(jié)點數(shù)據(jù)/遞歸傳送子樹信息復(fù)制同一層下一結(jié)點為頭的表/表t1與表t2都是空樹，相等兩子樹都非空且結(jié)點類型相同/比較對應(yīng)數(shù)據(jù)/根數(shù)據(jù)結(jié)點子女?dāng)?shù)據(jù)結(jié)點break;case2 : x = Equal ( t1 -> firstChild, t2->firstChild );if ( x ) return Equal ( t1-> nextSibling, t2-> nextSibling )；/相等，遞歸比較同一

15、層的下一個結(jié)點；不等,return 0;operator << ()用廣義表的形式輸出一棵樹ostream& operator << ( ostream& out, GenTree& t ) /友元函數(shù)，將樹t輸岀到輸岀流對象out。t.traverse ( out, t.first );return out;void GenTree : traverse ( ostream& out, GenTreeNode * ptr ) /私有函數(shù)，廣義樹的遍歷算法if ( ptr != NULL ) if ( ptr-> utype = 0

16、 ) out << ptr-> RootData <<('else if ( ptr-> utype = 1 ) out << ptr-> ChildData;if ( ptr-> nextSibling != NULL ) out <<','else traverse ( ptr->firstChild );if ( ptr-> nextSibling != NULL ) out <<','traverse ( ptr-> nextSibling );

17、else out <<)'(5)析構(gòu)函數(shù)清除一棵用廣義表表示的樹GenTree :GenTree ( ) /用廣義表表示的樹的析構(gòu)函數(shù)，假定first工NULLRemove ( first );void GenTree : Remove ( GenTreeNode *ptr ) GenTreeNode * p;while ( ptr != NULL ) p = ptr-> nextSibling ;/遞歸比較其子樹不再遞歸比較/根數(shù)據(jù)結(jié)點子女?dāng)?shù)據(jù)結(jié)點子樹結(jié)點/向子樹方向搜索/向同一層下一兄弟搜索/在子樹中刪除if ( p-> utype = 2 ) Remove

18、 ( p->firstChild );ptr-> nextSibling = p -> nextSibling;delete( p );/釋放結(jié)點 p6-2列出右圖所示二叉樹的葉結(jié)點、分支結(jié)點和每個結(jié)點的層次。【解答】二叉樹的葉結(jié)點有、。分支結(jié)點有、。結(jié)點的層次為0；結(jié)點、的層次為1;結(jié)點、的層次為2;結(jié)點、的層次為3;結(jié)點的層次為4。6-3使用(1)順序表示和(2)二叉鏈表表示法，分別畫出右圖所示二叉樹的存儲表示。【解答】6-4用嵌套類寫出用鏈表表示的二叉樹的類聲明?！窘獯稹?include <iostream.h>template vclass Typecla

19、ssBinaryTree private:template vclass Type> classBinTreeNode public:BinTreeNodev Type> *leftChild , *rightChild ;Type data;Type RefValue;BinTreeNodev Type> * root;BinTreeNodev Type> *Parent ( BinTreeNodev Type> *start, BinTreeNodev Type> *current );int Insert ( BinTreeNodev Type>

20、 *current, const Type& item );int Find ( BinTreeNodev Type > *current, const Type& item ) const;void destroy ( BinTreeNodev Type> *current );void Traverse ( BinTreeNodev Type> *current, ostream& out ) const;public:BinaryTree ( ) : root ( NULL ) BinaryTree ( Type value ) : RefVal

21、ue ( value ), root ( NULL ) BinaryTree ( ) destroy (root); BinTreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) BinTreeNode ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL ) Type& GetData ( ) const return data; BinTreeNodevType>* GetLeft ( ) const return leftChild ;

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

23、nt ( BinTreeNodev Type> *current ) return root = NULL | root = current ? NULL : Parent ( root, current ); BinTreeNodev Type> * LeftChild ( BinTreeNodev Type> *current ) return current != NULL ? current-> leftChild : NULL ; BinTreeNodev Type> * RighttChild ( BinTreeNodev Type> *curr

24、ent ) return current != NULL ? current-> rightChild : NULL ; int Insert ( const Type& item );BinTreeNodev Type> * Find ( const Type& item );BinTreeNodev Type> * GetRoot ( ) const return root; friend istream& operator >> ( istream& in, BinaryTreev Type>& Tree );/

25、輸入二叉樹friend ostream& operator vv ( ostream& out, BinaryTreev Type>& Tree );/輸出二叉樹6-5在結(jié)點個數(shù)為n (n>1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié) 點？高度最大的樹的高度是多少？它有多少個葉結(jié)點？多少個分支結(jié)點？【解答】結(jié)點個數(shù)為n時，高度最小的樹的高度為1，有2層；它有n-1個葉結(jié)點，1個分支結(jié)點；高度最大的樹的高度為n-1，有n層；它有1個葉結(jié)點，n-1個分支結(jié)點。6- 6試分別畫出具有3個結(jié)點的樹和3個結(jié)點的二叉樹的所有不同形態(tài)。【解答】

26、具有3個結(jié)點的樹具有3個結(jié)點的二叉樹6- 7如果一棵樹有 m個度為1的結(jié)點，有n2個度為2的結(jié)點，nm個度為m的結(jié)點，試問有多少個度 為0的結(jié)點？試推導(dǎo)之。【解答】總結(jié)點數(shù)n=no + n1 + n2 + + nm總分支數(shù)e=n-1 = no + n1 + n2 + + nm-1=m* nm + (m-1)* nm-1 + + 2*n2 + n1則有nom|M(iT) n：16- 8試分別找出滿足以下條件的所有二叉樹：(1) 二叉樹的前序序列與中序序列相同；(2) 二叉樹的中序序列與后序序列相同；(3) 二叉樹的前序序列與后序序列相同。【解答】(1) 二叉樹的前序序列與中序序列相同：空樹或缺左

27、子樹的單支樹；(2) 二叉樹的中序序列與后序序列相同：空樹或缺右子樹的單支樹；(3) 二叉樹的前序序列與后序序列相同：空樹或只有根結(jié)點的二叉樹。6-9若用二叉鏈表作為二叉樹的存儲表示，試針對以下問題編寫遞歸算法：(1) 統(tǒng)計二叉樹中葉結(jié)點的個數(shù)。(2) 以二叉樹為參數(shù)，交換每個結(jié)點的左子女和右子女?！窘獯稹?1) 統(tǒng)計二叉樹中葉結(jié)點個數(shù)int BinaryTree vType> : leaf ( BinTreeNode vType> * ptr ) if ( ptr = NULL ) return 0;else if ( ptr-> leftChild = NULL &

28、;& ptr-> rightChild = NULL ) return 1; elsereturn leaf ( ptr-> leftChild ) + leaf ( ptr -> rightChild );(2) 交換每個結(jié)點的左子女和右子女void BinaryTree <Type> : exchange ( BinTreeNode <Type> * ptr ) BinTreeNode <Type> * temp;if ( ptr-> leftChild != NULL | ptr-> rightChild != N

29、ULL )temp = ptr-> leftChild ;ptr-> leftChild = ptr -> rightChild ;ptr-> rightChild = temp ;exchange ( ptr-> leftChild );exchange ( ptr-> rightChild );6-10 一棵高度為h的滿k叉樹有如下性質(zhì)：第h層上的結(jié)點都是葉結(jié)點，其余各層上每個結(jié)點都有 非空子樹，如果按層次自頂向下，同一層自左向右，順序從1開始對全部結(jié)點進行編號，試問：(1) 各層的結(jié)點個數(shù)是多少？(2) 編號為i的結(jié)點的父結(jié)點(若存在)的編號是多少？(

30、3) 編號為i的結(jié)點的第m個孩子結(jié)點(若存在)的編號是多少？(4) 編號為i的結(jié)點有右兄弟的條件是什么？其右兄弟結(jié)點的編號是多少？(5) 若結(jié)點個數(shù)為 n，則高度h是n的什么函數(shù)關(guān)系？【解答】(1) ki ( i = 0, 1，h )(2) .2(3) ( i-1)*k + m + 1(i-1 ) % k豐0或i蘭 匸士二2 * k時有右兄弟，右兄弟為i + 1。二 k 一(5) h = logk (n*(k-1)+1)-1 (n = 0 時 h = -1 ) 6-11試用判定樹的方法給出在中序線索化二叉樹上：【解答】(1)搜索指定結(jié)點的在中序下的后繼。設(shè)指針q指示中序線索化二叉樹中的指定結(jié)點

31、，指針p指示其后繼結(jié)點。q-> rightThread = 1?7q-> rightchild = NULLq無后繼q的后繼為q-> rightchildq的后繼為q的右子樹中 中序下的第一個結(jié)點找q的右子樹中在中序下的第一個結(jié)點的程序為：p = q-> rightChild ;while ( p-> leftThread = 1 ) p = p -> leftChild ;/ p 即為 q 的后繼(2)搜索指定結(jié)點的在前序下的后繼。q-> leftThread = 0q 的后繼為 q-> leftChildq-> rightThread

32、= 0q 的后繼為 q-> rightChildp = q;while ( p-> rightThread = 1 &&p-> rightChild ! = NULL ) p = p-> rightChild ; if ( p-> rightChild =NULL ) q 無后繼;else的后繼為 p-> rightChild 搜索指定結(jié)點的在后序下的后繼。(p = parent (q ) ) = NULL ?q無后繼p-> rightThread =1 | p-> rightChild = q可用一段遍歷程序來實現(xiàn)尋找 找到后立

33、即返回它的地址。q的后繼為pq的后繼為p的右子樹中后序下的第一個結(jié)點p的右子樹中后序下的第一個結(jié)點：即該子樹第一個找到的葉結(jié)點。6-12已知一棵完全二叉樹存放于一個一維數(shù)組Tn中，Tn中存放的是各結(jié)點的值。試設(shè)計一個算法,從T0開始順序讀出各結(jié)點的值，建立該二叉樹的二叉鏈表表示?！窘獯稹?建立二叉樹template vclass Typeistream& operator >> ( istream& in, BinaryTree< Type >& t ) int n;cout << "Please enter the num

34、ber of node : " in >> n ;Type *A = new Typen+1;for ( int i = 0; i < n; i+ ) in >> Ai;t. ConstructTree( T, n, 0, ptr );delete A;return in;/以數(shù)組建立一棵二叉樹template vclass Type>void BinaryTreev Type> : ConstructTree ( Type T , int n, int i, BinTreeNodev Type> * & ptr ) /私有函數(shù)

35、：將用Tn順序存儲的完全二叉樹，以i為根的子樹轉(zhuǎn)換成為用二叉鏈表表示的/以ptr為根的完全二叉樹。利用引用型參數(shù)ptr將形參的值帶回實參。if ( i >= n ) ptr = NULL ;else ptr = new BinTreeNodev Type> ( Ti);建立根結(jié)點ConstructTree ( T, n, 2*i+1, ptr -> leftChild );ConstructTree ( T, n, 2*i+2, ptr -> rightchild );6-13試編寫一個算法，把一個新結(jié)點I作為結(jié)點s的左子女插入到一棵中序線索化二叉樹中,左子女變成I的左

36、子女。【解答】s原來的templatevclass Type>void ThreadTree<Type> : leftinsert ( ThreadNodev Type> *s, ThreadNodev Type> * I ) if ( s != NULL && I != NULL ) I -> leftChild = s-> leftChild : I -> leftThread = s-> leftThread:預(yù)先鏈接I-> rightChild = s : I->rightThread = 1:s->

37、; leftChild = I : s-> leftThread = 0:if ( I-> leftThread = 0 ) ThreadNodevType> * p = I -> leftChild : while ( p-> rightThread = 0 )p = p-> rightChild :p-> rightChild = I :/新插入結(jié)點*l的后繼為*s*l成為*s的左子女*|的左子女存在找*l的左子樹中序下最后一個結(jié)點/該結(jié)點的后繼為*l6- 14寫出向堆中加入數(shù)據(jù)【解答】以最小堆為例：4, 2, 5, 8, 3, 6, 10, 14

38、時，每加入一個數(shù)據(jù)后堆的變化。8245836-16請畫出右圖所示的樹所對應(yīng)的二叉樹。對應(yīng)二叉樹6-17在森林的二叉樹表示中，用llink存儲指向結(jié)點第一個子女的指針，用rlink存儲指向結(jié)點下一個兄ltag 代替 llink，用 rtag弟的指針，用data存儲結(jié)點的值。如果我們采用靜態(tài)二叉鏈表作為森林的存儲表示，同時按森林的先根 次序依次安放森林的所有結(jié)點，則可以在它們的結(jié)點中用只有一個二進位的標(biāo)志代替rlink。并設(shè)定若ltag = 0,則該結(jié)點沒有子女，若ltag = 0,則該結(jié)點有子女；若 rtag = 0 ,則該結(jié)點 沒有下一個兄弟，若rtag - 0,則該結(jié)點有下一個兄弟。試給出這

39、種表示的結(jié)構(gòu)定義，并設(shè)計一個算法,將用這種表示存儲的森林轉(zhuǎn)換成用llink - rlink表示的森林。【解答】0G6對應(yīng)二叉樹1-1-14-16-189-1-1ABCDEFGHIKJ523-1-17-1-110-1-1123llinkdatarlink4578910森林的左子女-右兄弟表示的靜態(tài)二叉鏈表10010101100ABCDEFGHIKJ11100100100012345678910ltag data rtag森林的雙標(biāo)記表示(1)結(jié)構(gòu)定義/左子女-右兄弟鏈表結(jié)點類的定義protected:Type data;int llink, rlink ;template vclass Type

40、classLchRsibNode /結(jié)點數(shù)據(jù)/結(jié)點的左子女、右兄弟指針public:LchRsibNode ( ) : llink(NULL), rlink(NULL) LchRsibNode ( Type x ) : llink(NULL), rlink(NULL), data(x) template vclass Type> classDoublyTagNode /雙標(biāo)記表結(jié)點類的定義protected:Type data;/結(jié)點數(shù)據(jù)int ltag, rtag;結(jié)點的左子女、右兄弟標(biāo)記public:DoublyTagNode ( ) : ltag(0), rtag(O) Doubl

41、yTagNode ( Type x ) : ltag(0), rtag(0), data(x) template vclass Type> classstaticlinkList靜態(tài)鏈表類定義:public LchRsibNode <Type>, public DoublyTagNode <Type>private:LchRsibNodevType> *V ;存儲左子女-右兄弟鏈表的向量DoublyTagNode <Type> *U ;存儲雙標(biāo)記表的向量int MaxSize, CurrentSize;/向量中最大元素個數(shù)和當(dāng)前元素個數(shù)publi

42、c:dstaticlinkList ( int Maxsz ) : MaxSize ( Maxsz ), CurrentSize (0) V = new LchRsibNode < Type> Maxsz;U = new DoublyTagNode < Type> Maxsz;(2)森林的雙標(biāo)記先根次序表示向左子女-右兄弟鏈表先根次序表示的轉(zhuǎn)換 void staticlinkListv Type> : DtagF- LchRsibF ( ) Stackv int> st; int k;for ( int i = 0; i < CurrentSize;i

43、+ ) switch ( Ui.ltag ) case0 : switch ( Ui.rtag ) case 0 : Vi.llink = Vi.rlink =-1;if ( st.IsEmpty ( ) = 0 ) k = st.GetTop ( );st.Pop ( ); Vk.rlink = i + 1 ; break;case 1 : Vi.llink = -1; Vi.rlink = i + 1 ; break;break;case1 : switch ( Ui.rtag ) case 0 : Vi.llink = i + 1;Vi.rlink = -1; break;case 1 : Vi.llink = i + 1;st.Push ( i );6-18二叉樹的雙序遍歷(Double-order traversal)是指：對于二叉樹的每一個結(jié)點來說，先訪問這個結(jié)點, 再按雙序遍歷它的左子樹，然后再一次訪問這個結(jié)點，接下來按雙序遍歷它的右子樹。試寫出執(zhí)行這種 雙序遍歷的算法。【解答】template vclass Typevoid BinaryTreev Type> : Double_order ( BinTreeNodev Type> *current ) if ( current != NULL ) cout &