算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）（第2版） 課件 第7章-樹的應(yīng)用

DataStructureandAlgorithmdesign|analyze|experiment|implement數(shù)據(jù)結(jié)構(gòu)與算法第七章樹的應(yīng)用*7.1表達(dá)式樹7.2哈夫曼樹和哈夫曼編碼7.3堆和優(yōu)先級(jí)隊(duì)列*7.4并查集*7.5算法拓展*7.6你怎么看？目錄CONTENTS二叉樹的周游算法與表達(dá)式的“前綴”和“后綴”表示法之間有著密切的聯(lián)系。例如圖是表達(dá)式A+B×(C+D)的二叉樹表示。按照前序方式周游，運(yùn)算符出現(xiàn)在前面，參與運(yùn)算的對(duì)象緊跟在其后，這樣就形成了前綴表達(dá)式（波蘭式）+A×B+CD按照中序方式周游，得到的結(jié)果是去掉括號(hào)的中綴表達(dá)式：A+B×C+D下面是后序方式周游的結(jié)果，得到的是后綴表達(dá)式（逆波蘭式）：ABCD+×+圖表達(dá)式樹表達(dá)式樹*7.1表達(dá)式樹7.2哈夫曼樹和哈夫曼編碼7.2.1哈夫曼樹7.2.2哈夫曼編碼7.3堆和優(yōu)先級(jí)隊(duì)列*7.4并查集*7.5算法拓展*7.6

你怎么看？目錄CONTENTS概念和術(shù)語(1)路徑（Path）：從一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支序列，構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。(2)路徑長度（PathLength）：路徑上的分枝數(shù)目稱作路徑長度。如根結(jié)點(diǎn)到第L層結(jié)點(diǎn)路徑長度為L-1。完全二叉樹是路徑長度最短的二叉樹。(3)結(jié)點(diǎn)的權(quán)（Weight）：在實(shí)際應(yīng)用中，人們常常給樹的每個(gè)結(jié)點(diǎn)賦予一個(gè)具有某種實(shí)際意義的數(shù)，如單價(jià)、出現(xiàn)頻度等，稱該數(shù)為這個(gè)結(jié)點(diǎn)的權(quán)。

概念和術(shù)語哈夫曼樹例如，給定四個(gè)葉結(jié)點(diǎn)a，b，c，d，其權(quán)值分別是2、3、6、9，可以構(gòu)造出形態(tài)不同的多棵二叉樹。a)WPL=2

2+3

2+6

2+9

2=40b)WPL=2

1+3

2+6

3+9

3=53c)WPL=9

1+6

2+3

3+2

3=36d)WPL=9

1+6

2+2

3+3

3=36哈夫曼樹的性質(zhì)2.哈夫曼樹的特點(diǎn)(1)n個(gè)葉結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)；(2)權(quán)值越大的葉結(jié)點(diǎn)離根結(jié)點(diǎn)越近，權(quán)值越小的葉子結(jié)點(diǎn)離根結(jié)點(diǎn)越遠(yuǎn)。(3)哈夫曼樹是正則二叉樹，只有度為0（葉子）和度為2（分支）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn)。(4)哈夫曼樹的任意非葉節(jié)點(diǎn)的左右子樹交換后仍是哈夫曼樹，哈夫曼樹的樹形不唯一，但WPL是相同的。哈夫曼算法(1)根據(jù)給定的權(quán)值集合{w1

，w2

，…，wn}，構(gòu)造含有n棵二叉樹的集合（森林）F={T1

，T2

，…，Tn}，其中每一棵二叉樹Ti只有根結(jié)點(diǎn)，其權(quán)值為wi，左右子樹為空；(2)在集合F中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一棵新的二叉樹，這棵新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹根結(jié)點(diǎn)的權(quán)值之和；(3)從集合F中刪除作為左、右子樹的兩棵二叉樹，同時(shí)把新二叉樹加入到F中；(4)重復(fù)上述兩步，直到集合F中只含有一棵二叉樹為止，這棵二叉樹即為哈夫曼樹。哈夫曼樹的構(gòu)造舉例初始狀態(tài)集合中有4棵樹，權(quán)值分別為2、3、6、9自測(cè)w={5,29,7,8,14,23,3,11}51429782331114297823115388715142923538111153819142923871511538192923148715292914871529115381923421153819234229148715295811538192342291487152958100哈夫曼樹的形態(tài)是不唯一的對(duì)n（n≥2）個(gè)權(quán)值均不相同的字符構(gòu)造哈夫曼樹。下列關(guān)于該哈夫曼樹的敘述中，錯(cuò)誤的是（）該樹一定是一棵完全二叉樹樹中一定沒有度為1的結(jié)點(diǎn)樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值A(chǔ)BCD提交【2010年統(tǒng)考408】單選題1分下列選項(xiàng)給出的是從根分別到達(dá)兩個(gè)葉節(jié)點(diǎn)路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是24，10，5和24，10，724，10，5和24，12，724，10，10和24，14，1124，10，5和24，14，6ABCD提交【2015年統(tǒng)考408】單選題1分對(duì)n個(gè)互不相同的符號(hào)進(jìn)行哈夫曼編碼。若生成的哈夫曼樹共有115個(gè)結(jié)點(diǎn)，則n的值是（）。56575860ABCD提交【2019年統(tǒng)考408】單選題1分若某二叉樹有5個(gè)葉子結(jié)點(diǎn)，其權(quán)值分別為10,12,16,21,30，則其最小的帶權(quán)路徑長度（WPL）是（）。89200208289ABCD提交【2021年統(tǒng)考408】單選題1分給定權(quán)值7，6，3，32，5，26，12，9，構(gòu)造相應(yīng)的哈夫曼樹，并計(jì)算其帶權(quán)路徑長度。為使結(jié)果答案唯一，請(qǐng)用左結(jié)點(diǎn)的值小于等于右結(jié)點(diǎn)的值來構(gòu)造哈夫曼樹。作答主觀題10分哈夫曼樹的類型定義template<classT>classhuffmanTree{private:structNode{ Tdata; //結(jié)點(diǎn)的數(shù)據(jù)域intweight; //結(jié)點(diǎn)的權(quán)值

intparent,left,right; //雙親及左右孩子的下標(biāo)Node(){ //構(gòu)造函數(shù)weight=parent=left=right=0;};};structhuffmanCode{ Tdata;stringcode; //保存data的哈夫曼編碼huffmanCode(){code="";} //構(gòu)造函數(shù)，編碼前code是空串};Node*hfTree; //順序結(jié)構(gòu)，保存huffman樹huffmanCode*hfCode; //順序結(jié)構(gòu)，保存huffman編碼intsize; //葉結(jié)點(diǎn)數(shù)voidselectMin(intm,int&p); //選出當(dāng)前集合中的最小元素public:huffmanTree(intinitSize); //構(gòu)造函數(shù)~huffmanTree(){delete[]hfTree;delete[]hfCode;} voidcreateHuffmanTree(constT*d,constdouble*w); //創(chuàng)建哈夫曼樹voidhuffmanEncoding(); //獲取huffman編碼voidprintHuffmanCode(); //輸出huffman編碼};哈夫曼樹的類型定義哈夫曼樹類型定義的說明(1)每個(gè)Node類型的元素保存的信息有結(jié)點(diǎn)的數(shù)據(jù)域data、權(quán)值weight、父結(jié)點(diǎn)和左右孩子的下標(biāo)parent、left、right。因?yàn)閚個(gè)葉結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)，哈夫曼樹可以用一個(gè)大小為2n的數(shù)組hfTree來存儲(chǔ)。數(shù)組下標(biāo)為0的單元不用，根結(jié)點(diǎn)存放在下標(biāo)為1的單元，葉結(jié)點(diǎn)依次存放在n+1到2n的位置。(2)parent域在構(gòu)造哈夫曼樹的過程中有兩個(gè)作用：一是在建立哈夫曼樹過程中，用作區(qū)別結(jié)點(diǎn)是否被使用過，parent=0表示該結(jié)點(diǎn)沒有雙親，還未被使用過，一旦被使用，就有了雙親，parent域的值就是指向雙親的指針。二是在構(gòu)造好哈夫曼樹之后求哈夫曼編碼時(shí)，需從葉子結(jié)點(diǎn)出發(fā)走一條從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，因此需要知道結(jié)點(diǎn)的雙親信息。構(gòu)造函數(shù)[代碼7.9]構(gòu)造函數(shù)template<classT>huffmanTree<T>::huffmanTree(intinitSize){size=initSize; //size為初始集合中的結(jié)點(diǎn)數(shù)hfTree=newNode[2*size]; //哈夫曼樹采用順序儲(chǔ)存結(jié)構(gòu)hfCode=newhuffmanCode[size];//哈夫曼編碼}[代碼7.10]根據(jù)葉結(jié)點(diǎn)數(shù)據(jù)數(shù)組d及其權(quán)值數(shù)組w創(chuàng)建哈夫曼樹。template<classT>voidhuffmanTree<T>::createHuffmanTree(constT*d,constdouble*w){inti,min1,min2; //最小樹、次最小樹的下標(biāo)for(i=size;i<2*size;++i){ //size個(gè)葉結(jié)點(diǎn)賦值hfTree[i].data=d[i-size];hfTree[i].weight=w[i-size];}創(chuàng)建哈夫曼樹for(i=size-1;i>0;--i){//合并產(chǎn)生n-1個(gè)新結(jié)點(diǎn)

//選出parent的值為0且權(quán)值最小的兩棵子樹min1、min2作為結(jié)點(diǎn)i的左右孩子selectMin(i+1,min1); hfTree[min1].parent=i;selectMin(i+1,min2); hfTree[min2].parent=i;hfTree[i].weight=hfTree[min1].weight+hfTree[min2].weight;hfTree[i].left=min1;hfTree[i].right=min2;}}創(chuàng)建哈夫曼樹選取根結(jié)點(diǎn)的權(quán)值最小的二叉樹[代碼7.11]選出parent的值為0且權(quán)值最小的子樹的根結(jié)點(diǎn)的下標(biāo)。template<classT>voidhuffmanTree<T>::selectMin(intm,int&p){intj=m;while(hfTree[j].parent!=0)j++; //跳過已有雙親的結(jié)點(diǎn)for(p=j,j+=1;j<2*size;j++) //向后掃描剩余元素if((hfTree[j].weight<hfTree[p].weight)&&0==hfTree[j].parent)p=j; //發(fā)現(xiàn)更小的記錄，記錄它的位置}*7.1表達(dá)式樹7.2哈夫曼樹和哈夫曼編碼7.2.1哈夫曼樹7.2.2哈夫曼編碼7.3堆和優(yōu)先級(jí)隊(duì)列*7.4并查集*7.5算法拓展*7.6

你怎么看？目錄CONTENTS概念和術(shù)語哈夫曼樹被廣泛應(yīng)用在各種技術(shù)中，其中最典型的就是在編碼技術(shù)上的應(yīng)用。利用哈夫曼樹，可以得到平均長度最短的編碼?；靖拍詈托g(shù)語:1.字符編碼：狹義的字符編碼是指給一組對(duì)象中的每一個(gè)對(duì)象標(biāo)記一個(gè)二進(jìn)制位串，以便文本在計(jì)算機(jī)中存儲(chǔ)和通過通信網(wǎng)絡(luò)的傳遞。2.等長編碼：表示一組對(duì)象的二進(jìn)制位串的長度相等，如ASCII編碼。3.不等長編碼：表示一組對(duì)象的二進(jìn)制位串的長度不相等4.前綴碼：任何一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴。哈夫曼編碼字符串：“CATCATTCPPCTCAC

”,編碼：C:00A:01T:10P:11，則報(bào)文為：“000110000110100011110010000100”考慮到出現(xiàn)頻率，C:0A:00T:1P:01則報(bào)文為：“00010001100101010000”。但：譯碼有困難：“0001”有多種譯法：CCP,AP,CAT,……設(shè)計(jì)的變長編碼必須滿足一個(gè)條件：任意一個(gè)編碼不能成為其它編碼的前綴，即必須是“前綴碼”。哈夫曼編碼

Huffman編碼方法：設(shè)有n種字符，在一個(gè)電文中，第i種字符出現(xiàn)的次數(shù)為Wi,編碼長度為li，則一段電文的總長度為：

L=w1l1+w2l2+…+wnln=∑wili使L最小，可以看作是已知n個(gè)結(jié)點(diǎn)的權(quán)wi，求一棵Huffman樹的問題。由此得到的二進(jìn)制編碼，稱為Huffman編碼。哈夫曼編碼用二叉樹可以構(gòu)造前綴碼；哈夫曼樹可以構(gòu)造最短的前綴碼（哈夫曼編碼）構(gòu)造哈夫曼編碼：將需要傳送的信息中各字符出現(xiàn)的頻率作為權(quán)值來構(gòu)造一棵哈夫曼樹，每個(gè)帶權(quán)葉結(jié)點(diǎn)都對(duì)應(yīng)一個(gè)字符，根結(jié)點(diǎn)到葉結(jié)點(diǎn)都有一條路徑，我們約定路徑上指向左子樹的分支用0表示，指向右子樹的分支用1表示，則根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)路徑上的0、1碼序列即為相應(yīng)字符的哈夫曼編碼。例如：字符集D={‘G’,‘O’,‘L’,‘E’,‘S’,‘D’，space}，各字符對(duì)應(yīng)的權(quán)值（使用頻率）W={4，6，1，2，1，1，2}。利用權(quán)值集W構(gòu)造哈夫曼樹，然后按照左子女為0，右子女為1的規(guī)則構(gòu)造哈夫曼編碼哈夫曼編碼如下：‘G’:10‘O’:11‘L’:0010‘E’:010‘S’:0011‘D’:000space:011

哈夫曼編碼ACBDEF160000111364125736912G0112801A：100B：11C：011D：1011E：1010F：000G：01自測(cè)題：哈夫曼編碼

哈夫曼編碼

求哈夫曼編碼的方法依次從葉結(jié)點(diǎn)出發(fā)，向上回溯，直至根結(jié)點(diǎn)，在回溯的過程中生成哈夫曼編碼。即從哈夫曼樹的葉結(jié)點(diǎn)出發(fā)，利用其雙親指針parent找到其雙親結(jié)點(diǎn)，然后再利用其雙親結(jié)點(diǎn)的指針域left和right來判斷該結(jié)點(diǎn)是雙親的左孩子還是右孩子，若是左孩子，則在該葉結(jié)點(diǎn)的編碼前添加‘0’，若是右孩子，則在該葉結(jié)點(diǎn)的編碼前添加‘1’。在編碼中，需要從葉子結(jié)點(diǎn)出發(fā)，走從葉子到根的路徑；譯碼中，需要從根到葉子。*生成哈夫曼編碼[代碼7.12]根據(jù)哈夫曼樹為每個(gè)葉結(jié)點(diǎn)生成哈夫曼編碼。template<classT>voidhuffmanTree<T>::huffmanEncoding(){ intf,p; //p是當(dāng)前正在處理的結(jié)點(diǎn)，f是p的雙親的下標(biāo)for(inti=size;i<2*size;++i){hfCode[i-size].data=hfTree[i].data;p=i;f=hfTree[p].parent;while(f){if(hfTree[f].left==p) //p是其雙親f的左孩子，編碼+‘0’hfCode[i-size].code='0'+hfCode[i-size].code;else //p是其雙親f的右孩子，編碼+‘1’hfCode[i-size].code='1'+hfCode[i-size].code;p=f;f=hfTree[p].parent;}}}已知字符集{a,b,c,d,e,f,g,h},若各字符的哈夫曼編碼依次是0100,10,,0000，0101,001,011,11,0001，則編碼序列0100011001001011110101的譯碼結(jié)果是（）acgabfhadbagbbafbeagdafeefgdABCD提交【2017年統(tǒng)考408】單選題1分5個(gè)字符有如下4種編碼方案，不是前綴編碼的是（）01,0000,0001,001,1011,000,001,010,1000,001,010,011,1000,100,110,1110,1100ABCD提交【2017年統(tǒng)考408】單選題1分已知字符集{a,b,c,d,e,f}，若各字符出現(xiàn)的次數(shù)分別為6,3,8,2,10,4，則對(duì)應(yīng)字符集中各字符的哈夫曼編碼可能是（）。00,1011,01,1010,11,10000,100,110,000,0010,0110,1011,11,0011,00,0100011,10,11,0010,01,000ABCD提交【2018年統(tǒng)考408】提示：只有字符b、d位于第四層，它們需要4位編碼，且前三位相同單選題1分*7.1表達(dá)式樹7.2哈夫曼樹和哈夫曼編碼7.3堆和優(yōu)先級(jí)隊(duì)列7.3.1二叉堆7.3.2優(yōu)先級(jí)隊(duì)列*7.4并查集*7.5算法拓展*7.6你怎么看？目錄CONTENTS二叉堆堆是一棵完全二叉樹，且滿足下述關(guān)系之一

ki≤k2i且ki≤k2i+1(i=1,2,…,

n/2

)或者：

ki≥k2i且ki≥k2i+1(i=1,2,…,

n/2

)其中，下標(biāo)是樹按層次遍歷的次序最大堆也稱大根堆或大堆：父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)孩子結(jié)點(diǎn)的鍵值，根結(jié)點(diǎn)K1是序列中的最大值。最小堆也稱小根堆或小堆：父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)孩子結(jié)點(diǎn)的鍵值，根結(jié)點(diǎn)K1是序列中的最小值。例如：序列D1={6，8，9，10，15，12，18，12’}是小根堆，D2={18，12，15，10，8，12’，6，9}是大根堆。二叉堆二叉堆的特性結(jié)構(gòu)性：符合完全二叉樹的結(jié)構(gòu)有序性：滿足父節(jié)點(diǎn)小于子節(jié)點(diǎn)（最小化堆）或父節(jié)點(diǎn)大于子節(jié)點(diǎn)（最大化堆）完全二叉樹適合用順序存儲(chǔ)結(jié)構(gòu)表示和實(shí)現(xiàn)，因此堆可以利用一維數(shù)組實(shí)現(xiàn)。對(duì)一棵有n個(gè)結(jié)點(diǎn)的二叉堆，對(duì)結(jié)點(diǎn)從1到n進(jìn)行編號(hào)，數(shù)組0號(hào)單元不使用，對(duì)任意一個(gè)結(jié)點(diǎn)i（1≤i≤n）有：若i=1，則結(jié)點(diǎn)i為根，無雙親；若i>1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)的編號(hào)是?i/2?。若2i≤n，則i的左孩子的編號(hào)是2i，否則i無左孩子；若2i＋1≤n，則i的右孩子的編號(hào)是2i+1，否則i無右孩子。例如，圖7.6的小根堆和大根堆可以存儲(chǔ)在如圖7.7(a)、(b)所示的一維數(shù)組中。二叉堆的存儲(chǔ)二叉堆的存儲(chǔ)*7.1表達(dá)式樹7.2哈夫曼樹和哈夫曼編碼7.3堆和優(yōu)先級(jí)隊(duì)列7.3.1二叉堆7.3.2優(yōu)先級(jí)隊(duì)列*7.4并查集*7.5算法拓展*7.6你怎么看？目錄CONTENTS基本的優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列(PriorityQueue)：是零個(gè)或多個(gè)元素的集合，優(yōu)先隊(duì)列中的每一個(gè)元素都有一個(gè)優(yōu)先級(jí)，元素出隊(duì)的先后順序由優(yōu)先級(jí)的高低決定，而不是由入隊(duì)的先后次序決定。優(yōu)先級(jí)高的先出隊(duì)，優(yōu)先級(jí)低的后出隊(duì)。優(yōu)先隊(duì)列在現(xiàn)實(shí)生活廣泛存在，例如排隊(duì)上車，老弱病殘?jiān)袃?yōu)先上車；排隊(duì)候診，危急病人優(yōu)先就診。優(yōu)先隊(duì)列的主要特點(diǎn)是支持從一個(gè)集合中快速地查找和刪除具有最大值或最小值的元素。最小優(yōu)先隊(duì)列，適合查找和刪除最小元素；最大優(yōu)先隊(duì)列中，適合查找和刪除最大元素。優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)方法很多，常用的如利用普通隊(duì)列實(shí)現(xiàn)，還可以利用二叉堆實(shí)現(xiàn)。優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)利用現(xiàn)有的隊(duì)列結(jié)構(gòu)。有兩種方法可以處理優(yōu)先級(jí)入隊(duì)時(shí)，按照優(yōu)先級(jí)在隊(duì)列中尋找合適的位置，將新入隊(duì)的元素插入在此位置。出隊(duì)操作的實(shí)現(xiàn)保持不變。入隊(duì)操作的實(shí)現(xiàn)保持不變，將新入隊(duì)的元素放在隊(duì)列尾。但出隊(duì)時(shí)，在整個(gè)隊(duì)列中查找優(yōu)先級(jí)最高的元素，讓它出隊(duì)。第一種方案的入隊(duì)操作的時(shí)間復(fù)雜度是O（N），出隊(duì)操作的時(shí)間復(fù)雜度是O（1）。第二種方案的入隊(duì)操作的時(shí)間復(fù)雜度是O（1），出隊(duì)操作的時(shí)間復(fù)雜度是O（N）。基于二叉堆的優(yōu)先級(jí)隊(duì)列

如果數(shù)值越小，優(yōu)先級(jí)越高，則可以用一個(gè)最小化堆存儲(chǔ)優(yōu)先級(jí)隊(duì)列在最小化堆中，最小元素是根元素，而根結(jié)點(diǎn)永遠(yuǎn)存放在數(shù)組的下標(biāo)為1的元素中。獲取隊(duì)頭元素的操作就是返回下標(biāo)為1的數(shù)組元素值出隊(duì)操作就是刪除下標(biāo)為1的數(shù)組元素中的值入隊(duì)操作就是在數(shù)組的末尾添加一個(gè)元素，但添加后要調(diào)整元素的位置，以保持堆的有序性優(yōu)先級(jí)隊(duì)列類數(shù)據(jù)成員：用一個(gè)動(dòng)態(tài)數(shù)組成員函數(shù)：實(shí)現(xiàn)隊(duì)列類的所有操作優(yōu)先級(jí)隊(duì)列的類型定義基于小根堆的最小優(yōu)先級(jí)隊(duì)列的定義如下：template<classelemType>classpriorityQueue:publicQueue<elemType>{private:intcurLength; //隊(duì)列中元素個(gè)數(shù)elemType*data; //指向存放元素的數(shù)組intmaxSize; //隊(duì)列的大小voidresize(); //擴(kuò)大隊(duì)列空間voidsiftDown(intparent);//從parent位置向下調(diào)整優(yōu)先級(jí)隊(duì)列voidsiftUp(intposition);//從position位置向上調(diào)整優(yōu)先級(jí)隊(duì)列public:priorityQueue(intinitSize=100);priorityQueue(constelemTypedata[],intsize);~priorityQueue(){delete[]data;}boolempty()const{returncurLength==0;} //判空intsize()const{returncurLength;} //求長度voidbuildHeap(); //建堆voidenQueue(constelemType&x); //入隊(duì)elemTypedeQueue(); //出隊(duì)elemTypegetHead()const{ //取隊(duì)首元素if(empty())throwoutOfRange();returndata[1];}};優(yōu)先級(jí)隊(duì)列的類型定義基于小根堆的最小優(yōu)先級(jí)隊(duì)列的基本操作1.入隊(duì)入隊(duì)操作是在堆中插入一個(gè)新元素堆的插入是在具有最大序號(hào)的元素之后插入新的元素或結(jié)點(diǎn)，否則將違反堆的結(jié)構(gòu)性。如果新元素放入后，沒有違反堆的有序性，那么操作結(jié)束。否則，讓該節(jié)點(diǎn)向父節(jié)點(diǎn)移動(dòng)，直到滿足有序性或到達(dá)根節(jié)點(diǎn)。新節(jié)點(diǎn)的向上移動(dòng)稱為向上調(diào)整在如下的堆中插入元素3的過程：入隊(duì)入隊(duì)[代碼7.15]入隊(duì)template<classelemType>voidpriorityQueue<elemType>::enQueue(constelemType&x){ if(curLength==maxSize-1)resize(); data[++curLength]=x; //下標(biāo)從1開始siftUp(curLength); //新入隊(duì)元素需向上調(diào)整}入隊(duì)向上調(diào)整堆[代碼7.16]向上調(diào)整堆，為提高效率，當(dāng)雙親的鍵值大時(shí)，采用向下移動(dòng)雙親數(shù)據(jù)的策略，而不是交換數(shù)據(jù)。template<classelemType>voidpriorityQueue<elemType>::siftUp(intposition){//從position開始向上調(diào)整elemTypetemp=data[position]; //保存position位置元素for(;position>1&&temp<data[position/2];position/=2)data[position]=data[position/2]; //position位置元素比雙親小，雙親下移data[position]=temp;}入隊(duì)的時(shí)間效率最壞情況是對(duì)數(shù)的，時(shí)間復(fù)雜度是O(log2n)平均情況，過濾會(huì)提前結(jié)束。有資料表明，平均是2.6次比較，因此元素平均上移1.6層。出隊(duì)當(dāng)最小元素被刪除時(shí)，在根上出現(xiàn)了一個(gè)空結(jié)點(diǎn)。堆的大小比以前小1，堆的結(jié)構(gòu)性告訴我們，最后一個(gè)結(jié)點(diǎn)應(yīng)該刪掉。為了保持完全二叉樹的性質(zhì)，將葉結(jié)點(diǎn)n中的元素暫時(shí)存放在結(jié)點(diǎn)i=1中。

為了保持小根堆的性質(zhì)，比較結(jié)點(diǎn)i（從根結(jié)點(diǎn)開始）和其較小孩子的鍵值，若結(jié)點(diǎn)i的鍵值大于其較小孩子的鍵值，將結(jié)點(diǎn)i中的元素與其較小孩子的元素交換，令結(jié)點(diǎn)i的較小孩子成為新的結(jié)點(diǎn)i，繼續(xù)向下比較，直到結(jié)點(diǎn)i的鍵值不大于其較小孩子的鍵值或i到達(dá)葉結(jié)點(diǎn)為止。向下調(diào)整過程如圖小根堆中最小元素3的出隊(duì)過程思考：能否利用堆，對(duì)無序集合排序？向下調(diào)整過程出隊(duì)[代碼7.17]出隊(duì)template<classelemType>elemTypepriorityQueue<elemType>::deQueue(){ if(empty())throwoutOfRange();elemTypemin;min=data[1]; //保存最小元素data[1]=data[curLength--]; //隊(duì)尾元素存入下標(biāo)1位置（堆頂）siftDown(1); //從隊(duì)首（堆頂）向下調(diào)整returnmin; //返回隊(duì)首元素}向下調(diào)整[代碼7.18]為提高效率，采用向上移動(dòng)數(shù)據(jù)的策略，而不是交換數(shù)據(jù)template<classelemType>voidpriorityQueue<elemType>::siftDown(intparent){ //從parent開始向下調(diào)整intchild;elemTypetmp=data[parent];//保存parent處結(jié)點(diǎn)for(;parent*2<=curLength;parent=child){ child=parent*2; //child用于記錄較小的子結(jié)點(diǎn)if(child!=curLength&&data[child+1]<data[child])child++; //右孩子更小if(data[child]<tmp)data[parent]=data[child];elsebreak;}data[parent]=tmp;}出隊(duì)操作的性能因?yàn)闃溆袑?duì)數(shù)的深度，在最壞情況下，出隊(duì)是一個(gè)對(duì)數(shù)時(shí)間的操作。出隊(duì)操作的時(shí)間復(fù)雜度是O(log2n)根據(jù)堆的有序性，堆中最后一個(gè)結(jié)點(diǎn)的值一般都是比較大的。因此，向下過濾很少有提前一或二層結(jié)束的，所以出隊(duì)操作平均也是對(duì)數(shù)時(shí)間。建堆方法一可以看成N次連續(xù)插入，其時(shí)間應(yīng)該是在O(NlogN)時(shí)間內(nèi)完成。事實(shí)上，在構(gòu)造過程中，我們并不關(guān)心每個(gè)元素加入后堆的狀態(tài)，我們關(guān)心的是N個(gè)元素全部加入后的最后狀態(tài)，最后的狀態(tài)是要保證堆的有序性。至于中間過程中的有序性是否成立并不重要。有了這個(gè)前提后，我們能將構(gòu)造堆的時(shí)間復(fù)雜度降到O（N）建堆過程方法二：利用堆的遞歸定義具有n個(gè)結(jié)點(diǎn)的完全二叉樹，其葉子結(jié)點(diǎn)被認(rèn)為符合堆的定義，其最后一個(gè)非終端結(jié)點(diǎn)的編號(hào)是

n/2

，從該結(jié)點(diǎn)開始，直到根結(jié)點(diǎn)，依次使用向下調(diào)整堆算法siftDown，使堆的序列從[n/2..n]，一直擴(kuò)大到[1..n]，就完成了初始堆的建立。例如，初始序列D={18，12，15，10，8，12’，6，9}，利用方法二建立小根堆的過程如圖7.10所示。首先，將它看成是一棵完全二叉樹，然后把它調(diào)整成一個(gè)堆自下往上調(diào)整每一個(gè)子堆建堆過程建堆[代碼7.19]建堆方法二的實(shí)現(xiàn)。template<classelemType>voidpriorityQueue<elemType>::buildHeap(){for(inti=curLength/2;i>0;i--)siftDown(i);

//[curLength/2..1]從下標(biāo)最大的非終端結(jié)點(diǎn)開始調(diào)整}[代碼7.21]構(gòu)造無序堆，有初始大小和初始序列，然后調(diào)用buildHeap()建堆。template<classelemType>priorityQueue<elemType>::priorityQueue(constelemType*items,intsize):maxSize(size+1),curLength(size){data=newelemType[maxSize];for(inti=0;i<size;i++)data[i+1]=items[i]; //拷貝元素}建堆建堆的時(shí)間代價(jià)分析建堆的時(shí)間是O(N)的。高度為h的節(jié)點(diǎn)，在shiftDown中交換的最大次數(shù)是h。建堆的時(shí)間是所有節(jié)點(diǎn)的調(diào)整時(shí)所需交換次數(shù)之和，即所有節(jié)點(diǎn)的高度之和。定理：對(duì)于一棵高度為h，包含了N=2H+1-1個(gè)結(jié)點(diǎn)的滿二叉樹，結(jié)點(diǎn)的高度和為N–H–1證明：高度為h的結(jié)點(diǎn)有一個(gè)，高度為h-1的結(jié)點(diǎn)有2個(gè)，高度為h-2的結(jié)點(diǎn)有22個(gè)，高度為h-i的節(jié)點(diǎn)有2i個(gè)。因此，所有節(jié)點(diǎn)的高度和為：*建堆的時(shí)間代價(jià)分析已知關(guān)鍵字序列5,8,12,19,28,20,15,22是小根堆（最小堆）,插入關(guān)鍵字3,調(diào)整后得到的小根堆是（）3,5,12,8,28,20,15,22,193,5,12,19,20,15,22,8,283,8,12,5,20,15,22,28,193,12,5,8,28,20,15,22,19ABCD提交【2009年統(tǒng)考408】單選題1分已知序列25，13，10，12，9是大根堆，在序列尾部插入新元素18，將其再調(diào)整為大根堆，調(diào)整過程中元素之間進(jìn)行的比較次數(shù)是（）1245ABCD提交【2009年統(tǒng)考408】單選題1分已知小根堆為8，15，10，21，34，16，12，刪除關(guān)鍵字8之后需重建堆，在此過程中，關(guān)鍵字之間的比較數(shù)是（）1234ABCD提交【2015年統(tǒng)考408】單選題1分下列關(guān)于大根堆（至少含2個(gè)元素）的敘述中正確的是（）。I．可以將堆看成一顆完全二叉樹II．可采用順序存儲(chǔ)方式保存堆III．可以將堆看成一棵二叉排序樹IV．堆中的次大值一定在根的下一層

僅I、II僅II、III僅I、II、IV僅I、III、IVABCD提交【2020年統(tǒng)考408】單選題1分在將數(shù)據(jù)序列（6,1,5,9,8,4,7）建成大根堆時(shí)，正確的序列變化過程是（）。6,1,7,9,8,4,5→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,56,9,5,1,8,4,7→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,56,9,5,1,8,4,7→9,6,5,1,8,4,7→9,6,7,1,8,4,5→9,8,7,1,6,4,56,1,7,9,8,4,5→7,1,6,9,8,4,5→7,9,6,1,8,4,5→9,7,6,1,8,4,5→9,8,6,1,7,4,5ABCD提交提示：如無特殊說明，默認(rèn)采用篩選法建堆【2018年統(tǒng)考408】單選題1分將關(guān)鍵字6,9,1,5,8,4,7依次插入到初始為空的大根堆H中，得到的H是（）9,8,7,6,5,4,19,8,7,5,6,1,49,8,7,5,6,4,19,6,7,5,8,4,1ABCD提交【2021年統(tǒng)考408】注意：本題沒有采用篩選法建堆，而是將關(guān)鍵字依次插入到初始為空的大根堆中，每插入一個(gè)新元素需要調(diào)用向上調(diào)堆算法siftUp。單選題1分對(duì)任意給定的含n(n>2)個(gè)字符的有限集S，用二叉樹表示S的哈夫曼編碼集和定長編碼集，分別得到二叉樹T1和T2。下列敘述中，正確的是（）T1與T2的結(jié)點(diǎn)數(shù)相同T1的高度大于T2的高度出現(xiàn)頻次不同的字符在T1中處于不同的層出現(xiàn)頻次不同的字符在T2中處于相同的層ABCD提交【2022年統(tǒng)考408】單選題1分對(duì)于關(guān)鍵碼集合K={19，8，35，65，40，3，7，45}，1、寫出建立的小根堆。2、寫出關(guān)鍵字3，7，8出堆的過程。作答主觀題10分建立小根堆，調(diào)堆的過程如下圖。其中n=8，n/2=4，所以從65開始調(diào)整。1983573406545以k3為根的子樹65>45調(diào)整以k2為根的子樹35>3調(diào)整以k1為根的子樹8<40,8<45無需調(diào)整以k0為根的子樹19>3調(diào)整19>7調(diào)整參考答案：建堆過程*7.1表達(dá)式樹7.2哈夫曼樹和哈夫曼編碼7.3堆和優(yōu)先級(jí)隊(duì)列*7.4并查集*7.5算法拓展*7.6你怎么看？目錄CONTENTS并查集并查集（UnionFindSets）：是一種特殊的集合，用于處理一些不相交集合的合并及查詢問題。并查集常用于求解等價(jià)類問題，如最小生成樹的Kruskal算法和求最近公共祖先等。并查集的常用基本操作有三個(gè)：(1)構(gòu)造操作：將集合中的每一個(gè)元素初始為一個(gè)獨(dú)立的不相交集合（等價(jià)類）；(2)合并操作：把屬于不同集合的兩個(gè)元素各自所屬的集合合并；(3)查找操作：找出元素屬于哪個(gè)子集。常用來確定兩個(gè)元素是否屬于同一子集。*7.1表達(dá)式樹7.2哈夫曼樹和哈夫曼編碼7.3堆和優(yōu)先級(jí)隊(duì)列*7.4并查集*7.5算法拓展*7.6你怎么看？目錄CONTENTS*算法拓展11.二叉樹的帶權(quán)路徑長度（WPL）是二叉樹中所有葉結(jié)點(diǎn)的帶權(quán)路徑長度之和。給定一棵二叉樹T，采用二叉鏈表存儲(chǔ)，結(jié)點(diǎn)結(jié)構(gòu)為：（left，weight，right），其中葉結(jié)點(diǎn)的weight域保存該結(jié)點(diǎn)的非負(fù)權(quán)值。設(shè)root為指向T的根結(jié)點(diǎn)的指針，請(qǐng)?jiān)O(shè)計(jì)求T的WPL的算法，要求：(1)給出算法的基本設(shè)計(jì)思想；(2)使用C或C++語言，給出二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義；(3)根據(jù)設(shè)計(jì)思想，采用C或C++語言描述算法，關(guān)鍵之處給出注釋?！?014年全國碩士研究生入學(xué)計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合試題（13分）】

*算法拓展1(2)二叉樹結(jié)點(diǎn)的數(shù)據(jù)類型定義如下：structNode{Node*left,*right; //指向左、右孩子的指針intweight; //結(jié)點(diǎn)的權(quán)值Node():left(NULL),right(NULL){}//無參構(gòu)造函數(shù)Node(intvalue,Node*l=NULL,Node*r=NULL){weight=value;left=l;right=r;}};*算法拓展1classBinaryLinkList{private:structNode{Node*left,*right; //指向左、右孩子的指針intweight; //結(jié)點(diǎn)的權(quán)值Node():left(NULL),right(NULL){}//無參構(gòu)造函數(shù)Node(intvalue,Node*l=NULL,Node*r=NULL){weight=value;left=l;right=r;}};Node*root; //指向根結(jié)點(diǎn)的指針intwplPreOrder(Node*t,intdeep)const;//前序遍歷求WPLpublic:intwplPreOrder(){returnwplPreOrder(root,0);}//前序遍歷求WPL的公有函數(shù)……};*算法拓展1(3)算法實(shí)現(xiàn)intBinaryLinkList::wplPreOrder(Node*t,intdeep)const{if(t==NULL)return0; //情況①：空子樹WPL為0elseif((t->left==NULL)&&(t->right==NULL)) returndeep*t->weight; //情況②：當(dāng)前結(jié)點(diǎn)為葉結(jié)點(diǎn) //返回葉結(jié)點(diǎn)的帶權(quán)路徑長度else //情況③：當(dāng)前結(jié)點(diǎn)為非終端結(jié)點(diǎn)returnwplPreOrder(t->left,deep+1)+wplPreOrder(t->right,deep+1); //遞歸統(tǒng)計(jì)左、右子樹的WPL之和}*算法拓展1簡答142（10分）若任一個(gè)字符的編碼都不是其他字符編碼的前綴，則稱這種編碼具有前綴特性?，F(xiàn)有某字符集（字符個(gè)數(shù)≥2）的不等長編碼，每個(gè)字符的編碼均為二進(jìn)制的0、1序列，最長為L位，且具有前綴特性。請(qǐng)回答下列問題：（1）哪種數(shù)據(jù)結(jié)構(gòu)適宜保存上述具有前綴特性的不等長編碼？（2）基于你所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)，簡述從0/1串到字符串的譯碼過程。（3）簡述判定某字符集的不等長編碼是否具有前綴特性的過程。【2020年全國統(tǒng)考408】（1）使用一棵二叉樹保存字符集中各字符的編碼，每個(gè)編碼對(duì)應(yīng)于從根開始到達(dá)某葉結(jié)點(diǎn)的一條路徑，路徑長度等干編碼位數(shù)，路徑到達(dá)的葉結(jié)點(diǎn)中保存該編碼對(duì)應(yīng)的字符。（2）從左至右依次掃描O/1串中的各位。從根開始，根據(jù)串中當(dāng)前位沿當(dāng)前結(jié)點(diǎn)的左子指針或右子指針下移，直到移動(dòng)到葉結(jié)點(diǎn)時(shí)為止。輸出葉結(jié)點(diǎn)中保存的字符。然后再從根開始重復(fù)這個(gè)過程。直到掃描到0/1串結(jié)束，譯碼完成。簡答1（3）二叉樹既可用于保存各字符的編碼，也可用于檢測(cè)編碼是否具有前綴特性。判定編碼是否具有前綴特性的過程，同時(shí)也是構(gòu)建二叉樹的過程。初始時(shí)，二叉樹中僅含有根結(jié)點(diǎn)，其左子指針和右子指針均為空。依次讀入每個(gè)編碼C，建立/尋找從根開始對(duì)應(yīng)于該編碼的一條路徑，過程如下∶對(duì)每個(gè)編碼，從左至右掃描C的各位，根據(jù)C當(dāng)前位（0或1）沿結(jié)點(diǎn)的指針（左子指針或右子指針）向下移動(dòng)。當(dāng)遇到空指針時(shí)，創(chuàng)建新結(jié)點(diǎn)，讓為空的指針指向該新結(jié)點(diǎn)并繼續(xù)移動(dòng)。沿指針移動(dòng)過程中，可能遇到三種情況∶①若遇到了葉結(jié)點(diǎn)（非根），則表明不具有前綴特性，返回；②若在處理C的所有位的過程中，均沒有創(chuàng)建新結(jié)點(diǎn)，則表明不具有前綴特性，返回；③若處理C的最后一個(gè)編碼位時(shí)創(chuàng)建了新結(jié)點(diǎn)，則繼續(xù)驗(yàn)證下一個(gè)編碼。若所有編碼均通過驗(yàn)證，則編碼具有前綴特性。簡答1*7.1表達(dá)式樹7.2哈夫曼樹和哈夫曼編碼7.3堆和優(yōu)先級(jí)隊(duì)列*7.4并查集*7.5算法拓展*7.6你怎么看？目錄CONTENTS二進(jìn)制編碼與法律法規(guī)“0”————違法……

并無中間量存在，切不可大意“1”————守法戴維·霍夫曼“霍夫曼編碼”的發(fā)明人戴維·霍夫曼(DavidAlbertHuffman)是信息論的先驅(qū),對(duì)計(jì)算機(jī)科學(xué)、通信等學(xué)科作出巨大貢獻(xiàn)。1925年生于俄亥俄州,從小聰慧好學(xué),他在俄亥俄州立大學(xué)畢業(yè)時(shí)只有17歲。然后他進(jìn)入MIT一邊工作,一邊深造,霍夫曼編碼就是他