【正文】 s Comp bool MinHeapElem,Comp:: remove(int pos,Elemamp。 it){ if((pos0)||(pos=n) return false。 swap( Heap, pos, n)。 //要刪除的節(jié)點和最后一個節(jié)點交換 while((pos!=0)amp。amp。(Comp::lt(Heap[pos],Heap[parent(pos)]))) swap(Heap,pos,parent(pos))。 siftdown(pos)。 it=Heap[n]。 return true。 } 刪除某一個節(jié)點 77 霍夫曼樹 一、樹的路徑長度（ PL） PL是指從根到其它各結(jié)點的路徑長度（分支數(shù)）之和 0 1 4 3 2 5 6 (a) PL = 13 7 (b) PL = 15 0 1 4 3 2 5 6 7 78 具有 n個結(jié)點的路徑長度分析 ? 完全二叉樹各結(jié)點的路徑長度分別是數(shù)列 0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4, … 的前 n項之和，具有最小值 ? ??????102 )1(logniiPL ? 若 n個結(jié)點的高度為 h的二叉樹，從根到 h – 1 層都有最多結(jié)點數(shù) 2h – 1 ，其余結(jié)點分布在第 h 層的任意位置上，也具有最小 PL ，這種樹稱為理想平衡二叉樹。 一、樹的路徑長度（ PL） 79 二、霍夫曼樹 樹的帶權(quán)（ Weighted）路徑長度 WPL ? 帶權(quán)的葉子結(jié)點又名外結(jié)點，具有外結(jié)點的樹叫擴充二叉樹 ? 具有 n個外結(jié)點，其中任意結(jié)點的權(quán)值為 Wi，到根的路徑長度為 li ，則該擴充二叉樹的帶權(quán)路徑長度為： ? 具有最小 WPL 的擴充二叉樹叫霍夫曼樹 2 4 5 7 (a) WPL = 36 (b) WPL = 46 2 4 5 7 7 5 2 4 (c) WPL = 35 (霍夫曼樹 ) 80 霍夫曼樹的構(gòu)造方法 將 n個權(quán)值視為具有 n棵擴充二叉樹的森林 F，然后重復(fù)以下步驟，直到 F中只有一棵樹為止： ① 在 F中選根的權(quán)值最小的兩棵作為左右子樹構(gòu)造一棵新的二叉樹，其根的權(quán)為左右子樹根的權(quán)值之和。 ② 在 F中刪除那兩棵樹，并把新的二叉樹加入。 二、霍夫曼樹 2 5 4 (a) 7 ， ， ， (b) 2 5 4 7 ， ， 6 (c) 7 ， 6 2 5 4 11 6 (d) 7 2 5 4 11 18 81 三、 Huffman樹的實現(xiàn) templateclass Elemclass HuffNode{ 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。 }。 抽象基類 82 template class Elem class LeafNode:public HuffNodeElem{ private: FreqPairElem* it。 public: LeafNode(const Elemamp。 val, int freq) {it=new FreqPairElem(val, int freq)。} int weight(){return itweight()。} FreqPairElem* val(){return it。} bool isLeaf(){return true。} virtual HuffNode* left()const{return NULL。} virtual void setLeft(HuffNode*){} virtual HuffNode*right()const{return NULL:} virtual void setRight(HuffNode*){} }； 三、 Huffman樹的實現(xiàn) 葉結(jié)點類 83 template class Elem class IntlNode:public HuffNodeElem{ private: HuffNodeElem* lc。 HuffNodeElem* rc。 int wgt。 public: IntlNode(HuffNodeElem* l,HuffNodeElem* r) {wgt=lweight()+rweight()。 lc=l,rc=r。} int weight(){return wgt。} 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。} }。 三、 Huffman樹的實現(xiàn) 內(nèi)部結(jié)點類 84 template class Elemclass FreqPair{ private: Elem it。 int freq。 public: FreqPair(const Elemamp。e, int f) {it=e。 freq=f。} ~FreqPair(){} int weight(){return freq。} Elemamp。 val(){return it。} }。 三、 Huffman樹的實現(xiàn) 元素 /頻率對的類 85 templateclass Elemclass HuffTree{ private: HuffNodeElem* theroot。 public: HuffTree(Elemamp。val,int freq) {theroot=newLeafNodeElem(val,freq)。} HuffTree(HuffTreeElem* l,HuffTreeElem*r) {theroot=new IntlNodeElem(lroot(), rroot())。} ~HuffTree(){} HuffNodeElem * root(){return theroot。} int weight(){return therootweight()。} }。 三、 Huffman樹的實現(xiàn) Huffman樹類 86 templateclass Elemclass HHCompare{ public: static bool lt(HuffTreeElem* x,HuffTreeElem*y) {return xweight()yweight()。} static bool eq(HuffTreeElem* x,HuffTreeElem*y) {return xweight()==yweight()。} static bool gt(HuffTreeElem* x,HuffTreeElem*y) {return xweight()yweight()。} }。 87 templateclass ElemHuffTreeElem* buildHuff(SSListHuffTreeElem*,HHCompaireElem*fl){ HuffTreeElem* temp1,*temp2,*temp3。 for(flsetStart()。flleftLength()+flrightLength()1。 flsetStart()){ flremove(temp1)。 flremove(temp2)。 temp3=new HuffTreeElem(temp1,temp2)。 flinsert(temp3)。 delete temp1。 delete temp2。 } return temp3。 } 構(gòu)造霍夫曼樹的算法 88 四、霍夫曼編碼 —— 霍夫曼樹應(yīng)用事例 最小冗余編碼問題 ☆ 設(shè)用 0， 1碼來對一串字符信息進行等長編碼： T —— 00， A —— 01， D —— 10， S —— 11 ☆ 對于信息串“ ATTSTATADT ‖所得到的編碼為 01,00,00,11,00,01,00,01,10,00 共 20位編碼 ☆ 字母集合 {T， A， D， S}出現(xiàn)的頻度 W = {5， 3， 1， 1}， 若采用不等長編碼表示 T —— 0， A —— 10， D —— 110， S —— 111 所得到的 編碼是 10,0,0,111,0,10,0,10,110,0 共 17位，這是最小冗 余編碼。 89 霍夫曼樹編碼 ☆ 以字符的頻度為權(quán)構(gòu)造霍夫曼樹 ☆ 左分支表示 0，右分支表示 1 ☆ 從根到各外結(jié)點路徑上經(jīng)由的數(shù)字序列構(gòu)成各字符的編碼 霍夫曼樹編碼的優(yōu)越性 ☆ 是最小冗余碼 ☆ 非前綴碼 ——碼 Ci 不是碼 Cj 的前綴 ☆ 譯碼簡單唯一 ——不斷從根開始沿霍夫曼編碼樹查找。 10001110100101100 譯碼得到的只能是報文串： ATTSTATADT 四、霍夫曼編碼 —— 霍夫曼樹應(yīng)用事例 5 1 3 1 1 1 1 0 0 0 T A D S 2 5 10 90 作業(yè) ? p120： ? p121： 、 、 、 、 ? p122： ? 項目設(shè)計： ? p122： ? p123： The End 91