數(shù)據(jù)結(jié)構(gòu)-第四章-層次結(jié)構(gòu)-樹

第四章層次結(jié)構(gòu)——樹1.樹的描述有唯一的結(jié)點沒有前綴其余結(jié)點都有且只有一個前綴從根結(jié)點可以按后繼關(guān)系到達其余各結(jié)點

4.1、樹的概念4.1樹的概念4.2二叉樹4.3樹的應(yīng)用主要內(nèi)容2.樹的表示表(a(b(e(k,l),f),(c(g)),(d(h,i,j)))凸凹圖集合圖樹形圖4.1樹的概念樹的凹凸圖表示abekIfcgdhij樹的集合表示ghijaklbefcd樹的樹形表示3.樹的術(shù)語根、葉、分支結(jié)點父子、兄弟、祖孫關(guān)系高度度子樹、森林有序樹

4.1樹的概念結(jié)點的名稱根：樹中沒有前綴的結(jié)點成為根葉子：樹中沒有后繼的結(jié)點成為葉子分支節(jié)點：除根和葉子之外的結(jié)點結(jié)點的關(guān)系雙親和孩子：若結(jié)點a是結(jié)點b的前綴，則稱a是b的雙親，b是a的孩子兄弟：若結(jié)點a也是c的雙親，則c是b的兄弟，b也是c的兄弟祖先和子孫：若b又是e的前綴，則稱a是e的祖先，e是a的子孫結(jié)點的層次：即結(jié)點所在的層數(shù)，對于一棵樹，從根算起，根是第一層，根的孩子為第二層，依此類推高度：結(jié)點的層次，也叫做結(jié)點的高度。樹中結(jié)點高度最大者，為樹的高度。度：結(jié)點的度，指的是該節(jié)點孩子的個數(shù)，樹中所有結(jié)點中度最大者，為該樹的度。提問：葉子節(jié)點的度是多少？子樹：由樹的一部分結(jié)點組成，并保持原樹中的父子關(guān)系，其結(jié)構(gòu)也是一棵樹，成為原樹的子樹。森林：m棵互不相交的樹的集合有序樹：若樹中各結(jié)點的子樹從左到右是有次序地，不能交換則成該樹為有序樹4.樹的存儲結(jié)點結(jié)構(gòu)根指針:鏈頭指針空間利用率：4.1樹的概念返回樹中結(jié)點有多個后繼，所以不能使用順序結(jié)構(gòu)，采用鏈接結(jié)構(gòu)，每個結(jié)點中有多個指針域，指向孩子、雙親、兄弟等datachild1child2……childn存儲空鏈域太多，空間利用率低ab∧c∧∧de∧f∧∧∧g∧∧∧h∧∧∧i∧∧∧j∧∧∧k∧∧∧l∧∧∧t4.2二叉樹二叉樹的概念性質(zhì)二叉樹的存儲二叉樹的運算1、二叉樹的概念二叉樹是一種特殊的樹。其結(jié)點個數(shù)可以為0，這是稱其為空二叉樹。如果二叉樹不為空，則具有以下特征：每個結(jié)點最多只有兩棵子樹兩棵子樹有左右之分，其次序不能任意顛倒（即是有序樹）二叉樹的五種基本形態(tài)圖5.1二叉樹的五種基本形態(tài)

二叉樹中關(guān)系的一些定義左子結(jié)點:左子樹的根結(jié)點，稱為左孩子右子結(jié)點：右子樹的根節(jié)點，稱為右孩子兄弟結(jié)點：具有同一個父結(jié)點的，相互之間稱為兄弟結(jié)點葉結(jié)點：沒有孩子結(jié)點的結(jié)點稱為葉結(jié)點，也稱為終端結(jié)點一般的樹用二叉樹表示左手抱孩子，右手抱兄弟滿二叉樹和完全二叉樹如果一棵二叉樹每層的結(jié)點數(shù)目都達到最大，則這棵二叉樹稱作滿二叉樹(fullbinarytree)。如果一棵二叉樹最多只有最下面的兩層結(jié)點度數(shù)可以小于2，并且最下面一層的結(jié)點都集中在該層最左邊的連續(xù)位置上，則此二叉樹稱作完全二叉樹(completebinarytree)。1523456789114131211102345678911110完全二叉樹完全二叉樹的特點是：其葉結(jié)點只可能在層次最大的兩層出現(xiàn)完全二叉樹中由根結(jié)點到各個結(jié)點的路徑長度總和在具有同樣結(jié)點個數(shù)的二叉樹中達到了最小，即任意一棵二叉樹中根結(jié)點到各結(jié)點的最長路徑一定不短于結(jié)點數(shù)目相同的完全二叉樹中的路徑長度目錄

2、二叉樹的主要性質(zhì)性質(zhì)1.在二叉樹中，第i層上最多有2i-1個結(jié)點（i≥1）

證明：利用數(shù)學歸納法當i=1時，2i-1=1，只有一個根結(jié)點，正確。現(xiàn)在假設(shè)對所有的j，1≤j＜

i，命題成立，即第j層上之多有2j-1個結(jié)點。下面證明當就j=i時結(jié)論也成立。由歸納假設(shè)，第i-1層上最多有2i-2個結(jié)點。由于二叉樹每個結(jié)點的度數(shù)最大為2，所以第i層上的最大結(jié)點數(shù)為第i-1層上的最大結(jié)點數(shù)的2倍，即2i-1個。二叉樹的主要性質(zhì)性質(zhì)2.高度為k的二叉樹至多有

2k-1個結(jié)點（k≥0）。其中高度(depth)定義為二叉樹中層數(shù)最大的葉結(jié)點的層數(shù)。證明：由性質(zhì)1可知，第i層的最大結(jié)點數(shù)為2i-1，所以二叉樹的主要性質(zhì)性質(zhì)3.任何一棵二叉樹，若其終端結(jié)點數(shù)為n0

，度為2的結(jié)點數(shù)為n2，則n0=n2+1

。

證明：設(shè)n1為二叉樹中度為1的結(jié)點數(shù)。該二叉樹的結(jié)點總數(shù)n為度分別為0，1，2的結(jié)點數(shù)之和，即n=n0+n1+n2（5.1）

除根結(jié)點外，其余結(jié)點都有一條邊進入，設(shè)邊數(shù)為e，有n=e+1。由于這些邊是由度為1或2的的結(jié)點射出的，所以又有e=n1+2n2，于是得

n=e+1=n1+2n2+1 （5.2）由公式5.1和5.2得n0+n1+n2=n1+2n2+1，即n0=n2+1

二叉樹的主要性質(zhì)性質(zhì)4.滿二叉樹定理：非空滿二叉樹樹葉數(shù)目等于其分支結(jié)點數(shù)加1。

證明：滿二叉樹定理由性質(zhì)3可直接推出。

性質(zhì)5.滿二叉樹定理推論：一個非空二叉樹的空子樹數(shù)目等于其結(jié)點數(shù)加1。

證明：設(shè)二叉樹為T，度為1的結(jié)點下空子樹數(shù)目為1，度為0的節(jié)點空子樹數(shù)目為2，所以空子樹的數(shù)目為n1+2n0 根據(jù)性質(zhì)3，n=n1+n2+n0=n1+2n0-1 我們有：n1+2n0=n+1

二叉樹的主要性質(zhì)性質(zhì)6.有n個結(jié)點（n>0）的完全二叉樹的高度為[log2(n+1)]。其中二叉樹的高度(height)定義為二叉樹中層數(shù)最大的葉結(jié)點的層數(shù)。證明：假設(shè)高度為h，則根據(jù)性質(zhì)2和完全二叉樹的定義，有或不等式中各項取對數(shù)，于是得到。因為h為整數(shù)，所以h＝[log2(n+1)]。

二叉樹的主要性質(zhì)性質(zhì)7.對于具有n個結(jié)點的完全二叉樹，結(jié)點按層次由左到右編號，則對任一結(jié)點i（1≤i≤n）有

（1）如果i=1，則結(jié)點i是二叉樹的根結(jié)點；若i＞1，則其父結(jié)點編號是[i/2]。（2）當2i≤n時，結(jié)點i的左子結(jié)點是2i，否則結(jié)點i沒有左子結(jié)點。當2i+1≤n時，結(jié)點i的右子結(jié)點是2i+1，否則結(jié)點i沒有右子結(jié)點。

二叉樹的主要性質(zhì)證明：對于i=1，由完全二叉樹的定義，其左孩子的編號是2，如果2>n，即不存在編號為1的結(jié)點，此時結(jié)點i沒有左孩子。其右孩子的編號只能是3，如果3>n，此時結(jié)點i沒有右孩子。對于i>1分兩種情況討論：(1)設(shè)第j層的第一個結(jié)點編號為i(此時有i=2j-1)，則其左孩子必為第j+1層的第一個結(jié)點，其編號為2j=2i，如果2i>n，那么i沒有左孩子；其右孩子必為第j+1層第二個結(jié)點，其編號為2i+1。(2)假設(shè)第j層的某個結(jié)點編號為i，若它有左孩子，那么它的左孩子必然是第j+1層中的第2[i-2j-1]個，那么其左孩子的編號就是2j+2[i-2j-1]=2i；如果結(jié)點i有右孩子，那么其右孩子的編號必是2i+2。目錄

3、二叉樹的存儲通常采用鏈接的形式lchild指向左孩子，rchild指向右孩子lchilddatarchildlchildparentdatarchild5.3.1二叉樹的鏈式存儲結(jié)構(gòu)圖5.8

圖5.5中二叉樹的二叉鏈表存儲結(jié)構(gòu)

容易看出，在含有n個結(jié)點的二叉鏈表中有n+1個空鏈域?？梢岳眠@些空鏈域存儲其它的有用信息，形成其它的鏈式存儲結(jié)構(gòu)。圖5.5二叉樹示例結(jié)點類型typedef

struct

BiTreeNode

{

BiTreeNode*lchild;

BiTreeNode*rchild;

ElemTypedata;}BiTree;

4、運算遍歷（也叫周游）插入、刪除（1）遍歷遍歷廣度優(yōu)先遍歷——水平遍歷深度優(yōu)先遍歷——前序遍歷、中序遍歷、后序遍歷①水平遍歷概念：按照層次從小到大，從左到右訪問二叉樹的所有結(jié)點水平遍歷結(jié)果：ABCDEFGHI①水平遍歷思路：訪問結(jié)點的過程中應(yīng)該將其孩子結(jié)點存儲起來，等處理下一層時再取出來處理。從左到右遍歷，處理下一層時，結(jié)點遍歷的順序和存儲的順序一致所以采用隊列①水平遍歷算法初始化；當隊不空時，重復(fù)做：出隊；處理；如果有左子，左子進隊；如果有右子，右子進隊；voidLevelOrder(BiTree*r){

if(r==NULL) return;

linkQue

aQue;

CreatlnkQueue(aQue);

BiTree*p=r;

enQueue(aQue,p);//根入隊

while(!QueisEmpty(aQue)) {

deQueue(aQue,p);//隊頭出隊

visit(p);//訪問

if(p->lchild!=NULL)

enQueue(aQue,p->lchild);//左孩子入隊

if(p->rchild!=NULL)

enQueue(aQue,p->rchild);//右孩子入隊 }

DellnkQueue(aQue);}②前序遍歷概念：先處理根，然后遍歷左子樹，最后遍歷右子樹前序遍歷結(jié)果：ABDEGCFHI思路為了保證遍歷的持續(xù)，

需使用表臨時存儲

一些結(jié)點的地址。保存和取出的次序為先進后出。故應(yīng)使用棧。算法初始化當未遍歷完，重復(fù)做：如果當前結(jié)點非空，處理，進棧，取左子；否則，出棧，取右子。voidPreOrder(BiTree*r){

if(r==NULL) return;

lnkStack*s=NULL;

BiTree*p;

p=r;

while(!StackIsEmpty(s)||p) {

if(p) {

visit(p);

push(s,p); p=p->lchild; } else {

pop(s,p); p=p->rchild; } }}③中序遍歷概念：先遍歷左子樹，然后處理根，最后遍歷右子樹中序遍歷結(jié)果：DBGEACHFI思路在前序遍歷的基礎(chǔ)上，將處理結(jié)點的語句后移。voidInOrder(BiTree*r){

if(r==NULL) return;

lnkStack*s=NULL;

BiTree*p=r;

while(!StackIsEmpty(s)||p) {

if(p) {

push(s,p); p=p->lchild; } else {

pop(s,p);

visit(p); p=p->rchild; } }}④后序遍歷概念：先遍歷左子樹，然后遍歷右子樹，最后處理根后序遍歷結(jié)果：DGEBHIFCA思路需要兩次訪問棧頂結(jié)點。前者是為了處理其右子樹，后者是為了處理該結(jié)點。算法取棧頂結(jié)點；如果是第一次訪問，設(shè)標記，取右子；否則，出棧，處理。voidPostOrder(BiTree*r){

if(!r) return;

lnkStack*s=NULL;

BiTree*p=r;

PostOrderNodetag;

while(!StackIsEmpty(s)||p) {

while(p!=NULL) {

tag.p=p;

tag.isLeft=1;

push(s,tag); p=p->lchild; }

pop(s,tag);

if(tag.isLeft) {

tag.isLeft=0; p=tag.p;

push(s,tag); p=p->rchild; } else {

visit(tag.p); p=NULL; } }}深度優(yōu)先遞歸算法【算法1】

深度優(yōu)先前序遍歷voidPreOrder(BiTree*root){ //前序周游二叉樹或其子樹

if(r!=NULL){

Visit(r); //訪問當前結(jié)點

PreOrder(r->lchild); //前序周游左子樹

PreOrder(r->rchild); //前序周游右子樹 }}深度優(yōu)先遞歸算法【算法2】

中序遍歷voidInOrder(BiTree*r){ if(r!=NULL){

InOrder(r->lchild); //中序周游左子樹

Visit(r); //訪問當前結(jié)點

InOrder(r->rchild);//中序周游右子樹 }}深度優(yōu)先遞歸算法【算法3】后序遍歷voidPostOrder(BiTree*r){ //后序周游二叉樹或其子樹

if(r!=NULL){

PostOrder(r->lchild()); //后序周游左子樹

PostOrder(r->rchild()); //后序周游右子樹

Visit(r); //訪問當前結(jié)點 }}深度優(yōu)先遍歷二叉樹對于有n個結(jié)點的二叉樹，遍歷完樹的每一個元素都需要O(n)時間只要對每個結(jié)點的處理（函數(shù)Visit的執(zhí)行）時間是一個常數(shù)，那么遍歷二叉樹就可以在線性時間內(nèi)完成所需要的輔助空間為周游過程中棧的最大容量，即樹的高度最壞情況下具有n個結(jié)點的二叉樹高度為n，則所需要的空間復(fù)雜度為O(n)目錄

5、二叉樹的運算例1：求二叉樹結(jié)點個數(shù)思路：將原有遍歷算法中訪問結(jié)點的函數(shù)從打印結(jié)點內(nèi)容改為計數(shù)即可例2求二叉樹中值為v的結(jié)點的父結(jié)點值思路一：在遍歷算法中，訪問結(jié)點變?yōu)楸容^結(jié)點的孩子值是否為V。思路二：采用后序遍歷。棧頂元素即為父結(jié)點例4.3已知二叉樹root，要求按層輸出各結(jié)點值思路：按層處理，采用水平遍歷，用計數(shù)器記錄每層入隊時結(jié)點的個數(shù)，出隊時計數(shù)器值為0時，該層結(jié)束，換行voidLevelOrderInLine(BiTree*r)//例4.3{

if(r==NULL) return;

linkQue

aQue;

CreatlnkQueue(aQue);

BiTree*p=r;

enQueue(aQue,p);

intcount=1;

int

dcount=0;

while(!QueisEmpty(aQue)) {

if(dcount==0) {

dcount=count; count=0; }

deQueue(aQue,p);

dcount--;

visit(p);

if(dcount==0)

cout<<endl;

if(p->lchild!=NULL) {

enQueue(aQue,p->lchild); count++; }

if(p->rchild!=NULL) {

enQueue(aQue,p->rchild); count++; } }

DellnkQueue(aQue);}4.2.6二叉樹的其他存儲及運算①數(shù)組存儲②帶逆存儲③穿線存儲①數(shù)組存儲Struct

arrTree{ElemTypedata;int

lchildint

rchild}arrTree

a[n];0A121B342C-153D-1-14E6-15F786G-1-17H-1-18I-1-1②帶逆存儲對于經(jīng)常求父結(jié)點的問題，結(jié)點在存儲時，可以存儲父結(jié)點lchildparentdatarchild③穿線存儲穿線存儲的二叉樹，也叫穿線樹、或線索二叉樹。利用結(jié)點中空閑的左右子鏈域：若作子鏈域空，則存儲制定遍歷下的前綴結(jié)點的地址；若右子鏈域空，則存儲指定遍歷下后繼結(jié)點的地址構(gòu)造方法

寫出遍歷序列畫出穿線鏈修改相應(yīng)鏈域:為了區(qū)別是否是穿線鏈，加標記前序遍歷穿線樹ABDEGCFHI中序穿線樹DBGEACHFI后序遍歷：DGEBHIFCA4.3樹的應(yīng)用1.二叉排序樹2.堆排序3.哈夫曼樹4.決策樹5.博弈樹1、二叉排序樹二叉搜索樹中的每個非空結(jié)點表示一個記錄某結(jié)點左子樹不空，則左子樹上所有結(jié)點的值均小于該結(jié)點的關(guān)鍵碼值若其右子樹不為空，則右子樹上所有結(jié)點的值均大于該結(jié)點的關(guān)鍵碼值樹中各結(jié)點的關(guān)鍵碼必須是唯一的二叉搜索樹可以是一棵空樹，任何結(jié)點的左右子樹都是二叉搜索樹,按照中序周游整個二叉樹得到一個由小到大有序排列1、二叉排序樹對于關(guān)鍵碼集合K={50，19，35，55，20，5，100，52，88，53，92}，二叉排序樹的生成過程如圖所示：5051955355220100539288查找插入刪除二叉排序樹的查找二叉排序樹的高效率在于繼續(xù)檢索時只需要查找兩棵子樹之一：將給定值key與根結(jié)點的關(guān)鍵碼比較，如果key小于根結(jié)點的值，則只需要檢索左子樹如果key大于根結(jié)點的值，就只檢索右子樹這個過程一直持續(xù)到key被匹配成功或者遇到葉結(jié)點為止如果遇到葉結(jié)點仍沒有發(fā)現(xiàn)key，那么key就不在這棵二叉搜索樹中查找運算

無需遍歷算法效率與樹的高度相關(guān)二叉排序樹的插入算法：插入運算

要點：保持二叉排序樹的特性插入位置的選擇二叉排序樹的插入算法：需要運用檢索方法，查找待插入關(guān)鍵碼是否在樹中如果存在則不允許插入重復(fù)關(guān)鍵碼如果直到找到空結(jié)點還沒有發(fā)現(xiàn)重復(fù)關(guān)鍵碼，那么就把新結(jié)點插入到待插入方向作為新的葉結(jié)點對于給定的關(guān)鍵碼集合，可以從一個空的二叉搜索樹開始，按照檢索路徑搜索這棵二叉樹，將關(guān)鍵碼一個個插入到相應(yīng)的葉結(jié)點位置，從而動態(tài)生成二叉搜索樹二叉排序樹插入操作：將待插入結(jié)點的關(guān)鍵碼與根結(jié)點的關(guān)鍵碼相比較，若待插入的關(guān)鍵碼小于根結(jié)點的關(guān)鍵碼，則進入左子樹，否則進入右子樹。按照同樣的方式沿檢索路徑直到葉結(jié)點，確定插入位置，把待插入結(jié)點作為一個新葉結(jié)點插入到二叉搜索樹中。二叉排序樹的刪除設(shè)pointer，temppointer是指針變量，其中pointer表示要刪除的結(jié)點。首先找到待刪除的結(jié)點pointer，刪除該結(jié)點的過程如下：若結(jié)點pointer沒有左子樹，則用pointer右子樹的根代替被刪除的結(jié)點pointer；若結(jié)點pointer有左子樹，則在左子樹里找到按中序周游的最后一個結(jié)點temppointer，把temppointer的右指針置成指向pointer的右子樹的根，然后用結(jié)點pointer左子樹的根代替被刪除的結(jié)點pointer。

二叉排序樹的刪除圖5.12二叉搜索樹的刪除示例圖5.11二叉搜索樹二叉排序樹的刪除改進的二叉搜索樹結(jié)點刪除算法的思想為：若結(jié)點pointer沒有左子樹，則用pointer右子樹的根代替被刪除的結(jié)點pointer若結(jié)點pointer有左子樹，則在左子樹里找到按中序周游的最后一個結(jié)點temppointer（即左子樹中的最大結(jié)點）由于temppointer沒有右子樹，刪除該結(jié)點只需用temppointer的左子樹代替temppointer，然后用temppointer結(jié)點代替待刪除的結(jié)點pointer二叉搜索樹的刪除圖5.13改進的二叉搜索樹的刪除圖5.11二叉搜索樹52.552.5堆排序相關(guān)概念滿二叉樹完全二叉樹堆排序堆：是這樣的二叉樹，他的每個結(jié)點的值都大于它的兩個孩子（如果存在）的值，這就是堆最大堆：如果結(jié)點的值都大于孩子的值最小堆：如果結(jié)點的值都小于孩子的值302510201755421355941746堆的性質(zhì)從邏輯的角度來講，堆是一種樹形結(jié)構(gòu)，而且是一種特殊的完全二叉樹。此完全二叉樹的每個結(jié)點對應(yīng)于序列中的一個關(guān)鍵碼，根結(jié)點對應(yīng)于關(guān)鍵碼K0，按層次從左至右依次類推。說其特殊，主要是因為堆序只是局部有序，即最小堆對應(yīng)的完全二叉樹中所有內(nèi)部結(jié)點的值均不大于其左右孩子的關(guān)鍵碼值，而一個結(jié)點與其兄弟之間沒有必然的聯(lián)系。最小堆不像二叉搜索樹那樣實現(xiàn)了關(guān)鍵碼的完全排序。相比較而言，只有當結(jié)點之間是父子關(guān)系的時候，才可以確定這兩個結(jié)點關(guān)鍵碼的大小關(guān)系。堆排序思路：將一個順序表看作是順序存儲的完全二叉樹將其調(diào)整為堆，則得到最大結(jié)點最大結(jié)點離堆，剩下結(jié)點調(diào)整成堆，次大結(jié)點離堆重復(fù)上述過程，直到只剩下一個結(jié)點（46，94，13，42，55，17，10，70）4694131017554270建堆算法從最后一個非葉結(jié)點開始逐個篩for(p=n/2;p>=1;p--)

sift(p,n);n/2篩一個結(jié)點的算法當p有孩子時將p較大的孩子=>k如果s[p]<s[k]則交換s[p],s[k]

否則結(jié)束（46，94，13，42，55，17，10，70）4694131017554270堆排序算法

set_heap(s,n)for(i=n;i>=2;i--)swap(s[1],s[i])sift(1,i-1)時間效率建堆算法：篩n/2個結(jié)點，log2n次比較選擇排序：n-1遍，log2n次比較

O(nlog2n) 3、哈夫曼樹

Huffman樹

Huffman編碼Huffman樹假設(shè)有n個權(quán)值分別為w1，w2，…，wn(n≥2)的結(jié)點，求帶權(quán)路徑長度就是要構(gòu)造一棵二叉樹，每一個葉子結(jié)點ki取wi作為它的權(quán)，li表示該葉子結(jié)點的路徑長度，則帶權(quán)路徑長度可記作WPL(T)WPL(T)=,其中帶權(quán)路徑長度最小的二叉樹稱為Huffman樹。

Huffman樹例如，圖中表示了三棵具有4個葉結(jié)點的二叉樹，各葉結(jié)點的權(quán)值分別為6，2，3，4。它們的帶權(quán)路徑長度分別為：(a)6×2+2×2+3×2+4×2=30(b)6×2+2×3+3×3+4×1=31(c)6×1+2×3+3×3+4×2=29其中，5.18(c)中所示的二叉樹帶權(quán)路徑長度最小。可以驗證，它就是一棵Huffman樹，也就是說，這棵樹在所有的具有6，2，3，4權(quán)值的葉結(jié)點的二叉樹中帶權(quán)路徑長度最小。圖5.18具有不同帶權(quán)外部路徑長度的二叉樹3、Huffman樹建立Huffman編碼樹：(1)對于給定的n個權(quán)值w1，w2，…，wn(n≥2)，構(gòu)成n棵二叉樹的集合T={T1，T2，…，Tn}，使得每一棵二叉樹只具有一個帶權(quán)為wi的根結(jié)點。(2)構(gòu)造一棵新的二叉樹，在集合T中找出兩個權(quán)值最小的樹作為新樹根結(jié)點的左右子樹，把新樹根結(jié)點的權(quán)值賦為其左右子樹根結(jié)點的和。(3)在集合T中刪除這兩棵樹，并把得到的新二叉樹加入到集合中。(4)重復(fù)步驟(2)、(3)的操作，直到集合T中只含有一棵樹為止。5.6.1Huffman樹Huffman樹的構(gòu)造過程236495152364（1）HT是權(quán)值越大的越靠近根結(jié)點；（2）HT不唯一，但WPL一定相等。5915typedef

struct

HuffmanNode{

intweight;//權(quán)值

intparent;//雙親下標

int

lchild,rchild;//左右孩子下標}HTree;HTree*intHTree(int*Element,int

n,int&cursize,int&size){//初始化，將權(quán)值Element賦給哈夫曼樹為葉結(jié)點

inti;

HTree*list; size=2*n-1;//樹中結(jié)點的個數(shù)

list=newHTree[size];

for(i=0;i<n;i++) {

list[i].weight=Element[i]; }

for(i=0;i<size;i++) {

list[i].parent=-1;

list[i].lchild=list[i].rchild=0; }

cursize=n; returnlist;}bool

FindMinTwo(HTree*list,int

cursize,int&f,int&s){

inti;

for(i=0;i<cursize;i++) {

if(list[i].parent==-1) { f=i; break; } }

if(i>=cursize) returnfalse;

for(++i;i<cursize;i++) {

if(list[i].parent==-1) { s=i; break; } }

if(i>=cursize) returnfalse;

if(list[f].weight>list[s].weight) {

int

tmp;

tmp=f; f=s; s=tmp; }

for(++i;i<cursize;i++) {

if(list[i].parent==-1&&list[i].weight<list[f].weight) { s=f; f=i; } elseif(list[i].parent==-1&&list[i].weight<list[s].weight) { s=i; } } returntrue;

}voidCreatHuffmanTree(HTree*&list,int

size,int&cursize){

int

f,s;

while(FindMinTwo(list,cursize,f,s)) {

list[cursize].weight=list[f].weight+list[s].weight;

list[cursize].lchild=f;

list[cursize].rchild=s;

list[f].parent=cursize;

list[s].parent=cursize;

list[cursize].parent=-1;

cursize++; }}5.6.2Huffman編碼Huffman編碼過程如下：用d1，d2，…，dn作為外部結(jié)點構(gòu)造具有最小路徑長度的二叉樹把從每個結(jié)點引向其左子結(jié)點的邊標上號碼0，從每個結(jié)點引向其右子結(jié)點的邊標上號碼1從根結(jié)點到每個葉結(jié)點路徑上的編號連接起來就是這個外部結(jié)點所代表字符的編碼。得到的二進制前綴碼就稱作Huffman編碼圖5.20

Huffman編碼示例5.6.2Huffman編碼用Huffman算法構(gòu)造出的二叉樹給出了各字符的編碼，同時也用來譯碼從二叉樹的根開始，把二進制編碼每一位的值與Huffman樹邊上標記的0，1相匹配，確定選擇左分支還是右分支，直至確定一條到達樹葉的路徑。一旦到達樹葉，就譯出了一個字符。然后繼續(xù)用這棵二叉樹繼續(xù)譯出其它二進制編碼AACBACBAABAABCDCACADAACCA定長編碼：A:00;B:01;C:10;D:11編碼長度：50

哈夫曼編碼AACBACBAABAABCDCACADAACCA不定長編碼：A:12;B:4;C:7;D:2A:0;B:01;C:1;D:11編碼長度：31001010101...AACBACBAABAABCDCACADAACCA不定長編碼：A:12;B:4;C:7;D:2A:0;B:101;C:11;D:100編碼長度：440011101011101…返回voidCode(HTree*list,char**Hc,intn){

int

start,pi,j,i=0; char*s=newchar[n];

while(i<n){ s[n-1]='\0'; start=n-1; pi=list[i].parent; j=i;

while(pi!=-1){

if(list[pi].lchild==j) s[--start]='0'; elses[--start]='1'; j=pi; pi=list[pi].parent; }

strcpy(Hc[i],&s[start]); i++; } delete[]s;}5.6.2Huffman編碼

例如，在一個數(shù)據(jù)通信系統(tǒng)中使用的字符是a，b，c，d，e，f，g，對應(yīng)的頻率分別為15，2，6，5，20，10，18。各字符的二進制編碼為：a：00b：11110c：1110d：11111e：10f：110g