第5章樹與二叉樹

基本內(nèi)容：樹的基本概念樹和樹林的存儲表示樹與樹林的周游（遍歷）

二叉樹二叉樹的存儲表示

二叉樹的周游和線索二叉樹樹、樹林與二叉樹的轉(zhuǎn)換

哈夫曼樹和哈夫曼編碼第五章樹與二叉樹線性結(jié)構(gòu)：唯一前驅(qū)、后繼，一對一關(guān)系。非線性結(jié)構(gòu)：存在兩個或兩個以上前驅(qū)或后繼。一對多，或多對多的關(guān)系。層次關(guān)系的問題可以用樹、二叉樹表示重點(diǎn)：樹、二叉樹的存儲結(jié)構(gòu)二叉樹的操作及其運(yùn)算的實(shí)現(xiàn)樹、樹林與二叉樹的轉(zhuǎn)換

Haffman樹與Haffman編碼樹的定義樹的邏輯表示：

T=(N,R) N={A,B,C,D,E,F,G,H,I,J} R={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<C,H>,<E,I>,<E,J>}A,B,…,J結(jié)點(diǎn)

<A,B>…,樹支（關(guān)系）一對多的關(guān)系，允許多個后繼。5.1樹的基本概念樹的定義基本術(shù)語（概念）樹林樹的基本運(yùn)算ABCDEFGHIJ樹的遞歸定義：n(n≥0)個結(jié)點(diǎn)的有窮集合T，當(dāng)T非空時滿足：有且僅有一個特別標(biāo)志的稱為根的結(jié)點(diǎn)除根外，其余結(jié)點(diǎn)分為m≥0個互不相交的非空集合T1、T2、…、Tm，而且每個非空集合Ti又是一顆樹，稱為T的子樹。樹的特點(diǎn)：根無前驅(qū)，其它結(jié)點(diǎn)有唯一前驅(qū)除樹葉（無子樹的結(jié)點(diǎn)）結(jié)點(diǎn)外，其它結(jié)點(diǎn)有一個或多個后繼空樹基本術(shù)語（概念）父結(jié)點(diǎn)、子結(jié)點(diǎn)、邊若y為x的一顆子樹的根，x為y的父結(jié)點(diǎn)

y為x的子結(jié)點(diǎn)，

有向?qū)?lt;x,y>為從x到y(tǒng)的邊兄弟：同一父母的結(jié)點(diǎn)互為兄弟祖先、子孫

若y在x的一顆子樹中（y≠x)，

x為y的祖先，y為x的子孫路徑、路徑長度

從祖先x到子孫y的邊的序列為x到y(tǒng)的路徑，邊的數(shù)目為路徑長度結(jié)點(diǎn)的層、樹的層數(shù)

根的層為0，其余結(jié)點(diǎn)的層為父結(jié)點(diǎn)層+1

樹的層數(shù)：結(jié)點(diǎn)的最大層數(shù)【空樹:0,其它:≥1】ABDCHIFGE124389675樹的深度和高度：結(jié)點(diǎn)的最大層數(shù)

【空樹:0,其它:≥1】結(jié)點(diǎn)的度和樹的度

結(jié)點(diǎn)的子樹個數(shù)為結(jié)點(diǎn)的度，最大結(jié)點(diǎn)的度為樹的度樹葉和分支結(jié)點(diǎn)

度數(shù)為0的結(jié)點(diǎn)為樹葉（終端結(jié)點(diǎn)），其余結(jié)點(diǎn)為分支結(jié)點(diǎn)無序樹、有序樹：子樹無次序的樹為無向樹，否則為有向樹結(jié)點(diǎn)的次序

在有向樹中從左往右規(guī)定結(jié)點(diǎn)的次序，以右結(jié)點(diǎn)為根的子樹中所有結(jié)點(diǎn)皆在左結(jié)點(diǎn)的右邊。ABDCHIFGE124389675

零顆或多顆互不相交的樹構(gòu)成樹林（森林），樹根互為兄弟。對樹中每個結(jié)點(diǎn)而言，其子樹的集合即為樹林。

就邏輯結(jié)構(gòu)而言，任何一棵樹是一個二元組Tree=(root,F),其中root稱為樹的根結(jié)點(diǎn)；F是m（m>=0）棵子樹構(gòu)成的樹林，F(xiàn)=(T1,T2,…,Tm),其中Ti=(ri,Fi)稱作根root的第i棵子樹；當(dāng)m0時，在樹根和其子樹林之間存在下列關(guān)系:

RF={<root,ri>|i=1,2,…,m,m>0}3.樹林4.樹的基本運(yùn)算

創(chuàng)建一顆空樹判斷是否為空樹求根結(jié)點(diǎn)求父結(jié)點(diǎn)求第一個子結(jié)點(diǎn)求右兄弟遍歷樹（樹的周游）5.2樹和樹林的存儲表示選擇存儲表示方法原則：結(jié)點(diǎn)本身+結(jié)點(diǎn)之間的關(guān)系樹的存儲表示（三種）父結(jié)點(diǎn)表示法[雙親表示法，上層（前驅(qū)）關(guān)系]子表表示法[孩子表示法，下層（后繼）關(guān)系]長子-兄弟表示法[孩子兄弟表示法，下層（長子）和同層（兄弟）關(guān)系]樹的存儲表示樹林的存儲表示（1）父結(jié)點(diǎn)表示法用一組連續(xù)空間存儲樹的結(jié)點(diǎn)，并附設(shè)一個指示器指示其雙親結(jié)點(diǎn)的位置。結(jié)構(gòu)類型如下：typedefstructParTreeNode/*樹中結(jié)點(diǎn)結(jié)構(gòu)*/{ DataType info; /*結(jié)點(diǎn)信息*/ int parent;/*父結(jié)點(diǎn)位置*/}ParTreeNodetypedefstructParTree{ ParTreeNode nodelist[MAXNUM]; int n;}ParTree,*PParTree;結(jié)點(diǎn)順序存放，結(jié)點(diǎn)的位置由結(jié)點(diǎn)在數(shù)組中的下標(biāo)給出。根結(jié)點(diǎn)無父結(jié)點(diǎn)，因此其parent為-1。優(yōu)點(diǎn)：a)容易求根、找父結(jié)點(diǎn)及其所有的祖先；

b)能找到結(jié)點(diǎn)的子女和兄弟；缺點(diǎn)：a)沒有表示出結(jié)點(diǎn)之間的左右次序（無法求最左右兄弟）；

b)找結(jié)點(diǎn)的子女和兄弟比較費(fèi)事；改進(jìn)方法：按一種周游次序在數(shù)組中存放結(jié)點(diǎn)。常見的一種方法是依次存放樹的先根序列，如下圖：Infoparenta-1b0c0d1e1f2g2h4i4j4普通改進(jìn)改進(jìn)后，任何結(jié)點(diǎn)的所有子孫都在該結(jié)點(diǎn)后連續(xù)存放。找長子運(yùn)算：如果存在長子，必定在結(jié)點(diǎn)的下一個位置

if(t->nodelist[p+1].parent==p) returnp+1; elsereturn-1;找右兄弟運(yùn)算：與結(jié)點(diǎn)具有相同父結(jié)點(diǎn)的后面結(jié)點(diǎn)

parent=t->nodelist[p].parent; for(i=p+1;i<t->n;i++) { if(t->nodelist[i].parent==parent) returni; } return–1;優(yōu)點(diǎn)：存儲密度高，求雙親和最左子女方便缺點(diǎn)：求右兄弟等運(yùn)算麻煩。（2）子表表示法typedefstructEdgeNode /*子表中結(jié)點(diǎn)的結(jié)構(gòu)*/{ int node_position; structEdgeNode*next;}EdgeNode;typedefstructChiTreeNode /*結(jié)點(diǎn)表中結(jié)點(diǎn)的結(jié)構(gòu)*/{ DataTypeinfo; EdgeNode*children;}ChiTreeNode;結(jié)點(diǎn)表中包含所有結(jié)點(diǎn)，其每一元素除了包含結(jié)點(diǎn)信息外還包含一個子表，存放該結(jié)點(diǎn)的所有子結(jié)點(diǎn)。結(jié)點(diǎn)表順序存放，子表用鏈接表示(按照從左往右次序存放子結(jié)點(diǎn)）。typedefstructChiTree /*樹結(jié)構(gòu)*/{ ChiTreeNode node_list[MAXNUM]; int root; /*根結(jié)點(diǎn)的位置*/ int n; /*結(jié)點(diǎn)的個數(shù)*/}ChiTree,*PChiTree; 優(yōu)點(diǎn)：方便找左子女、找所有子女等缺點(diǎn)：找父結(jié)點(diǎn)、找右兄弟麻煩找右兄弟：for(m=0;m<t->n;m++) { v=t->nodelist[m].children; while(v) {if(v->node_position==p) { if(v->next)returnv->next->node_position; elsereturn–1; } v=v->next; } } 找雙親：for(m=0;m<t->n;m++) { v=t->nodelist[m].children; while(v) { if(v->nodeposition==p)return(m); v=v->next; } return–1; }找到包含p的子表。在子表中，右邊的結(jié)點(diǎn)即為右兄弟找到包含p的子表。該子表對應(yīng)的結(jié)點(diǎn)即為雙親如果沒有root，如何找根？（3）長子-兄弟表示法typedefstructCSNode /*結(jié)點(diǎn)結(jié)構(gòu)*/{ DataType info; /*結(jié)點(diǎn)信息*/ structCSNode*lchild; /*最左子女*/ structCSNode*rsibling; /*右兄弟*/}CSTree,*PCSTree;優(yōu)點(diǎn)：方便找子女、找兄弟等運(yùn)算缺點(diǎn)：找父結(jié)點(diǎn)麻煩注意:通過長子-兄弟表示法，將一顆樹轉(zhuǎn)換為一顆二叉樹。并且在此二叉樹中，根結(jié)點(diǎn)的右兄弟指針一定為空（根無兄弟），該二叉樹根結(jié)點(diǎn)無右子樹，在樹林存儲表示中將用到此指針。找子女：找到長子，再沿著找右兄弟的指針找所有子女找父結(jié)點(diǎn)：首先找到長子，然后再找父結(jié)點(diǎn)。思考：如何修改長子-兄弟存儲結(jié)構(gòu)，更方便找雙親？typedefstructCSNode /*結(jié)點(diǎn)結(jié)構(gòu)*/{ DataTypeinfo; /*結(jié)點(diǎn)信息*/

structCSNode*parent; /*父結(jié)點(diǎn)*/ structCSNode*lchild; /*最左子女*/ structCSNode*rsibling; /*右兄弟*/}CSTree,*PCSTree;2.樹林的存儲表示（與樹對應(yīng)的三種）父結(jié)點(diǎn)表示法[雙親表示法]子表表示法[孩子表示法]長子-兄弟表示法[孩子兄弟表示法]

（1）父結(jié)點(diǎn)表示法(2)子表表示法(3)長子-兄弟表示法思考：如何求森林中包含幾棵樹？5.3樹和樹林的周游（遍歷）周游的定義：按照某種規(guī)則（次序）訪問樹或樹林中的所有結(jié)點(diǎn)，并且每個結(jié)點(diǎn)只能訪問一次。本質(zhì)：將非線性結(jié)構(gòu)轉(zhuǎn)換為元素線性序列。樹的周游按深度方向周游[縱向遍歷]

先根遍歷中根遍歷后根遍歷按寬度方向周游[橫向遍歷]

樹的周游樹林的周游與周游結(jié)合的存儲（1）深度方向先根遍歷

–先訪問根，再按照從左往右次序先根遍歷根的每顆子樹。

先根序列(1,2,3,5,8,9,6,10,4,7)中根遍歷

–先中根遍歷最左子樹，再訪問根，再按照從左往右次序中根遍歷根的其它子樹。

中根次序(2,1,8,5,9,3,10,6,7,4)后根遍歷

–按照從左往右次序后根遍歷根的每顆子樹，再訪問根

后根次序(2,8,9,5,10,6,3,7,4,1)特點(diǎn)：a)在先、中和后根遍歷序列中，樹結(jié)點(diǎn)的左右次序不變;

b)在先根遍歷序列中，結(jié)點(diǎn)的所有子孫都緊密排列在該結(jié)點(diǎn)的右邊；假定post(n)表示結(jié)點(diǎn)n在先根序列中的位置，

desc(n)表示結(jié)點(diǎn)n的子孫個數(shù)，則結(jié)點(diǎn)x是結(jié)點(diǎn)n的子孫的充分必要條件為：

post(n)+desc(n)≥post(x)>post(n)

c)在后根遍歷序列中，結(jié)點(diǎn)的所有子孫都緊密排列在該結(jié)點(diǎn)的左邊；假定post(n)表示結(jié)點(diǎn)n在后根序列中的位置，

desc(n)表示結(jié)點(diǎn)n的子孫個數(shù)，則結(jié)點(diǎn)x是結(jié)點(diǎn)n的子孫的充分必要條件為：

post(n)-desc(n)≤post(x)<post(n)先根遍歷中根遍歷后根遍歷任何結(jié)點(diǎn)，先根遍歷完后：如有右兄弟，進(jìn)入右兄弟；否則，進(jìn)入上一層（父結(jié)點(diǎn)）的右兄弟。任何結(jié)點(diǎn)，中根遍歷完（長子子樹也已經(jīng)遍歷完）后：1）如有第2顆子樹，進(jìn)入。2）否則（也無其它子樹），父結(jié)點(diǎn)。第2顆和2后的子樹，進(jìn)入前需要保存右兄弟，以便子樹遍歷完后，進(jìn)入右兄弟。任何結(jié)點(diǎn)，后根遍歷完后：如有右兄弟，進(jìn)入右兄弟；否則，上一層（父結(jié)點(diǎn)）先根遍歷（遞歸）：voidPreOrder(Nodep){

Nodec;

visit(p); //先訪問根

c=leftChild(p);//獲取長子

//按照從左往右次序先根遍歷子女

while(c)

{

PreOrder(c);

//先根遍歷

c=rightSibling(c);

//右兄弟

}}先根遍歷（非遞歸）:結(jié)點(diǎn)被彈棧，說明以該結(jié)點(diǎn)為根的子樹已遍歷完。如存在右兄弟，進(jìn)入右兄弟子樹；否則，繼續(xù)彈棧（彈出雙親）。voidPreOrder(Nodep){

Nodec,q;

Stacks=CreateEmptyStack();

//創(chuàng)建空棧

c=root(p);

do

{//順長子鏈一直下去，邊走邊訪問

//并壓入棧，便于今后右兄弟的訪問

while(c)

{

visit(c);

//訪問該結(jié)點(diǎn)

push(s,c);

//將該結(jié)點(diǎn)壓入棧

c=leftChild(c);

//獲取該結(jié)點(diǎn)的長子

}

while(!c&&!isEmptyStack(s))

{q=pop(s);

c=rightSibling(q);

}

}while(c);}421216521521752152121131進(jìn)入5進(jìn)入7進(jìn)入31245673中根遍歷（遞歸）：voidinOrder(Nodep){

Nodec;

c=leftChild(p);

//獲取該結(jié)點(diǎn)的長子

if(!c)

visit(p);

//不存在，訪問該結(jié)點(diǎn)

else

{

inOrder(c);

//中根遍歷長子

visit(p);

//訪問根

//中根遍歷其它子女

c=rightSibling(c);

while(c)

{

inOrder(c);

c=rightSibling(c);

}

}}中根遍歷（非遞歸）：結(jié)點(diǎn)被彈棧，說明其長子子樹已遍歷完。此時，訪問結(jié)點(diǎn)，并進(jìn)入第2顆子樹繼續(xù)遍歷。（如2nd不存在，繼續(xù)彈棧）。2nd顆和其它子樹進(jìn)入前，如右兄弟存在需要壓棧右兄弟，以便子樹遍歷完后進(jìn)入右兄弟。voidInOrder(Nodep){

Nodec,q;

Stacks=CreateEmptyStack();

//創(chuàng)建空棧

c=root(p);do{while(c) //順長子鏈,邊走邊壓棧

{ //【結(jié)點(diǎn)+第2子女】push(s,c); //結(jié)點(diǎn)入棧

c=leftChild(c);//長子

q=rightSibling(c);//第2子女

push(s,q); //第2子女入棧

}if(!IsEmptyStack(s)){c=pop(s); //第2子女(或下一子女)q=pop(s); //結(jié)點(diǎn)（或空）if(q)visit(q);//訪問結(jié)點(diǎn)

if(c&&(q=rightSibling(c))){//下一子女入棧

push(s,NULL);//區(qū)別第2子女

push(s,q);//將來進(jìn)入[只進(jìn)入，不訪問]}}}while(!IsEmptyStack(s));}1245673N4523152314N67531275316N7315317124563789100452315231c=0q=46031c=5q=207856031進(jìn)入5子樹856031c=0q=7086031c=8q=56031c=0q=85子樹結(jié)束31c=6q=0進(jìn)入6子樹6無右兄弟091063110631c=0q=901031c=10q=631c=0q=106子樹結(jié)束c=3q=103c=0q=31的1st子樹遍歷完，進(jìn)入2nd子樹中根遍歷（非遞歸）：結(jié)點(diǎn)被彈棧，說明其長子子樹已遍歷完。此時，訪問結(jié)點(diǎn)，并進(jìn)入第2顆子樹繼續(xù)遍歷。（如2nd不存在，繼續(xù)彈棧）。2nd顆（含2后的其它子樹）進(jìn)入前，如右兄弟存在需要壓棧右兄弟，以便子樹遍歷完后進(jìn)入右兄弟繼續(xù)遍歷。【注：如是二叉樹，2nd無右兄弟】后根遍歷（遞歸）：voidpostOrder(Nodep){

Nodec;

c=leftChild(q);

//獲取該結(jié)點(diǎn)的長子，

//然后按照從左往右的次序

//后根遍歷該結(jié)點(diǎn)的所有子女

while(c)

{//后根遍歷

postOrder(c);

//后根遍歷右兄弟

c=rightSibling(c);

}

visit(p);

//最后訪問根}后根遍歷（非遞歸）：站點(diǎn)被彈棧，說明其所有子樹已經(jīng)遍歷完。此時，需要訪問結(jié)點(diǎn)，并繼續(xù)右兄弟子樹遍歷（如右兄弟不存在，彈棧父結(jié)點(diǎn)）。voidpostOrder(Nodep){

Nodec,q;

Stacks=CreateEmptyStack();

//創(chuàng)建空棧

c=root(p);do{while(c){push(s,c); //結(jié)點(diǎn)入棧

c=leftChild(c);//順長子鏈

}if(!IsEmptyStack(s)){q=pop(s);visit(q); c=rightSibling(q);//右兄弟存在,進(jìn)入

if(!c)//右兄弟不存在：上一層

{

q=pop(s);visit(q);c=rightSibling(q);}}}while(!IsEmptyStack(s));}421652147521652172153121311245673(2)寬度方向按照層序進(jìn)行訪問：按照從左往右規(guī)則，首先訪問根，再訪問層為1的結(jié)點(diǎn)，再訪問層為2的結(jié)點(diǎn)，…，直到所有結(jié)點(diǎn)訪問為止。

訪問序列：(1,2,3,4,5,6,7,8,9,10)得到層序序列；實(shí)現(xiàn)方法（采用隊列實(shí)現(xiàn)）：首先將根送入隊列；其后每當(dāng)從隊列取出一個結(jié)點(diǎn)訪問之后，馬上把它的子女按照從左往右的次序送入隊列的尾部；重復(fù)該過程直到隊列為空。寬度優(yōu)先遍歷算法//隊列控制下的層次遍歷voidLevelOrder(Treet){

Nodec;

Queueq;

//隊列元素的類型為Node

q=CreateEmptyQueue();

//建立空隊列

c=root(t);

if(!c)

return;

enQueue(q,c);

//根入隊列

while(!isEmptyQueue(q))

//隊列非空

{

c=frontQueue(q);

//訪問并刪除結(jié)點(diǎn)

deQueue(q);

visit(c);

//獲取該結(jié)點(diǎn)的長子，然后將該結(jié)點(diǎn)的

//子女按照從左往右的次序加入隊列

c=leftChild(c);

while(c)

{enQueue(q,c);

//入隊列

c=rightSibling(c);

//右兄弟

}

}}1234344565676789789108910……12345672.樹林的周游

先根：訪問第一顆樹的根結(jié)點(diǎn)；先根遍歷第一顆樹的根結(jié)點(diǎn)的子樹樹林；先根遍歷除去第一顆樹后的樹林先根遍歷序列：（A,B,C,K,D,E,H,F,J,G)

后根：后根遍歷第一顆樹的根結(jié)點(diǎn)的子樹樹林；訪問第一顆樹的根結(jié)點(diǎn)；后根遍歷除去第一顆樹后的樹林后根遍歷序列：(B,K,C,A,H,E,J,F,G,D)先根遍歷第一棵樹先根遍歷其它樹后根遍歷第一棵樹后根遍歷其它樹3.樹、樹林的其它存儲表示[與周游方法結(jié)合]先得到周游結(jié)果，再根據(jù)結(jié)點(diǎn)結(jié)構(gòu)求其它信息。帶右兄弟指針的先根次序表示：structNode { DataTypeinfo; intltag; Pnodersibling; } ltag=0結(jié)點(diǎn)無子女

1結(jié)點(diǎn)有子女

info ABCKDEHFJG rsibling ltag1010110100帶雙標(biāo)記的先根次序表示(課后)：找子女：？找雙親：？帶長子指針的層次次序表示：structNode { DataTypeinfo; Pnodelchild; intrtag;(0:無右兄弟,1:有) }

lchild infoADBCEFGKHJ rtag1010110000找兄弟：rtag=0(無);rtag=1:右邊連續(xù)rtag=1，最后一個rtag=0找長兄：上一結(jié)點(diǎn)rtag=0，無長兄；否則找前面連續(xù)rtag=1的第一個結(jié)點(diǎn)為長兄找孩子：lchild后，找長子的兄弟找雙親：先找長兄，再找lchild指向長兄的結(jié)點(diǎn)。帶度數(shù)的后根次序表示(課后)：5.4二叉樹二叉樹的定義：結(jié)點(diǎn)的有限集合，該集合或者為空集，或者由一個稱為根的結(jié)點(diǎn)和兩顆互不相交的分別稱為根的“左子樹”和“右子樹”的二叉樹組成。1.基本概念

a)五種基本形態(tài)：b)

二叉樹不是樹的特殊情形，它們是兩個概念。樹和二叉樹之間最主要的差別是：二叉樹中結(jié)點(diǎn)的子樹要區(qū)分為左子樹和右子樹，即使在結(jié)點(diǎn)只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹?；靖拍钪匾再|(zhì)基本運(yùn)算滿二叉樹完全二叉樹c)

滿二叉樹：如果一棵二叉樹的任何結(jié)點(diǎn)或者是樹葉，或者有兩棵非空子樹，則此二叉樹稱作“滿二叉樹”。d)

完全二叉樹：如果一棵二叉樹至多只有最下面的兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則此二叉樹稱為“完全二叉樹”。完全二叉樹不一定是滿二叉樹。與其它教材的定義有區(qū)別其它教材的滿二叉樹形態(tài)結(jié)點(diǎn)數(shù):n=2k-1，k為層數(shù)e)擴(kuò)充二叉樹：把原二叉樹的結(jié)點(diǎn)都變?yōu)槎葦?shù)為2的分支結(jié)點(diǎn)，也就是說，不改變度數(shù)為2的結(jié)點(diǎn)；對于度數(shù)為1的結(jié)點(diǎn)，則增加一個分支；對于度數(shù)為0（樹葉）增加兩個分支。在擴(kuò)充的二叉樹里，新增加的外部結(jié)點(diǎn)的個數(shù)比原來的內(nèi)部結(jié)點(diǎn)個數(shù)多1。假定內(nèi)部結(jié)點(diǎn)數(shù)為n，則擴(kuò)充二叉樹中有2n條邊，2n+1個結(jié)點(diǎn)，因此外部結(jié)點(diǎn)數(shù)目為：2n+1-n=n+1。2n+1中包含一個根結(jié)點(diǎn)E=I+2n“外部路徑長度”E：在擴(kuò)充的二叉樹里從根到每個外部結(jié)點(diǎn)的路徑長度之和?！皟?nèi)部路徑長度”I：在擴(kuò)充的二叉樹里從根到每個內(nèi)部結(jié)點(diǎn)的路徑長度之和。E=2+2+4+4+3+3+3=21I=1+3+2+1+2=9E=9+2*6=9+12=21（1）在二叉樹的i層上最多有2i個結(jié)點(diǎn)（i≥

0）第i層：2i-1個結(jié)點(diǎn)（i≥1）（2）深度為k的二叉樹最多有2k-1個結(jié)點(diǎn)，（k≥

0）

【其它教材中，深度k，有2k-1個結(jié)點(diǎn)：滿二叉樹】（3）對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。證明：假定度數(shù)為1的結(jié)點(diǎn)數(shù)為n1，則有：n=n0+n1+n2

除根外，其它結(jié)點(diǎn)都有一條分支進(jìn)入，則分支數(shù)為:B=n-1

又所有的分支都有度數(shù)為2和度數(shù)為1的結(jié)點(diǎn)發(fā)出，因此B=2n2+n1

綜合上述三式得：n0=n2+12.二叉樹的重要性質(zhì)（4）具有n個結(jié)點(diǎn)的完全二叉樹的深度k為（5）如果對一棵有n個結(jié)點(diǎn)的完全二叉樹按從上到下、從左往右的順序?qū)渲兴薪Y(jié)點(diǎn)從1開始編號，則對任一結(jié)點(diǎn)i（1≤i≤n)，有：

【a】i=1，結(jié)點(diǎn)i是根；i>1,其雙親結(jié)點(diǎn)是

【b】2i>n，結(jié)點(diǎn)i無左孩子；否則，其左孩子是結(jié)點(diǎn)2i

【c】2i+1>n，結(jié)點(diǎn)i無右孩子；否則，其右孩子是結(jié)點(diǎn)2i+1（6）在擴(kuò)充二叉樹中，外部結(jié)點(diǎn)的個數(shù)比內(nèi)部結(jié)點(diǎn)個數(shù)多1（7）對于任意擴(kuò)充二叉樹，外部路徑長度E和內(nèi)部路徑長度I滿足如下關(guān)系：E=I+2n，其中n為內(nèi)部結(jié)點(diǎn)個數(shù)。證明：n=0，E=0，I=0，結(jié)論成立

n=1，E=2，I=0，結(jié)論成立假定對于任意n，有：En=In+2n

現(xiàn)在考慮n+1個內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹。在n+1個內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹中刪除一個原來二叉樹作為樹葉的、路徑長度為K的內(nèi)部結(jié)點(diǎn)，使之成為包含n個內(nèi)部結(jié)點(diǎn)的擴(kuò)充二叉樹。由于刪除了一個路徑長度為K的內(nèi)部結(jié)點(diǎn)，內(nèi)部路徑長度的變化為：

In=In+1-K

刪除了一個路徑長度為K的內(nèi)部結(jié)點(diǎn)導(dǎo)致刪除了兩個外部路徑長度為K+1的外部結(jié)點(diǎn)，增加了一個路徑長度為K的外部結(jié)點(diǎn)，外部路徑長度的變化為：

En=En+1-2(K+1)+K=En+1-K-2即，En+1=

En+K+2=In+2n+K+2=In+K+2(n+1)=In+1+2(n+1)因此，n+1時結(jié)論成立。3.二叉樹的基本運(yùn)算創(chuàng)建一棵空二叉樹；判斷某棵二叉樹是否為空；求二叉樹的根結(jié)點(diǎn)，若為空，則返回一特殊值；求二叉樹中某個指定結(jié)點(diǎn)的父結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)為根時，返回一特殊值；求二叉樹中某個指定結(jié)點(diǎn)的左子女結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)沒有左子女時，返回一特殊值；求二叉樹中某個指定結(jié)點(diǎn)的右子女結(jié)點(diǎn)，當(dāng)指定結(jié)點(diǎn)沒有右子女時，返回一特殊值；二叉樹的周游，即按某種方式訪問二叉樹中的所有結(jié)點(diǎn)，并使每個結(jié)點(diǎn)恰好被訪問一次。返回二叉鏈表5.5二叉樹的存儲表示順序表示（1）完全二叉樹根據(jù)性質(zhì)5，結(jié)點(diǎn)序號可以反映結(jié)點(diǎn)的邏輯關(guān)系，因此可以用一維數(shù)組按照從上到下、從左往右的順序存儲樹中所有結(jié)點(diǎn)，通過數(shù)組元素下標(biāo)反映完全二叉樹中結(jié)點(diǎn)的邏輯關(guān)系。ABDHCGFEIJBACDEFGHIJ數(shù)組下標(biāo)：0123456789順序表示鏈接表示（2）一般二叉樹如果仍然采用上述完全二叉樹方式存儲，則數(shù)組下標(biāo)不能反映結(jié)點(diǎn)之間的邏輯關(guān)系。為此，可以首先對一般的二叉樹進(jìn)行改造，增加一些不存在的空結(jié)點(diǎn)，使之成為完全二叉樹，然后再用一維數(shù)組順序存儲，增加的空結(jié)點(diǎn)用空表示。父結(jié)點(diǎn)：(i-1)/2,左子女：2i+1，右子女：2i+2與性質(zhì)5有差別（從0開始編號，性質(zhì)5從1開始）問題：對于完全或近似完全的二叉樹，宜采用上述順序結(jié)構(gòu)存儲。但對于一般二叉樹，如果增加的空結(jié)點(diǎn)非常多，則容易造成空間浪費(fèi)，此時不宜采用上述方法存儲。（3）特殊二叉樹

對于一種特殊情況，如果二叉樹為右單支樹[深度為k]，則需要一個長度為2k-1的一維數(shù)組，造成（2k-1）-k個結(jié)點(diǎn)浪費(fèi)。如果k=6,則有57個結(jié)點(diǎn)空間浪費(fèi)。ABC…順序存儲表示如下：typedefstructSeqBTree { DataType nodelist[MAXNODE]; intn; /*改造成完全二叉樹后結(jié)點(diǎn)的個數(shù)*/}SeqBTree,*PSeqBTree;2.鏈接表示（1）二叉鏈表

每個結(jié)點(diǎn)結(jié)構(gòu)為：其中：info項存儲結(jié)點(diǎn)信息，llink指向左孩子，rlink指向右孩子。llinkrlinkinfo基本運(yùn)算n個結(jié)點(diǎn)的二叉鏈表中有n+1個空指針。通過擴(kuò)充二叉樹中外部結(jié)點(diǎn)個數(shù)可以證明typedefstructBinTreeNode{ DataType info; structBinTreeNode *llink; structBinTreeNode *rlink;}BinTreeNode,*PBinTreeNode,BinTree,*PBinTree基本運(yùn)算實(shí)現(xiàn)llinkrlink（2）三叉鏈表每個結(jié)點(diǎn)結(jié)構(gòu)為：二叉鏈表每個結(jié)點(diǎn)增加指向父結(jié)點(diǎn)的指針plink，便得到三叉鏈表存儲表示。三叉鏈表對于找父結(jié)點(diǎn)等操作非常方便，但增加了空間要求。llinkplinkinforlink基本運(yùn)算typedefstructBinTreeNode{ DataType info; structBinTreeNode *llink; structBinTreeNode *rlink; structBinTreeNode *plink;}BinTreeNode,*PBinTreeNode,BinTree,*PBinTree（3）線索鏈表：修改空指針，指向其直接前驅(qū)或后繼的二叉鏈表

[后面詳細(xì)討論]ABDCEGHFItACBDEFGHI^^^^^^^^^^^二叉樹^tABCDEFGHI^^^^^^^^^

二叉鏈表表示（10個空指針）

三叉鏈表表示（空指針數(shù)？）5.6二叉樹的遍歷和線索二叉樹1.二叉樹的遍歷

(a)定義：按某條搜索路徑訪問樹中每一個結(jié)點(diǎn)，使得每個結(jié)點(diǎn)被訪問一次且僅被訪問一次。通過一次完整的遍歷，可以將二叉樹結(jié)點(diǎn)信息由非線性序列變?yōu)榫€性序列。因此，二叉樹的遍歷過程實(shí)際上是非線性結(jié)構(gòu)線性化的過程。

(b)遍歷方法：由二叉樹定義可知，二叉樹有三部分組成：根、左子樹和右子樹。因此，遍歷整個二叉樹實(shí)質(zhì)上就是按照某種次序依次遍歷這三部分。假定D、L、R分別表示遍歷根、遍歷左子樹、遍歷右子樹，按照排列組合，有6種遍歷方法：DLR,LDR,LRD,DRL,RDL,RLD。遍歷定義遍歷算法二叉樹的建立線索二叉樹DLR如果限定左右子樹的訪問按照先左后右，則上面6種只有3種符合，即：DLR,LDR,LRD，分別稱為：先根遍歷、中根遍歷、后根遍歷。(c)先根遍歷

根—>先根遍歷左子樹—>先根遍歷右子樹遍歷結(jié)果：ABDCEGFHI(d)中根遍歷中根遍歷左子樹—>根—>中根遍歷右子樹遍歷結(jié)果：DBAEGCHFI(e)后根遍歷后根遍歷左子樹—>后根遍歷右子樹—>根遍歷結(jié)果：DBGEHIFCAABDCEGHFI表達(dá)式：(a-b)÷(c+d)的二叉樹形式如右圖：則其DLR遍歷為：÷-ab+cd[前綴表達(dá)，波蘭式]LDR遍歷為：a-b÷c+d[中綴表達(dá)]LRD遍歷為：ab-cd+÷[后綴表達(dá)，逆波蘭式]任何一個算術(shù)表達(dá)式，都可以給出其對應(yīng)的二叉樹形式，其遍歷結(jié)果可以得到表達(dá)式的各種表達(dá)形式。÷-+abcd2.二叉樹的遍歷算法

[1]遞歸算法

a)先根b)中根c)后根

[2]非遞歸算法利用棧實(shí)現(xiàn)遍歷非遞歸算法。棧保存遍歷過程中結(jié)點(diǎn)或結(jié)點(diǎn)的左右孩子。數(shù)組S[M]作為棧，Top為棧頂指針，假定?？臻g足夠大，不會產(chǎn)生溢出問題。VoidPreOrder(BinTreet){if(!t) return;

visit(t);PreOrder(t->llink);PreOrder(t->rlink);}VoidInOrder(BinTreet){if(!t) return;InOrder(t->llink);

visit(t);InOrder(t->rlink);}VoidPostOrder(BinTreet){if(!t) return;PostOrder(t->llink);PostOrder(t->rlink);

visit(t);}與樹類似，但有差別！二叉樹基本運(yùn)算中，無找右兄弟運(yùn)算。如有：某些遍歷更簡單！但需要選擇合適的存儲表示。a)先根

思想：從根開始，沿左子樹一直走到末端為止，在走的過程中訪問所遇結(jié)點(diǎn)，并依次將所遇結(jié)點(diǎn)的非空右孩子進(jìn)棧。當(dāng)左子樹結(jié)點(diǎn)全處理完后，從棧頂退出某結(jié)點(diǎn)的右孩子，此時該結(jié)點(diǎn)的左子樹已經(jīng)遍歷完，再按照上述過程遍歷結(jié)點(diǎn)的右子樹，如此重復(fù)直到?？諡橹?。

先根非遞歸算法

也可壓結(jié)點(diǎn)本身，彈棧時（根+左子樹已經(jīng)遍歷完）

通過右孩子進(jìn)入右子樹?！绢愃茦涞南雀闅v】b)中根

思想：與先根遍歷基本類同，只是在沿左分支（左子樹）向前搜索過程中將遇到的結(jié)點(diǎn)進(jìn)棧，待遍歷完左子樹后，從棧頂退出結(jié)點(diǎn)并訪問，然后再遍歷右子樹。

中根非遞歸算法

由于只有左、右子女，與樹相比，簡單。

也可以同時壓右子女，彈棧時（左子樹已經(jīng)遍歷完）訪問結(jié)點(diǎn)，

通過右孩子進(jìn)入右子樹。【類似樹的中根遍歷】c)后根

思想：使用棧實(shí)現(xiàn)后根遍歷要比先、中根遍歷復(fù)雜。在后根遍歷中，當(dāng)搜索指針指向某個根結(jié)點(diǎn)時，不能馬上進(jìn)行訪問，而先要遍歷左子樹，所以要求根結(jié)點(diǎn)進(jìn)棧保存。當(dāng)遍歷完左子樹后，再次搜索到該結(jié)點(diǎn)時，還不能進(jìn)行訪問，還要遍歷其右子樹。所以，需要再次將該結(jié)點(diǎn)進(jìn)棧保存。為了區(qū)別同一結(jié)點(diǎn)的兩次入棧，需要一個特別的標(biāo)志：1表示該結(jié)點(diǎn)首次進(jìn)棧[遍歷左子樹前入棧]，2表示第二次進(jìn)棧[遍歷右子樹前入棧]。為此，有兩種辦法實(shí)現(xiàn)：**設(shè)立兩個棧，一個棧s1[M]用于存放結(jié)點(diǎn)，一個s2[M]

棧用于存放結(jié)點(diǎn)進(jìn)棧標(biāo)志。**修改原來的棧，增加標(biāo)志項（教材中的方法）

后根非遞歸算法教材中還給出了一種犧牲資源的后根遍歷算法。是否可參考樹的后根遍歷實(shí)現(xiàn)？左子樹遍歷完后，如何進(jìn)入右子女。二叉樹無右兄弟基本運(yùn)算！DLR3.二叉樹的建立“遍歷”是二叉樹各種操作的基礎(chǔ)，可以在遍歷過程中進(jìn)行各種操作，如可以在遍歷過程中生成結(jié)點(diǎn)，從而建立一棵二叉樹。順序存儲時：按照順序要求，把二叉樹中的結(jié)點(diǎn)加以擴(kuò)充，轉(zhuǎn)換成一個完全二叉樹形式，然后按層次周游順序把各個結(jié)點(diǎn)的信息輸入到nodelist數(shù)組中即可。二叉鏈表存儲：按先根遍歷次序生成二叉樹：例如要生成右面的二叉樹，只要按照下列順序輸入字符，即可建立相應(yīng)的二叉鏈表。

ABD@@@CE@G@@FH@@I@@其中，@為空結(jié)點(diǎn)(對應(yīng)于擴(kuò)充二叉樹中的外部結(jié)點(diǎn))。ABDCEGHFIBinTreeCreateBinTree(){BinTreet;charch;

scanf(“%c”,&ch);if(c==‘@’)t=NULL;else{t=(BinTree)malloc(sizeof(BinNode));t->data=ch; //根

t->llink=CreateBinTree(); //左子樹

t->rlink=CreateBinTree(); //右子樹

}returnt;}ABDCEGHFI對于每個結(jié)點(diǎn)，需要給出其左右子女結(jié)點(diǎn)信息。4.線索二叉樹（1）問題的提出遍歷可以將二叉樹中結(jié)點(diǎn)排列為一個線性表，因此結(jié)點(diǎn)的前驅(qū)、后繼可以在此線性表中得到。但是，二叉樹的存儲結(jié)構(gòu)中并沒有反映這種邏輯上的關(guān)系，只能通過對二叉樹進(jìn)行遍歷得到。問題：如果通過一次遍歷，保存主要信息，后面重復(fù)遍歷時利用這些信息，則可大大加快后面的遍歷速度。如何在遍歷過程中保存結(jié)點(diǎn)的前驅(qū)、后繼結(jié)點(diǎn)信息？解決辦法1：每個結(jié)點(diǎn)增加指向前驅(qū)、后繼結(jié)點(diǎn)的指針，遍歷過程中完成指針的設(shè)置。缺點(diǎn)：存儲空間增加，存儲要求提高，降低空間效率來提高時間效率。解決辦法2：前面證明過：在n個結(jié)點(diǎn)二叉樹的二叉鏈表存儲結(jié)構(gòu)中，有n+1個空指針。修改這些空指針讓其指向前驅(qū)或后繼結(jié)點(diǎn)，空llink指向前驅(qū)，空rlink指向后繼。線索：指向前驅(qū)或后繼的指針稱為線索。線索樹：加進(jìn)線索的二叉樹線索化：修改空指針為線索的過程為線索化，即通過線索化將二叉樹變?yōu)榫€索二叉樹。線索化與二叉樹的遍歷規(guī)則相互對應(yīng)，本節(jié)主要討論中序遍歷下的線索化。在線索二叉樹中，指針有兩類：指向其左右孩子的指針和指向前驅(qū)、后繼的線索。

如何區(qū)分它們？typedefstructThrTreeNode {DataTypeinfo;structThrTreeNode*llink,*rlink;intltag,rtag;}ThrTree,*PThrTree,*PThrTreeNode;每個結(jié)點(diǎn)增加兩個標(biāo)志項，分別標(biāo)志左右指針的類別：ltag=0llink為指針，指向左孩子

1llink為線索，指向結(jié)點(diǎn)的前驅(qū)rtag=0rlink為指針，指向右孩子

1rlink為線索，指向結(jié)點(diǎn)的后繼（2）線索樹結(jié)構(gòu)描述：rtagDATAllinkrlinkltag(3)中序線索化算法給定一棵樹，要將它按照中序線索化，其思想就是按照中序遍歷原則遍歷該二叉樹，在遍歷過程中用線索代替空指針。在未線索化之前，所有的llink和rlink皆為指針，因此所有的ltag和rtag為0。假定當(dāng)前正在訪問的結(jié)點(diǎn)為p，pr指向其中序遍歷前驅(qū)結(jié)點(diǎn)[上次剛訪問的結(jié)點(diǎn)]，修改線索包括兩步：

[a]如果pr的右指針為空， 修改pr的右指針指向p[p為pr的后繼]；

[b]如果p的左指針為空， 修改p的左指針指向pr[pr為p的前驅(qū)]。要實(shí)現(xiàn)非遞歸中序遍歷，需要一個附加的控制棧，棧結(jié)構(gòu)如下：#defineMAXNUM1000structSeqStack{PThrTreeNodes[MAXNUM]; //順序棧

intt; //棧頂 }typestructSeqStack*PSeqStack;中序線索化算法(4)線索二叉樹遍歷線索樹由于線索的存在，使得二叉樹的某些操作變得非常容易。例如：在某種次序遍歷序列中找結(jié)點(diǎn)的前驅(qū)、后繼不需要遍歷整個二叉樹，可直接根據(jù)線索或指針找到。找后繼：在中序線索二叉樹中，如果結(jié)點(diǎn)p的右指針為線索，則直接指向后繼；否則，其后繼為其右子樹最左下角的結(jié)點(diǎn)[中序遍歷右子樹第一個被訪問的結(jié)點(diǎn)]。找前驅(qū)：在中序線索二叉樹中，如果結(jié)點(diǎn)p的左指針為線索，則直接指向前驅(qū)；否則，其前驅(qū)為其左子樹最右下角的結(jié)點(diǎn)[中序遍歷左子樹最后一個被訪問的結(jié)點(diǎn)]。ABDCEGHFIDLR這樣，線索二叉樹的遍歷就不需要另設(shè)棧，算法簡單直接：

[a]找第一個被訪問的結(jié)點(diǎn)；

[b]沿著找后繼的辦法，找結(jié)點(diǎn)的后繼；

[c]重復(fù)[b]，直到結(jié)點(diǎn)的后繼為空為止。找第一個被訪問的結(jié)點(diǎn)也非常容易。對于中序線索二叉樹，第一個被訪問的結(jié)點(diǎn)是：從根結(jié)點(diǎn)出發(fā)沿左指針不斷往下走，左指針為空的結(jié)點(diǎn)[二叉樹最左下結(jié)點(diǎn)]。ABDCEGHFI（5）單邊線索二叉樹從上面的討論可以看出：線索二叉樹中既有指向前驅(qū)的左線索，又有指向后繼的右線索。如果只保留一邊[左或右]線索，便得到單邊線索二叉樹。左線索二叉樹：只將llink為空的指針修改為指向其前驅(qū)的線索，rlink不改動；右線索二叉樹：只將rlink為空的指針修改為指向其后繼的線索，llink不改動；單邊線索二叉樹應(yīng)用也非常廣泛。ABDCEGHFINULLABDCEGHFINULL5.7樹、樹林與二叉樹的轉(zhuǎn)換樹、樹林轉(zhuǎn)換為二叉樹樹、樹林和二叉樹皆可以通過二叉鏈表作為存儲結(jié)構(gòu)，因此借助二叉鏈表可以實(shí)現(xiàn)它們之間的轉(zhuǎn)換。通過樹、樹林的孩子-兄弟表示法得到的二叉鏈表作為轉(zhuǎn)換工具。樹對應(yīng)的二叉樹中，右子樹一定為空。樹林對應(yīng)的二叉樹中，最后一棵樹的右子樹必為空。樹轉(zhuǎn)換為二叉樹二叉樹轉(zhuǎn)換為樹轉(zhuǎn)換步驟：在所有相鄰的兄弟結(jié)點(diǎn)之間加一條線；對每個非終端結(jié)點(diǎn)，只保留它與最左子女的連線，刪除它與其它子女的連線；以根為軸心，將整顆樹順時針旋轉(zhuǎn)45度，使其結(jié)構(gòu)分明。2.二叉樹轉(zhuǎn)換為樹、樹林如某結(jié)點(diǎn)為其父母的左子女，則把該結(jié)點(diǎn)的右子女，右子女的右子女，……，都與該結(jié)點(diǎn)的父母用虛線連接起來；去掉原二叉樹中所有父母到右子女的連線；整理上面得到的樹或樹林，并將虛線改為實(shí)線。5.8哈夫曼樹及其應(yīng)用HaffMan樹的定義擴(kuò)充二叉樹外部路徑長度：

其中，Li是從根到第i個外部結(jié)點(diǎn)的路徑長度，

m為外部結(jié)點(diǎn)個數(shù)如果所有的外部結(jié)點(diǎn)都有一定的加權(quán)值，則外部路徑長度可以推廣為“帶權(quán)的外部路徑長度”：

其中，wi是第i個外部結(jié)點(diǎn)的加權(quán)值，其它同上。HaffMan樹的定義HaffMan算法構(gòu)造最優(yōu)二叉樹HaffMan編碼w1w2w3w4w5w6w7假定有一組實(shí)數(shù){w1,w2,…,wm}，現(xiàn)在要構(gòu)造一棵有m個外部結(jié)點(diǎn)的擴(kuò)充二叉樹，外部結(jié)點(diǎn)的加權(quán)值序列為{w1,w2,…,wm}，這樣的擴(kuò)充二叉樹有許多，帶權(quán)外部長度WPL最小所對應(yīng)的擴(kuò)充二叉樹稱為“HaffMan樹”或“最優(yōu)二叉樹”。例如：給定權(quán)值序列{2,3,4,11}，可以構(gòu)造出不同的擴(kuò)充二叉樹，并且可以計算出它們的WPL值，其中WPL最小值所對應(yīng)的擴(kuò)充二叉樹為HaffMan樹。114231142311423WPL=1x11+2x4+3x(2+3)=34WPL=2x3+3x(4+11)+1x2=53WPL=2x(2+11+3+4)=40對于擴(kuò)充二叉樹，外部結(jié)點(diǎn)個數(shù)=內(nèi)部結(jié)點(diǎn)個數(shù)+1。另外，從上面圖可以看出，在不同的擴(kuò)充二叉樹中，為了WPL值盡可能小，必須是：加權(quán)值較大的外部結(jié)點(diǎn)應(yīng)盡可能地靠近根（路徑長度短），這樣才能使得總的WPL值降低。給定一組加權(quán)值，有沒有一個通用的方法來尋找WPL最小的HaffMan樹？2.HaffMan算法構(gòu)造最優(yōu)二叉樹HaffMan最早給出了一種構(gòu)造最優(yōu)二叉樹的方法，因此稱為HaffMan算法：(1)根據(jù)給定的n個權(quán)值{w1,w2,…,wn}，構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}，其中每一棵二叉樹Ti中只有一個帶權(quán)為wi的根結(jié)點(diǎn)，其左右子樹為空。(2)在F中選取兩棵權(quán)值最小的樹作為左右子樹以構(gòu)造一棵新的二叉樹，且新二叉樹的根結(jié)點(diǎn)的權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和。(3)在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。(4)重復(fù)(2)和(3)，直到F中只含一棵樹為止。1142323511423549112354911204棵只有根的二叉樹2、3合并得到3棵二叉樹5、4合并得到2棵二叉樹9、11合并得到1棵二叉樹****左右選擇不同，得到的HaffMan樹形態(tài)不同，但WPL相同。HaffMan樹構(gòu)造的HaffMan算法實(shí)現(xiàn)：存儲結(jié)構(gòu)可以有多種，如二叉鏈表、三叉鏈表等。下面給出一種順序結(jié)構(gòu)(一維數(shù)組），結(jié)點(diǎn)定義：

ww:以該結(jié)點(diǎn)為根的子樹中所有外部結(jié)點(diǎn)的加權(quán)和。

parent:父結(jié)點(diǎn)在數(shù)組中的存儲位置（下標(biāo)），根無父，設(shè)為-1。

llink:左孩子存儲位置，對于外部結(jié)點(diǎn)，無孩子，設(shè)為-1。

rlink:右孩子存儲位置，對于外部結(jié)點(diǎn)，無孩子，設(shè)為-1。wwparentllinkrlink靜態(tài)鏈表：三叉鏈表w1plrw2………

假定外部結(jié)點(diǎn)個數(shù)為m，則內(nèi)部結(jié)點(diǎn)個數(shù)必為m-1，最后得到的HaffMan樹必定有2m-1個結(jié)點(diǎn)。因此，用2m-1個元素的一維數(shù)組就可以存儲該HaffMan樹。每個元素表示一個結(jié)點(diǎn)，前m個存儲外部結(jié)點(diǎn)，后m-1個用于內(nèi)部結(jié)點(diǎn)（需要構(gòu)造的結(jié)點(diǎn)）。structHtNode{intww;intparent,llink,rlink;};structHtTree{structHtNodeht[MAXNUM];introot;};tydefstructHtTree*PHtTree;w1plrw2………wm…………………012m-2m-1算法實(shí)現(xiàn)3.HaffMan編碼HaffMan樹有許多應(yīng)用，本節(jié)主要討論它在信息編碼中的應(yīng)用。（1）信息編碼：

定長編碼

–所有的字符都具有相同的編碼長度如26個字符：A,B