數(shù)據(jù)結(jié)構(gòu)C++ppt課件

1、數(shù)據(jù)結(jié)構(gòu)第5章 二叉樹(shù),肖 正 信息與智能系統(tǒng)系 ,1,2,5.1 定義及主要特性,邏輯定義 遞歸定義: 二叉樹(shù)由結(jié)點(diǎn)的有限集合組成，這個(gè)集合或者為空，或者由一個(gè)根結(jié)點(diǎn)及兩棵不相交的，分別稱作這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。 特點(diǎn)：每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)。 二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒。,3,基本形態(tài),4,二叉樹(shù)的相關(guān)術(shù)語(yǔ),從一個(gè)結(jié)點(diǎn)到它的兩個(gè)子結(jié)點(diǎn)都有邊(edge)相連，這個(gè)結(jié)點(diǎn)稱為它的子結(jié)點(diǎn)的父結(jié)點(diǎn)(parent)。 如果一棵樹(shù)的一串結(jié)點(diǎn)n1, n2, , nk有如下關(guān)系: 結(jié)點(diǎn)ni是ni+1的父結(jié)點(diǎn)(1ik), 就把n1, n2, , nk稱為一條由n1至nk的路徑

2、(path)。這條路經(jīng)的長(zhǎng)度(length)是k-1(因?yàn)閗個(gè)結(jié)點(diǎn)是用k-1條邊連接起來(lái)的)。如果有一條路徑從結(jié)點(diǎn)R至結(jié)點(diǎn)M, 那么R就稱為M的祖先(ancestor), 而M稱為R的子孫(descendant)。,5,二叉樹(shù)的相關(guān)術(shù)語(yǔ),結(jié)點(diǎn)M的深度(depth)就是從根結(jié)點(diǎn)到M的路徑的長(zhǎng)度。樹(shù)的高度(height)等于最深的結(jié)點(diǎn)的深度+1。任何深度為d的結(jié)點(diǎn)的層數(shù)(level)都為d。根結(jié)點(diǎn)深度為0，層數(shù)也為0。 沒(méi)有非空子樹(shù)的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)(leaf)或終端結(jié)點(diǎn)。至少有一個(gè)非空子樹(shù)的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)或內(nèi)部結(jié)點(diǎn)(internal node)。,6,二叉樹(shù)的相關(guān)術(shù)語(yǔ),滿二叉樹(shù) 如果一顆二叉樹(shù)的

3、任何結(jié)點(diǎn)，或者是樹(shù)葉，或者恰有兩個(gè)非空子女的分支結(jié)點(diǎn)，則此二叉樹(shù)稱為滿二叉樹(shù)。,(a)滿二叉樹(shù)(非完全二叉樹(shù)) (b)完全二叉樹(shù)(非滿二叉樹(shù)),7,二叉樹(shù)的相關(guān)術(shù)語(yǔ),完全二叉樹(shù) 若一顆二叉樹(shù)最多只有最下面的兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱此二叉樹(shù)為完全二叉樹(shù)。 自根結(jié)點(diǎn)起每一層從左至右地填充。一棵高度為d的完全二叉除了d-1層外，每一層都是滿的。底層葉結(jié)點(diǎn)集中在左邊的若干位置上。,8,完全二叉樹(shù),9,二叉樹(shù)性質(zhì),1. 滿二叉樹(shù)定理：非空滿二叉樹(shù)樹(shù)葉數(shù)等于其分支結(jié)點(diǎn)數(shù)加1。 證明：設(shè)二叉樹(shù)結(jié)點(diǎn)數(shù)為n，葉結(jié)點(diǎn)數(shù)為m，分支結(jié)點(diǎn)數(shù)為b。 有n（總結(jié)點(diǎn)數(shù)=

4、 m（葉)+b（分支）(1) 每個(gè)分支，恰有兩個(gè)子結(jié)點(diǎn)（滿），故有2*b條邊一顆二叉樹(shù)，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都恰有一條邊聯(lián)接父結(jié)點(diǎn)，故共有n-1條邊。即n-1=2*b(2) 由(1)(2)得n-1=m+b-1=2*b， 得出m(葉) =b（分支）+ 1,10,二叉樹(shù)的性質(zhì),2、滿二叉樹(shù)定理的推論: 一棵非空二叉樹(shù)空子樹(shù)的數(shù)目等于其結(jié)點(diǎn)數(shù)目加1。 證明1：設(shè)二叉樹(shù)T，將其所有空子樹(shù)換成葉結(jié)點(diǎn)，把新的二叉樹(shù)記為T。所有原來(lái)樹(shù)T的結(jié)點(diǎn)現(xiàn)在是樹(shù)T的分支結(jié)點(diǎn)。 根據(jù)滿二叉樹(shù)定理，新添加的葉結(jié)點(diǎn)數(shù)目等于樹(shù)T的結(jié)點(diǎn)數(shù)目加1， 而每個(gè)新添加的葉結(jié)點(diǎn)對(duì)應(yīng)樹(shù)T的一棵空子樹(shù)，因此樹(shù)T中空子樹(shù)的數(shù)目等于樹(shù)T中結(jié)點(diǎn)數(shù)目

5、加1。,11,二叉樹(shù)的性質(zhì),證明2：根據(jù)定義，二叉樹(shù)T中每個(gè)結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)指針（空或非空）。 因此一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)有2n個(gè)子結(jié)點(diǎn)指針。 除根結(jié)點(diǎn)外，共有n-1個(gè)結(jié)點(diǎn)，它們都是由其父結(jié)點(diǎn)中相應(yīng)指針指引而來(lái)的，換句話說(shuō)就有n-1個(gè)非空子結(jié)點(diǎn)指針。 既然子結(jié)點(diǎn)指針數(shù)為2n，則其中有n+1個(gè)為空(指針)。,12,二叉樹(shù)的性質(zhì),3. 任何一顆二叉樹(shù)，度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多一個(gè)。 證明：設(shè)有n個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0、1、2的結(jié)點(diǎn)數(shù)分別為=n0，n1，n2， n=n0 +n1 +n2 (公式1) 設(shè)邊數(shù)為e。因?yàn)槌酝?，每個(gè)結(jié)點(diǎn)都有一條邊進(jìn)入，故n=e+1。 由于這些邊是有度為1和2的結(jié)點(diǎn)

6、射出的，因此e=n1+ 2*n2，于是n=e+1= n1 +2*n2 +1（公式2） 因此由公式（1）（2）得 n0+n1+n2=n1+2*n2+1 即n0 =n2 +1,13,二叉樹(shù)的性質(zhì),4.二叉樹(shù)的第i層（根為第0層）最多有2i個(gè)結(jié)點(diǎn) 5.高度為k(深度為k-1。只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)的高度為1，深度為0)的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn) 6. 有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度為log2n+1(深度為log2n ),14,二叉樹(shù)的抽象數(shù)據(jù)類型,template class BinNode public: virtual BinNode* left() const=0; virtual BinNo

7、de* right() const=0; virtual Elem,15,5.2 周游二叉樹(shù),周游：系統(tǒng)地訪問(wèn)數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)都正好被訪問(wèn)到一次。 方法： 前序周游(preorder traversal)：訪問(wèn)根結(jié)點(diǎn)；前序周游左子樹(shù);前序周游右子樹(shù)。 中序周游(inorder traversal)：中序周游左子樹(shù);訪問(wèn)根結(jié)點(diǎn);中序周游右子樹(shù)。 后序周游(postorder traversal)：后序周游左子樹(shù);后序周游右子樹(shù);訪問(wèn)根結(jié)點(diǎn)。,16,先序遍歷,D L R,先序遍歷序列：A B D C,17,中序遍歷,L D R,中序遍歷序列：B D A C,18,后序遍歷,L R D,后

8、序遍歷序列： D B C A,19,舉例,中序遍歷：,后序遍歷：,層次遍歷：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,先序遍歷：,20,前序遍歷算法,template void preorder(BinNode* subroot) if (subroot = NULL) return; visit(subroot); preorder(subroot-leftchild(); preorder(subroot-rightchild(); ,21,遍歷算法應(yīng)用,

9、計(jì)算二叉樹(shù)的結(jié)點(diǎn)數(shù)： template int count(BinNode* subroot) if (subroot = NULL) return 0; / visit(subroot); return 1+count(subroot-left()+ count(subroot-right(); ,22,5.3 二叉樹(shù)的實(shí)現(xiàn),5.3.1 使用指針實(shí)現(xiàn)二叉樹(shù) 二叉鏈表(最常用) class BinNodePtr private: Elem it; BinNodePtr* lc; BinNodePtr* rc; ; 好處：運(yùn)算方便;問(wèn)題：空指針太多,23,二叉樹(shù)的存儲(chǔ),帶父指針的三重鏈表 在某些

10、經(jīng)常要回溯到父結(jié)點(diǎn)的應(yīng)用中很有效。 class BinNodePtr private: Elem it; BinNodePtr* lc; BinNodePtr* rc; BinNodePtr* father; ;,24,二叉樹(shù)存儲(chǔ)（區(qū)別葉和分支）,葉結(jié)點(diǎn)和分支結(jié)點(diǎn)的分別實(shí)現(xiàn) 當(dāng)葉結(jié)點(diǎn)和分支結(jié)點(diǎn)差別較大，或出于應(yīng)用要求而需要區(qū)分葉結(jié)點(diǎn)和分支結(jié)點(diǎn)時(shí) (a) 聯(lián)合 (b) 類繼承和虛函數(shù),25,表達(dá)式樹(shù)：聯(lián)合實(shí)現(xiàn)方法,class VarBinNode public: Nodetype mytype; union struct VarBinNode* left; VarBinNode* right;

11、Operator opx; intl; Operand var; ; ,26,用不同的類實(shí)現(xiàn)分支和葉,class VarBinNode public: virtual bool isLeaf isLeaf() = 0; ; class LeafNode :public VarBinNode private: Operand var; public: LeafNode(const Operand,27,不同類實(shí)現(xiàn)的分支結(jié)點(diǎn),Class IntlNode:public VarBinNode private: VarBinNode* left; VarBinNode* right; Operator

12、 opx; public: IntlNode (const Operator,28,5.3.2 結(jié)構(gòu)性空間開(kāi)銷分析,根據(jù)滿二叉樹(shù)定理：一半的指針是空的 如果只有葉結(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，分支結(jié)點(diǎn)為內(nèi)部結(jié)構(gòu)結(jié)點(diǎn)（如Huffman樹(shù)），則取決于二叉樹(shù)是否滿（越滿存儲(chǔ)效率越高） 對(duì)于簡(jiǎn)單的每個(gè)結(jié)點(diǎn)存兩個(gè)指針、一個(gè)數(shù)據(jù)域 總空間(2p +d)n 結(jié)構(gòu)性： 2pn 如果p=d，則2p/(2p +d) =2/3,29,結(jié)構(gòu)性空間開(kāi)銷分析,去掉滿二叉樹(shù)葉結(jié)點(diǎn)中的指針 則結(jié)構(gòu)性開(kāi)銷為1/2（假設(shè)p=d） 如果只在葉結(jié)點(diǎn)存數(shù)據(jù)，則結(jié)構(gòu)性開(kāi)銷為 2pn/(2pn +d(n+1) 2/3（假設(shè)p=d） 注意：區(qū)分葉結(jié)點(diǎn)和分支

13、結(jié)點(diǎn)又需要額外的算法時(shí)間。,30,5.3.3 使用數(shù)組實(shí)現(xiàn)完全二叉樹(shù),完全二叉樹(shù)的順序存儲(chǔ) ABCDEFGHIJKL 按照二叉樹(shù)的層次周游次序存儲(chǔ)在一個(gè)數(shù)組中 簡(jiǎn)單，省空間,31,順序存儲(chǔ),非完全二叉樹(shù)在置空值而轉(zhuǎn)換為完全二叉樹(shù)存儲(chǔ) CEDJFX/K/G/I/L,32,完全二叉樹(shù)的下標(biāo)對(duì)應(yīng)關(guān)系,0,0,0,0,0,0,0,0,0,0,0,0,33,完全二叉樹(shù)的下標(biāo)公式,公式中r表示結(jié)點(diǎn)的索引， n表示二叉樹(shù)結(jié)點(diǎn)總數(shù)。 Parent(r) =(r-1) /2，當(dāng)0rn時(shí)。 Leftchild(r) =2r +1，當(dāng)2r+1n時(shí)。 Rightchild(r) = 2r+ 2 ，當(dāng)2r+2 n 時(shí)。

14、 Leftsibling(r) =r-1，當(dāng)r為偶數(shù)且0=r=n-1。 Rightsibling(r) =r+1，當(dāng)r為奇數(shù)且r+1n。,34,5.4 二叉查找樹(shù),定義：二叉檢索樹(shù)或者為空, 或者是滿足下列條件的非空二叉樹(shù): (1若它的左子樹(shù)非空, 則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值; (2)它的右子樹(shù)非空, 則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于根結(jié)點(diǎn)的值; (3)左右子樹(shù)本身又各是一棵二叉檢索樹(shù)。 性質(zhì): 按照中序周游將各結(jié)點(diǎn)打印出來(lái)，將得到按照由小到大的排列。,35,BST圖示,36,檢索,二叉檢索樹(shù)的效率就在于只需檢索二個(gè)子樹(shù)之一。從根結(jié)點(diǎn)開(kāi)始，在二叉檢索樹(shù)中檢索值K。 如果根結(jié)點(diǎn)儲(chǔ)存

15、的值為K，則檢索結(jié)束。 如果K小于根結(jié)點(diǎn)的值，則只需檢索左子樹(shù) 如果K大于根結(jié)點(diǎn)的值,就只檢索右子樹(shù) 這個(gè)過(guò)程一直持續(xù)到K被找到或者我們遇上了一個(gè)樹(shù)葉。 如果遇上樹(shù)葉仍沒(méi)有發(fā)現(xiàn)K，那么K就不在該二叉檢索樹(shù)中。,37,二叉檢索樹(shù)類的定義,class BST private: BinNode* root; int nodecount; void clearhelp(BinNode * ); BinNode* inserthelp(BinNode *,const Elem,38,二叉檢索樹(shù)類的定義,public: BST() root = NULL;nodecount=0; BST() clearh

16、elp(root); void clear() clearhelp(root);root=NULL; nodecount=0; void insert(const Elem,39,檢索,template bool BST: findhelp(BinNode* subroot, const Key ,40,插入,template BinNode* BST: inserthelp(BinNode* subroot, const Elem ,41,BST插入圖示,42,刪除,從二叉檢索樹(shù)中刪除一個(gè)任意的結(jié)點(diǎn)R，首先必須找到R，接著將它從二叉樹(shù)中刪除掉。 如果R是一個(gè)葉結(jié)點(diǎn)(沒(méi)有兒子), 那么只要將R

17、的父結(jié)點(diǎn)指向它的指針改為NULL就可以了。 如果R是一個(gè)分支結(jié)點(diǎn), 我們就不能簡(jiǎn)單地刪除這個(gè)結(jié)點(diǎn), 因?yàn)檫@樣做會(huì)破壞樹(shù)的連通性。 如果R只有一個(gè)兒子, 就將R的父結(jié)點(diǎn)指向它的指針改為指向R的子結(jié)點(diǎn)就可以了。 如果R有兩個(gè)兒子, 為了保持二叉檢索樹(shù)的性質(zhì), 可以用R的中序后繼結(jié)點(diǎn)來(lái)代替它。,43,刪除子樹(shù)中最小值圖示,template BinNode* BST: deletemin(BinNode* subroot, BinNode* ,44,刪除右子樹(shù)中最小值結(jié)點(diǎn),45,BST Remove（1）,template BinNode* BST: removehelp(BinNode* subro

18、ot, const Key,46,BST Remove（2）,else / Found it: remove it BinNode* temp; t = subroot; if (subroot-left() = NULL) subroot = subroot-right(); else if (subroot-right() = NULL) subroot = subroot-left(); else / Both children are non-empty subroot-setRight( deletemin(subroot-right(), temp); Elem te = subr

19、oot-val(); subroot-setVal(temp-val(); temp-setVal(te); t = temp; return subroot; ,47,5.5 堆與優(yōu)先隊(duì)列,定義: 對(duì)于一個(gè)關(guān)鍵碼序列 K0, K1, , Kn-1，如果滿足KiK2i+1, KiK2i+2, (i=0,1,n/2-1),則稱其為堆，而且這是最大值堆。 性質(zhì): 是任意一個(gè)結(jié)點(diǎn)的值都大于或者等于其任意一個(gè)子結(jié)點(diǎn)存儲(chǔ)的值。由于根結(jié)點(diǎn)包含大于或等于其子結(jié)點(diǎn)的值，而其子結(jié)點(diǎn)又依次大于或等于各自子結(jié)點(diǎn)的值，所以根結(jié)點(diǎn)存儲(chǔ)著該樹(shù)所有結(jié)點(diǎn)中的最大值。,48,最小值堆,最小值堆(min-heap)的性質(zhì)是每一個(gè)

20、結(jié)點(diǎn)存儲(chǔ)的值都小于或等于其子結(jié)點(diǎn)存儲(chǔ)的值。由于根結(jié)點(diǎn)包含小于或等于其子結(jié)點(diǎn)的值，而其子結(jié)點(diǎn)又依次小于或等于各自子結(jié)點(diǎn)的值，所以根結(jié)點(diǎn)存儲(chǔ)了該樹(shù)所有結(jié)點(diǎn)的最小值。,49,最大值堆的實(shí)現(xiàn),template class maxheap private: Elem* Heap; / Pointer to the heap array int size; / Maximum size of the heap int n; / Number of elems now in heap void siftdown(int); / Put element in place public: maxheap(Ele

21、m* h, int num, int max); int heapsize() const; bool isLeaf(int pos) const; int leftchild(int pos) const; int rightchild(int pos) const; int parent(int pos) const; bool insert(const Elem,50,建堆圖示,51,堆的形成,不必將值一個(gè)個(gè)地插入堆中，通過(guò)交換形成堆。 假設(shè)根的左、右子樹(shù)都已是堆，并且根的元素名為R。能這種情況下，有兩種可能： (1) R的值大于或等于其兩個(gè)子女，此時(shí)堆已完成 (2) R的值小于其某一個(gè)

22、或全部?jī)蓚€(gè)子女的值，此時(shí)R應(yīng)與兩個(gè)子女中值較大的一個(gè)交換，結(jié)果得到一個(gè)堆，除非R仍然小于其新子女的一個(gè)或全部的兩個(gè)。這種情況下，我們只需簡(jiǎn)單地繼續(xù)這種將R“拉下來(lái)來(lái)”的過(guò)程，直至到達(dá)某一個(gè)層使它大于它的子女，或者它成了葉結(jié)點(diǎn)。,52,Shiftdown操作,53,舉例,54,Shiftdown,template void maxheap:siftdown(int pos) while (!isLeaf(pos) int j = leftchild(pos); int rc = rightchild(pos); if (rcn) ,55,Remove Max Value,template boo

23、l maxheap: removemax(Elem ,56,建堆操作的效率,57,5.6 Huffman編碼樹(shù),1.固定長(zhǎng)度編碼 設(shè)所有代碼都等長(zhǎng)，則表示n個(gè)不同的代碼需要log2n位稱為固定長(zhǎng)度編碼(a fixed-length coding scheme)。 ASCII 碼就是一種固定長(zhǎng)度編碼。 如果每個(gè)字符的使用頻率相等的話，固定長(zhǎng)度編碼是空間效率最高的方法。 2.數(shù)據(jù)壓縮和不等長(zhǎng)編碼 頻率不等的字符,58,數(shù)據(jù)壓縮和不等長(zhǎng)編碼,可以利用字母的出現(xiàn)頻率來(lái)編碼，使得經(jīng)常出現(xiàn)的字母的編碼較短，反之不常出現(xiàn)的字母編碼較長(zhǎng)。 數(shù)據(jù)壓縮既能節(jié)省磁盤空間，又能提高運(yùn)算速度。（外存時(shí)空權(quán)衡的規(guī)則） 不

24、等長(zhǎng)編碼是今天廣泛使用的文件壓縮技術(shù)的核心 Huffman 編碼是最簡(jiǎn)單的文件壓縮技術(shù)，它給出了這種編碼方法的思想。,59,5.6.1 建立Huffman編碼樹(shù),對(duì)于n個(gè)字符K0，K1，Kn-1，們它的使用頻率分別為w0，w1，wn-1，請(qǐng)給出它們的編碼，使得總編碼效率最高。 定義一個(gè)樹(shù)葉的帶權(quán)路徑長(zhǎng)度(Weighted path length)為權(quán)乘以它的路徑長(zhǎng)度(即樹(shù)葉的深度）。 這個(gè)問(wèn)題其實(shí)就是要求給出一個(gè)具有n個(gè)外部結(jié)點(diǎn)的擴(kuò)充二叉樹(shù) 該二叉樹(shù)每個(gè)外部結(jié)點(diǎn)Ki有一個(gè)wi與之對(duì)應(yīng)，作為該外部結(jié)點(diǎn)的權(quán),這個(gè)擴(kuò)充二叉樹(shù)的葉結(jié)點(diǎn)帶權(quán)外部路徑長(zhǎng)度總和 最?。ㄗ⒁獠还軆?nèi)部結(jié)點(diǎn)，也不用有序）。權(quán)越大的

25、葉結(jié)點(diǎn)離根越近；如果某個(gè)葉的權(quán)較小，可能就會(huì)離根較遠(yuǎn)。,60,建立Huffman樹(shù)的過(guò)程,首先，按照“權(quán)”（例如頻率）將字母排為一列。 接著，拿走頭兩個(gè)字母（“權(quán)”最小的兩個(gè)字母），再將它們標(biāo)記為Huffman樹(shù)的樹(shù)葉，將這兩個(gè)樹(shù)葉標(biāo)為一個(gè)分支結(jié)點(diǎn)的兩個(gè)子女，而該結(jié)點(diǎn)的權(quán)即為兩樹(shù)葉的權(quán)之和。將所得“權(quán)”放回序列中適當(dāng)位置，使“權(quán)”的順序保持。 重復(fù)上述步驟直至序列中只剩一個(gè)元素，則Huffman樹(shù)建立完畢。,61,Huffman建樹(shù)圖示,62,Huffman建樹(shù)圖示,63,Huffman建樹(shù)圖示,64,Huffman樹(shù)結(jié)點(diǎn)的實(shí)現(xiàn),template class HuffNode / Node a

26、bstract base class public: virtual int weight() = 0; virtual bool isLeaf() = 0; virtual HuffNode* left() const = 0; virtual void setLeft(HuffNode*) = 0; virtual HuffNode* right() const = 0; virtual void setRight(HuffNode*) = 0; ;,65,Huffman樹(shù)葉節(jié)點(diǎn)的實(shí)現(xiàn),template / Leaf node subclass class LeafNode : publi

27、c HuffNode private: FreqPair* it; / Frequency pair public: LeafNode(const Elem,66,Huffman樹(shù)分支結(jié)點(diǎn)的實(shí)現(xiàn),template / Internal node subclass class IntlNode : public HuffNode private: HuffNode* lc; / Left child HuffNode* rc; / Right child int wgt; / Subtree weight public: IntlNode(HuffNode* l, HuffNode* r) wg

28、t = l-weight() + r-weight(); lc = l; rc = r; int weight() return wgt; / Return frequency bool isLeaf() return false; HuffNode* left() const return lc; void setLeft(HuffNode*b) lc=(HuffNode*)b; HuffNode* right() const return rc; void setRight(HuffNode*b)rc=(HuffNode*)b; ;,67,元素/頻率對(duì)的類聲明,template class

29、 FreqPair / An element/frequency pair private: Elem it; / An element of some sort int freq; / Frequency for the element public: FreqPair(const Elem,68,Huffman樹(shù)的類聲明,template class HuffTree private: HuffNode* theRoot; public: HuffTree(Elem,69,Huffman樹(shù)的類聲明,/ Compare two Huffman trees by total weight te

30、mplate class HHCompare public: static bool lt(HuffTree* x, HuffTree* y) return x-weight() weight(); static bool eq(HuffTree* x, HuffTree* y) return x-weight() = y-weight(); static bool gt(HuffTree* x, HuffTree* y) return x-weight() y-weight(); ;,70,Huffman樹(shù)構(gòu)建函數(shù),/ Build a Huffman tree from list fl template HuffTree* buildHuff(SLList*, HHCompare * fl) HuffTree *temp1, *temp