2014南大專業(yè)課課件數(shù)據(jù)結(jié)構(gòu)樹與森林

1、6-1 寫出用廣義表表示法表示的樹的類，并給出如下成員函數(shù)的實現(xiàn)：(1) operator ( ) 接收用廣義表表示的樹作為輸入，建立廣義表的表示；(2)構(gòu)造函數(shù) 用另一棵表示為廣義表的樹初始化一棵樹；operator = ( ) 測試用廣義表表示的兩棵樹是否相等；operator ( ) 用廣義表的形式輸出一棵樹；析構(gòu)函數(shù) 清除一棵用廣義表表示的樹。【解答】#include #define maxSubTreeNum 20; class GenTree;/最大(子表)個數(shù)/GenTree 類的前視class GenTreeNode friend class GenTree; private:

2、utype;GenTreeNode * nextSibling;/廣義樹結(jié)點類的/結(jié)點標志：=0, 數(shù)據(jù); =1,/utype=0, 指向第一個;/utype=1 或 2, 指向同一層下一兄弟/聯(lián)合union char RootData; char Childdata; GenTreeNode *public:/utype=0,/utype=1,根結(jié)點數(shù)據(jù)結(jié)點數(shù)據(jù)Child;/utype=2, 指向第一個的指針GenTreeNode (tp, char item ) : utype (tp), nextSibling (NULL) if ( tp = 0 ) RootData = item;

3、else ChildData = item; /構(gòu)造函數(shù)：構(gòu)造廣義表表示的樹的數(shù)據(jù)結(jié)點GenTreeNode ( GenTreeNode *son = NULL ) : utype (2), nextSibling (NULL),Child ( son ) /構(gòu)造函數(shù)：構(gòu)造廣義表表示的樹的 nodetype ( ) return utype; char GetData ( ) return data; GenTreeNode * GetFchild ( ) return結(jié)點/返回結(jié)點的數(shù)據(jù)類型/返回數(shù)據(jù)結(jié)點的值Child; /返回結(jié)點的地址GenTreeNode * GetNsibling (

4、 ) return nextSibling; void setInfo ( char item ) data = item; /返回下一個兄弟結(jié)點的地址/將結(jié)點中的值修改為 item/將結(jié)點中的指針修改為 ptrvoid setFchild ( GenTreeNode * ptr ) Child = ptr; void setNsinbilg ( GenTreeNode * ptr ) nextSibling = ptr; ;class GenTree private:GenTreeNode *char retValue;/廣義樹類定義;/根指針/建樹時的停止輸入標志GenTreeNode *

5、Copy ( GenTreeNode * ptr );void Traverse ( GenListNode * ptr );/一個 ptr 指示的/對 ptr 為根的遍歷并輸出43void Remove ( GenTreeNode *ptr );/將以 ptr 為根的廣義樹結(jié)構(gòu)/比較以 s 和 t 為根的樹是否相等friendpublic:Equal ( GenTreeNode *s, GenTreeNode *t );GenTree ( );GenTree ( GenTree& t );GenTree ( );/構(gòu)造函數(shù)/構(gòu)造函數(shù)/析構(gòu)函數(shù)/判兩棵樹 t1 與 t2 是否相等/輸入/輸出f

6、riendoperator = ( GenTree& t1, GenTree& t2 );friend istream& operator ( istream& in, GenTree& t );friend ostream& operator ( ) 接收用廣義表表示的樹作為輸入，建立廣義表的表示istream& operator ( istream& in, GenTree& t ) /函數(shù), 從輸入流對象 in 接受用廣義表表示的樹，建立廣義表的t.ConstructTree ( in, retValue ); return in;表示 t。void GenTree : Construc

7、tTree ( istream& in, char& value ) /從輸入流對象 in 接受用廣義表表示的非空樹，建立廣義表的Stack st (maxSubTreeNum); GenTreeNode * p, q, r; Type ch;cin value;表示 t。/用于建表時回退地址/廣義樹停止輸入標志數(shù)據(jù)/建立整個樹的根結(jié)點/接著應(yīng)是(, 進棧cin ch;= q = new GenTreeNode ( 0, ch );cin ch; if ( ch = ( ) st.Push ( q ); cin ch;while ( ch != value ) switch ( ch ) /逐

8、個結(jié)點加入case ( :p = new GenTreeNode ( q ); r = st.GetTop( ); st.Pop( );r-nextSibling = p; st.Push( p ); st.Push( q ); break;q-nextSibling = NULL; st.pop( );if ( st.IsEmpty ( ) = 0 ) q = st.GetTop( ); else return 0;break; break; p = q;if ( isupper (ch) ) q = new GenTreeNode ( 0, ch ); else q = new GenTr

9、eeNode ( 1, ch );p-nextSibling = q;/建立, p-Child = q/從棧中退出前一結(jié)點/插/一結(jié)點 r 之后結(jié)點及根結(jié)點進棧case ) :/建成, 封閉鏈, 退到上層/棧不空, 取上層鏈結(jié)點/?？? 無上層鏈, 算法結(jié)束case , :default :/大寫字母, 建根結(jié)點/非大寫字母, 建數(shù)據(jù)結(jié)點/44cin ch;(2)構(gòu)造函數(shù) 用另一棵表示為廣義表的樹初始化一棵樹；GenTree : GenTree ( const GenTree& t ) /共有函數(shù)= Copy ( t);GenTreeNode* GenTree : Copy ( GenTree

10、Node *ptr ) /私有函數(shù)，一個 ptr 指示的用廣義表表示的GenTreeNode *q = NULL; if ( ptr != NULL ) q = new GenTreeNode ( ptr-utype, NULL );switch ( ptr-utype ) case 0 : q-RootData = ptr-RootData; break; case 1 : q-ChildData = ptr-ChildData; break;/根據(jù)結(jié)點類型 utype 傳送值域/傳送根結(jié)點數(shù)據(jù)/傳送結(jié)點數(shù)據(jù)case 2 : q-Child = Copy ( ptr-Child ); bre

11、ak;/遞歸傳送信息q-nextSibling = Copy ( ptr-nextSibling );/同一層下一結(jié)點為頭的表return q;(3) operator = ( ) 測試用廣義表表示的兩棵樹是否相等operator = ( GenTree& t1, GenTree& t2 ) /函數(shù) : 判兩棵樹 t1 與 t2 是否相等, 若兩表完全相等, 函數(shù)返回 1, 否則返回 0。return Equal ( t1, t2);Equal ( GenTreeNode *t1, GenTreeNode *t2 ) /是 GenTreeNode 的x;函數(shù)if ( t1 = NULL & t

12、2 = NULL ) return 1;if ( t1 != NULL & t2 != NULL & t1-utype = t2-utype ) switch ( t1-utype ) case 0 : x = ( t1-RootData = t2-RootData ) ? 1 : 0; break;case 1 : x = ( t1-ChildData = t2-ChildData ) ? 1 : 0;break;/表 t1 與表 t2 都是空樹, 相等/兩都非空且結(jié)點類型相同/比較對應(yīng)數(shù)據(jù)/根數(shù)據(jù)結(jié)點/數(shù)據(jù)結(jié)點case 2 : x = Equal ( t1-Child, t2-Child

13、);/遞歸比較其if ( x ) return Equal ( t1-nextSibling, t2-nextSibling );45/相等, 遞歸比較同一層的下一個結(jié)點; 不等, 不再遞歸比較return 0;(4) operator ( ) 用廣義表的形式輸出一棵樹ostream& operator utype = 0 ) out RootData utype = 1 ) out ChildData;if ( ptr-nextSibling != NULL ) out Child );if ( ptr-nextSibling != NULL ) out nextSibling );/向同一

14、層下一兄弟搜索else out nextSibling;if ( p-utype = 2 ) Remove ( p-Child );ptr-nextSibling = p-nextSibling; delete ( p );/在中刪除結(jié)點 p/466-2 列出右圖所示二叉樹的葉結(jié)點、分支結(jié)點和每個結(jié)點的層次。【解答】二叉樹的葉結(jié)點有、。分支結(jié)點有、。結(jié)點的層次為 0；結(jié)點、的層次為 1；結(jié)點、的層次為 2；結(jié)點、的層次為 3；結(jié)點的層次為 4。6-3(1)(2)使用順序表示和二叉鏈表表示法，分別畫出右圖所示二叉樹的表示。0123456789101112順序表示二叉鏈表表示6-4用嵌套類寫出用鏈

15、表表示的二叉樹的類?！窘獯稹?include template class BinaryTree private:template class Bpublic:reeNode BreeNode *leftChild, *rightChild;Type data;Type RefValue;BreeNode * root;BreeNode *Parent ( BreeNode *start, BreeNode *current );Insert ( BreeNode *current, const Type& item ); Find ( BreeNode *current, const Typ

16、e& item ) const;void destroy ( BreeNode *current );void Traverse ( Bpublic:reeNode *current, ostream& out ) const;BinaryTree ( ) : root ( NULL ) BinaryTree ( Type value ) : RefValue ( value ), root ( NULL ) BinaryTree ( ) destroy (root); BreeNode ( ) : leftChild ( NULL ), rightChild ( NULL ) BreeNod

17、e ( Type item ) : data ( item ), leftChild ( NULL ), rightChild ( NULL ) Type& GetData ( ) const return data; BreeNode* GetLeft ( ) const return leftChild; BreeNode* GetRight ( ) const return rightChild; void SetData ( const Type& item ) data = item; void SetLeft ( BreeNode *L ) leftChild = L; 47voi

18、d SetRight ( BreeNode *R ) RightChild =R; IsEmpty ( ) return root = NULL ? 1 : 0; BreeNode *Parent ( BreeNode *current ) return root = NULL | root = current ? NULL : Parent ( root, current ); BreeNode * LeftChild ( BreeNode *current ) return current != NULL ? current-leftChild : NULL; BreeNode * Rig

19、httChild ( BreeNode *current ) return current != NULL ? current-rightChild : NULL; Insert ( const Type& item );BreeNode * Find ( const Type& item );BreeNode * GetRoot ( ) const return root; friend istream& operator ( istream& in, BinaryTree& Tree ); friend ostream& operator ( ostream& out, BinaryTre

20、e& Tree );/輸入二叉樹/輸出二叉樹6-5 在結(jié)點個數(shù)為n (n1)的各棵樹中，高度最小的樹的高度是多少？它有多少個葉結(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)。6-7 如果一棵樹有n1 個度為 1 的結(jié)點, 有n2 個度為 2 的結(jié)點, , nm 個度為m 的結(jié)點,為 0 的結(jié)點? 試推

21、導(dǎo)之?！窘獯稹靠偨Y(jié)點數(shù) n = n0 + n1 + n2 + + nm總分支數(shù) e = n-1 = n0 + n1 + n2 + + nm-1= m*nm + (m-1)*nm-1 + + 2*n2 + n1試問有多少個度 1m0則有n (i 1)ni i26-8 試分別找出滿足以下條件的所有二叉樹:(1)(2)(3)二叉樹的前序序列與中序序列相同;二叉樹的中序序列與后序序列相同;二叉樹的前序序列與后序序列相同?！窘獯稹?1)(2)(3)二叉樹的前序序列與中序序列相同：空樹或缺樹的單支樹；二叉樹的中序序列與后序序列相同：空樹或缺右的單支樹；二叉樹的前序序列與后序序列相同：空樹或只有根結(jié)點的二叉

22、樹。6-9 若用二叉鏈表作為二叉樹的(1) 統(tǒng)計二叉樹中葉結(jié)點的個數(shù)。表示，試針對以下問題編寫遞歸算法：(2) 以二叉樹為參數(shù)，交換每個結(jié)點的【解答】女和右。48(1) 統(tǒng)計二叉樹中葉結(jié)點個數(shù)BinaryTree : leaf ( BreeNode * 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) 交換每個結(jié)點的女和

23、右void BinaryTree : exchange ( BreeNode * ptr ) BreeNode * 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 一棵高度為 h 的滿 k 叉樹有如下性質(zhì): 第h 層上的結(jié)點都是葉結(jié)點,其余各層上每個結(jié)點都

24、有 k 棵非空, 如果按層次自頂向下, 同一層自左向右, 順序從 1 開始對全部結(jié)點進行各層的結(jié)點個數(shù)是多少?,試問:(1)(2)(3)(4)(5)為 i 的結(jié)點的父結(jié)點(若存在)的是多少?為 i 的結(jié)點的第 m 個孩子結(jié)點(若存在)的是多少?為 i 的結(jié)點有右兄弟的條件是什么? 其右兄弟結(jié)點的若結(jié)點個數(shù)為 n, 則高度 h 是 n 的什么函數(shù)關(guān)系?是多少?【解答】(1)ki( i = 0, 1, , h )i k 2 (2)k(3)( i-1)*k + m + 1(4)( i-1 ) % k 0 或i i k 2 * k時有右兄弟，右兄弟為 i + 1。k(5)h = logk (n*(k-

25、1)+1)-1(n = 0 時 h = -1 )6-11 試用判定樹的方法給出在中序線索化二叉樹上：【解答】(1) 搜索指定結(jié)點的在中序下的后繼。設(shè)指針 q 指示中序線索化二叉樹中的指定結(jié)點，指針 p 指示其后繼結(jié)點。q-rightThread = 1?=q 的后繼為 q 的右中中序下的第一個結(jié)點q-rightChild = NULL ?=q 無后繼q 的后繼為 q-rightChild49找 q 的右中在中序下的第一個結(jié)點的程序為：p = q-rightChild;while ( p-leftThread = 1 ) p = p-leftChild; / p 即為q 的后繼(2) 搜索指定結(jié)

26、點的序下的后繼。q-leftThread = 0 ?=q-rightThread = 0 ?q 的后繼為 q-leftChild=q 的后繼為 q-rightChildp = q;while ( p-rightThread = 1 &p-rightChild != NULL ) p = p-rightChild; if ( p-rightChild =NULL ) q 無后繼;else 的后繼為 p-rightChild(3) 搜索指定結(jié)點的在后序下的后繼。( p = parent (q ) ) = NULL ?=q 無后繼p-rightThread = 1 | p-rightChild =

27、q ?=q 的后繼為 pq 的后繼為 p 的右中后序下的第一個結(jié)點可用一段遍歷程序來實現(xiàn)尋找 p 的右找到后立即返回它的地址。中后序下的第一個結(jié)點：即該第一個找到的葉結(jié)點。6-11 已知一棵完全二叉樹存放于一個一維數(shù)組 Tn中，Tn中存放的是各結(jié)點的值。試設(shè)計一個算法，從 T0開始順序讀出各結(jié)點的值，建立該二叉樹的二叉鏈表表示。6-12 試編寫一個算法，把一個新結(jié)點 l 作為結(jié)點 s 的。女到一棵線索化二叉樹中，s 原來的女變成 l 的左寫出向堆中加入數(shù)據(jù) 4, 2, 5, 8, 3, 6, 10, 14 時，每加入一個數(shù)據(jù)后堆的變化。判斷以下序列是否是最小堆? 如果不是, 將它調(diào)整為最小堆。

28、(1) 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 (2) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 (3) 103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20 (4) 05, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100 請畫出右圖所示的樹所對應(yīng)的二叉樹。在森林的二叉樹表示中，用 llink指向結(jié)點第一個的指針，用rlink指向結(jié)點下一個兄弟的指針，用 data結(jié)點的值。如果采用靜態(tài)二叉鏈表作為森林的表示，同時按森林的先根次序依次安放森

29、林的所有結(jié)點，則可以在它們的結(jié)點中用只有一個二進位的標志 ltag 代替 llink，用 rtag 代替 rlink。并設(shè)定若 ltag = 0，則該結(jié)點沒有，若 ltag 0，則該結(jié)點有；若 rtag= 0，則該結(jié)點沒有下一個兄弟，若 rtag 0，則該結(jié)點有下一個兄弟。試給出這種表示的結(jié)構(gòu)定義，并設(shè)計一個算法，將用這種表示的森林轉(zhuǎn)換成用 llink - rlink 表示的森林。6-17 二叉樹的雙序遍歷(Double-order traversal)是指：對于二叉樹的每一個結(jié)點來說，先這個結(jié)點，再按雙序遍歷它的樹，然后再一次這個結(jié)點，接下來按雙序遍歷它的右。試寫出執(zhí)行這種雙序遍歷的算法。已

30、知一棵二叉樹的前序遍歷的結(jié)果是 ABECDFGHIJ, 中序遍歷的結(jié)果是 EBCDAFHIGJ, 試畫出這棵二叉樹。已知一棵樹的先根次序遍歷的結(jié)果與其對應(yīng)二叉樹表示(長子-兄弟表示)的前序遍歷結(jié)果相同, 樹的后根次序遍歷結(jié)果與其對應(yīng)二叉樹表示的中序遍歷結(jié)果相同。試問利用樹的先根次序遍歷結(jié)果和后根次序遍歷結(jié)果能否唯一確定一50棵樹? 舉例說明。6-20 給定權(quán)值集合 15, 03, 14, 02, 06, 09, 16, 17 , 構(gòu)造相應(yīng)的樹, 并計算它的帶權(quán)外部路徑長度。6-21 假定用于通信的電文僅由 8 個字母c1, c2, c3, c4, c5, c6, c7, c8 組成, 各字母在

31、電文中出現(xiàn)的頻率分別為 5, 25, 3,6, 10, 11, 36, 4。試為這 8 個字母設(shè)計不等長 Huffman 編碼, 并給出該電文的總碼數(shù)。6-22 給定一組權(quán)值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 試構(gòu)造一棵具有最小帶權(quán)外部路徑長度的擴充 4 叉樹,要求該4 叉樹中所有內(nèi)部結(jié)點的度都是4, 所有外部結(jié)點的度都是0。這棵擴充4 叉樹的帶權(quán)外部路徑長度是多少? (提示：如果權(quán)值個數(shù)不足以構(gòu)造擴充 4 叉樹，可補充若干值為零的權(quán)值，再仿照樹的思路構(gòu)造擴充 4 叉樹)6-12 已知一棵完全二叉樹存放于一個一維數(shù)組 Tn中，Tn中存放的

32、是各結(jié)點的值。試設(shè)計一個算法，從 T0開始順序讀出各結(jié)點的值，建立該二叉樹的二叉鏈表表示。【解答】template /建立二叉樹istream& operator ( istream& in, BinaryTree& t ) n;cout n; Type *A = new Typen+1;for (i = 0; i Ai;t. ConstructTree( T, n, 0, ptr ); delete A;return in;/以數(shù)組建立一棵二叉樹template void BinaryTree : ConstructTree ( Type T ,n,i, BreeNode *& ptr )

33、轉(zhuǎn)換成為用二叉鏈表表示的/私有函數(shù) : 將用 Tn順序的完全二叉樹, 以 i 為根的/以 ptr 為根的完全二叉樹。利用if ( i = n ) ptr = NULL; else 型參數(shù) ptr 將形參的值帶回實參。ptr = new BreeNode ( Ti ); ConstructTree ( T, n, 2*i+1, ptr-leftChild );ConstructTree ( T, n, 2*i+2, ptr-rightChild );/建立根結(jié)點6-14 寫出向堆中加入數(shù)據(jù) 4, 2, 5, 8, 3, 6, 10, 14 時，每加入一個數(shù)據(jù)后堆的變化。【解答】以最小堆為例：44

34、222224454545883222235353535518484684610846106-16 請畫出右圖所示的樹所對應(yīng)的二叉樹。【解答】對應(yīng)二叉樹56768786-17 在森林的二叉樹表示中，用 llink指向結(jié)點第一個的指針，用 rlink指向結(jié)點下一個兄弟的指針，用 data結(jié)點的值。如果采用靜態(tài)二叉鏈表作為森林的表示，同時按森林的先根次序依次安放森林的所有結(jié)點，則可以在它們的結(jié)點中用只有一個二進位的標志 ltag 代替 llink，用 rtag代替 rlink。并設(shè)定若 ltag = 0，則該結(jié)點沒有，若 ltag 0，則該結(jié)點有；若 rtag = 0，則該結(jié)點沒有下一個兄弟，若 r

35、tag 0，則該結(jié)點有下一個兄弟。試給出這種表示的結(jié)構(gòu)定義，并設(shè)計一個算法，將用這種表示【解答】的森林轉(zhuǎn)換成用 llink - rlink 表示的森林。AAFHBFCGH對應(yīng)二叉樹BCDGIJDIEKEKJ012345678910llink datarlink012345678910ltag datartag(1) 結(jié)構(gòu)定義template class LchRsibNode protected:Type data;llink, rlink; public:LchRsibNode ( ) : llink(NULL), rlink(NULL) /女-右兄弟鏈表結(jié)點類的定義/結(jié)點數(shù)據(jù)/結(jié)點的女、右

36、兄弟指針LchRsibNode ( Type x ) : llink(NULL), rlink(NULL), data(x) 52森林的雙標記表示10010101100ABCDEFGHIKJ11100100100森林的女-右兄弟表示的靜態(tài)二叉鏈表1-1-14-16-189-1-1ABCDEFGHIKJ523-1-17-1-110-1-1template class DoublyTagNode protected:Type data;ltag, rtag; public:DoublyTagNode ( ) : ltag(0), rtag(0) /雙標記表結(jié)點類的定義/結(jié)點數(shù)據(jù)/結(jié)點的女、右兄弟標

37、記DoublyTagNode ( Type x ) : ltag(0), rtag(0), data(x) template class s iclinkList/靜態(tài)鏈表類定義: public LchRsibNode, public DoublyTagNode private:LchRsibNode *V; DoublyTagNode *U;MaxSize, CurrentSize;public:/女-右兄弟鏈表的向量雙標記表的向量/向量中最大元素個數(shù)和當前元素個數(shù)ds iclinkList (Maxsz ) : MaxSize ( Maxsz ), CurrentSize (0) V =

38、new LchRsibNode Maxsz;U = new DoublyTagNode Maxsz;(2) 森林的雙標記先根次序表示向女-右兄弟鏈表先根次序表示的轉(zhuǎn)換void s iclinkList : DtagF-LchRsibF ( ) Stack st;k;for (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 (

39、 ); break;case 1 : Vi.llink = -1; Vi rlink = i + 1;break;case 1 : switch ( Ui rtag ) case 0 : Vi.llink = i + 1; Vi rlink = -1; case 1 : Vi.llink = i + 1; st.Push ( i );Vk rlink = i + 1; break;break;536-18 二叉樹的雙序遍歷(Double-order traversal)是指：對于二叉樹的每一個結(jié)點來說，先這個結(jié)點，再按雙序遍歷它的雙序遍歷的算法。【解答】樹，然后再一次這個結(jié)點，接下來按雙序遍歷它的右。試寫出執(zhí)行這種template void BinaryTree : Double_order ( BreeNode *current ) if ( current != NULL ) cout data leftChild ); cout data rightChild );6-19 已知一棵二叉樹的前序遍歷的結(jié)果是 ABECDFGHIJ, 中序遍歷的結(jié)果是 EBCDAFHIGJ, 試畫出這棵二叉樹?！窘獯稹慨斍靶蛐蛄袨锳BECDFGHIJ，中序