數(shù)據(jù)結(jié)構(gòu)習(xí)題解析第6章

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

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

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

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

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

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

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

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

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