數(shù)據(jù)結(jié)構習題解析第6章

1、108第6章樹與森林一、復一、復習要點要點本章主要介紹了樹與森林、二叉樹的定義、性質(zhì)、操作和相關算法的實現(xiàn)。特別是二叉樹的遍歷算法，它們與許多以此為基礎的遞歸算法都必須認真學習。因為樹的先根遍歷次序與對應二叉樹表示的前序遍歷次序一致，樹的后根遍歷次序與對應二叉樹的中序遍歷次序一致，因此可以據(jù)此得出樹的遍歷算法。線索化二叉樹是直接利用二叉鏈表的空鏈指針記入前驅(qū)和后繼線索，從而簡化二叉樹的遍歷。堆是一種二叉樹的應用，可以用它作為優(yōu)先級隊列的

2、實現(xiàn)。它的存儲表示是完全二叉樹的順序存儲方式，它的定義不要求堆中的數(shù)據(jù)有序，但要求雙親結(jié)點與子女結(jié)點必須滿足某種關系。本章最后討論霍夫曼樹。這種樹是擴充二叉樹，要求在外結(jié)點上帶有權值，在構造霍夫曼樹時必須注意一個新結(jié)點的左子女上所帶的權值小于右子女上所帶的權值，這不是霍夫曼樹必須這樣，而是實現(xiàn)算法造成這種結(jié)果。此外，作為霍夫曼樹的應用，引入霍夫曼編碼。通常讓霍夫曼樹的左分支代表編碼“0”，右分支代表編碼“1”，得到霍夫曼編碼。這是一種不

3、等長編碼，可以有效地實現(xiàn)數(shù)據(jù)壓縮。本章復習的要點是：1、基本知識點要求理解樹和森林的定義，樹的抽象數(shù)據(jù)類型，二叉樹的定義，二叉樹的性質(zhì)，二叉樹的抽象數(shù)據(jù)類型，二叉樹的數(shù)組表示和鏈表存儲表示。要求掌握二叉樹的遍歷，包括中序遍歷、前序遍歷、后序遍歷方法，要求理解二叉樹的計數(shù)方法及從二叉樹遍歷結(jié)果得到二叉樹的方法。對于線索化二叉樹，要求理解什么是線索，中序線索化二叉樹的結(jié)構特性及尋找某結(jié)點的前驅(qū)和后繼的方法。此外，需要理解堆的定義及其實現(xiàn)的方

4、法，本章只考慮用完全二叉樹的順序存儲來實現(xiàn)。還需要理解堆的建立，插入與刪除過程。要求掌握樹森林與二叉樹的轉(zhuǎn)換，樹的遍歷方法。最后要求掌握霍夫曼樹的實現(xiàn)方法及霍夫曼編碼的概念。2、算法設計?建立二叉樹的遞歸算法。?前序、中序、后序遍歷二叉樹的遞歸算法。?使用棧的前序、中序、后序遍歷的非遞歸算法。?統(tǒng)計二叉樹結(jié)點個數(shù)，二叉樹葉結(jié)點個數(shù)，二叉樹高度的遞歸算法。?自左向右鏈接二叉樹葉結(jié)點的遞歸算法。?判斷兩棵二叉樹相等和交換二叉樹左、右子女指針

5、的遞歸算法。?通過二叉樹的遍歷建立前序線索化二叉樹和中序線索化二叉樹的算法。?中序線索化二叉樹上的中序遍歷算法。?前序線索化二叉樹上的前序遍歷算法。?后序線索化二叉樹上的后序遍歷算法。?利用堆實現(xiàn)優(yōu)先級隊列的操作。?堆的自上向下和自下向上的調(diào)整算法。?堆的插入與刪除算法。?樹的先根、后根、層次遍歷算法（基于樹的二叉樹表示）。110RootDatautype=0根結(jié)點數(shù)據(jù)Childdatautype=1子女結(jié)點數(shù)據(jù)GenTreeNodef

6、irstChildutype=2指向第一個子女的指針public:GenTreeNode(inttpitem):utype(tp)nextSibling(NULL)if(tp==0)RootData=itemelseChildData=item構造函數(shù)：構造廣義表表示的樹的數(shù)據(jù)結(jié)點GenTreeNode(GenTreeNodeson=NULL):utype(2)nextSibling(NULL)firstChild(son)構造函數(shù)：構

7、造廣義表表示的樹的子樹結(jié)點intnodetype()returnutype返回結(jié)點的數(shù)據(jù)類型GetData()returndata返回數(shù)據(jù)結(jié)點的值GenTreeNodeGetFchild()returnfirstChild返回子樹結(jié)點的地址GenTreeNodeGetNsibling()returnnextSibling返回下一個兄弟結(jié)點的地址voidsetInfo(item)data=item將結(jié)點中的值修改為itemvoidsetF

8、child(GenTreeNodeptr)firstChild=ptr將結(jié)點中的子樹指針修改為ptrvoidsetNsinbilg(GenTreeNodeptr)nextSibling=ptrclassGenTree廣義樹類定義private:GenTreeNodefirst根指針retValue建樹時的停止輸入標志GenTreeNodeCopy(GenTreeNodeptr)復制一個ptr指示的子樹voidTraverse(GenLi

9、stNodeptr)對ptr為根的子樹遍歷并輸出voidRemove(GenTreeNodeptr)將以ptr為根的廣義樹結(jié)構釋放friendintEqual(GenTreeNodesGenTreeNodet)比較以s和t為根的樹是否相等public:GenTree()構造函數(shù)GenTree(GenTree復制構造函數(shù)~GenTree()析構函數(shù)friendintoperat==(GenTree判兩棵樹t1與t2是否相等friendis