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

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

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

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

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

5、的遞歸算法。?通過(guò)二叉樹(shù)的遍歷建立前序線索化二叉樹(shù)和中序線索化二叉樹(shù)的算法。?中序線索化二叉樹(shù)上的中序遍歷算法。?前序線索化二叉樹(shù)上的前序遍歷算法。?后序線索化二叉樹(shù)上的后序遍歷算法。?利用堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的操作。?堆的自上向下和自下向上的調(diào)整算法。?堆的插入與刪除算法。?樹(shù)的先根、后根、層次遍歷算法（基于樹(shù)的二叉樹(shù)表示）。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ù)的數(shù)據(jù)結(jié)點(diǎn)GenTreeNode(GenTreeNodeson=NULL):utype(2)nextSibling(NULL)firstChild(son)構(gòu)造函數(shù)：構(gòu)

7、造廣義表表示的樹(shù)的子樹(shù)結(jié)點(diǎn)intnodetype()returnutype返回結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型GetData()returndata返回?cái)?shù)據(jù)結(jié)點(diǎn)的值GenTreeNodeGetFchild()returnfirstChild返回子樹(shù)結(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)中的子樹(shù)指針修改為ptrvoidsetNsinbilg(GenTreeNodeptr)nextSibling=ptrclassGenTree廣義樹(shù)類(lèi)定義private:GenTreeNodefirst根指針retValue建樹(shù)時(shí)的停止輸入標(biāo)志GenTreeNodeCopy(GenTreeNodeptr)復(fù)制一個(gè)ptr指示的子樹(shù)voidTraverse(GenLi

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