數(shù)據(jù)結(jié)構(gòu)與算法 課件 第6章 樹和二叉樹

第6章樹和二叉樹線性結(jié)構(gòu)與非線性結(jié)構(gòu)線性表、棧和隊列等數(shù)據(jù)結(jié)構(gòu)都屬于線性結(jié)構(gòu)，其元素間的邏輯關(guān)系都呈現(xiàn)一對一的關(guān)系。樹結(jié)構(gòu)和圖結(jié)構(gòu)屬于非線性結(jié)構(gòu)，其元素間的邏輯關(guān)系分別呈現(xiàn)一對多和多對多的關(guān)系。樹的元素之間存在明顯的分支和層次關(guān)系。它在客觀世界中大量存在，例如人類社會的家譜、各種社會組織結(jié)構(gòu)、計算機操作系統(tǒng)的多級目錄等。1【本章重點】①樹和二叉樹的定義；②二叉樹的性質(zhì)；③二叉樹和樹的存儲表示；④二叉樹的遍歷和遍歷算法的應(yīng)用；⑤樹、森林與二叉樹之間的轉(zhuǎn)換；⑥哈夫曼樹及應(yīng)用。2【本章難點】①二叉樹深度優(yōu)先非遞歸遍歷算法；②基于二叉樹深度優(yōu)先遞歸遍歷實現(xiàn)二叉樹的其他操作；③線索二叉樹。3【本章內(nèi)容】樹的基本概念二叉樹二叉樹的遍歷線索二叉樹樹和森林哈夫曼樹及其應(yīng)用習(xí)題646.1樹的基本概念樹的定義（遞歸定義）：樹（Tree）是n（n≥0）個結(jié)點的有限集合T，滿足兩個條件：（1）有且僅有一個特定的稱為根（Root）的結(jié)點，它沒有前驅(qū)；（2）其余的結(jié)點可分成m個互不相交的有限集合T1,T2,…,Tm，其中每個集合又是一棵樹，并稱為根的子樹。當(dāng)n=0時的空集合定義為空樹。5關(guān)于樹的基本術(shù)語:結(jié)點：指樹中的一個元素，包含數(shù)據(jù)項及若干指向其子樹的分支。結(jié)點的度：指結(jié)點擁有的子樹個數(shù)。樹的度：指樹中最大結(jié)點度數(shù)。葉子：指度為零的結(jié)點，又稱為終端結(jié)點。孩子：一個結(jié)點的子樹的根稱為該結(jié)點的孩子。雙親：一個結(jié)點的直接上層結(jié)點稱為該結(jié)點的雙親。兄弟：同一雙親的孩子互稱為兄弟。結(jié)點的層次：從根結(jié)點開始，根結(jié)點為第一層，根的孩子為第二層，根的孩子的孩子為第三層，依次類推。66.1樹的基本概念6.1樹的基本概念樹的深度：樹中結(jié)點的最大層次數(shù)。

堂兄弟：雙親在同一層上的結(jié)點互稱為堂兄弟。路徑：若存在一個結(jié)點序列k1,k2,…,kj,可使k1到達kj,則稱這個結(jié)點序列是k1到達kj的一條路徑。子孫和祖先：若存在k1到kj的一條路徑k1,k2,…,kj，則k1,…,kj-1為kj的祖先，而k2,…,kj為k1的子孫。森林：m(m≥0)棵互不相交的樹的集合構(gòu)成森林。有序樹和無序樹：若將樹中每個結(jié)點的各個子樹都看成是從左到右有次序的（即不能互換），則稱該樹為有序樹，否則為無序樹。7樹的存儲結(jié)構(gòu)（1）順序存儲順序存儲時，首先必須對樹形結(jié)構(gòu)的結(jié)點進行某種方式的線性化，使之成為一個線性序列，然后存儲。（2）鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯r，使用多指針域的結(jié)點形式，每一個指針域指向一棵子樹的根結(jié)點。由于樹的分支數(shù)不固定，很難給出一種固定的存儲結(jié)構(gòu)，通常采用二叉樹的形式存儲樹。86.2二叉樹二叉樹定義（遞歸定義）：

二叉樹是n（n≥0）個結(jié)點的有限集，它或為空樹（n=0），或由一個根結(jié)點及兩棵互不相交的、分別稱作這個根的左子樹和右子樹的二叉樹構(gòu)成。二叉樹的五種基本形態(tài)：二叉樹與度為2的樹的區(qū)別：二叉樹的子樹有左右之分，而樹的子樹不分左右。9性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(i≥1)。證明：可用數(shù)學(xué)歸納法予以證明。

當(dāng)i=1時，有2i-1=20=1，同時第一層上只有一個根結(jié)點，故命題成立。

設(shè)當(dāng)i=k時成立，即第k層上至多有2k-1個結(jié)點。

當(dāng)i=k+1時，由于二叉樹的每個結(jié)點至多有兩個孩子，所以第k+1層上至多有2

2k-1=2k個結(jié)點，故命題成立。10二叉樹的性質(zhì)二叉樹的性質(zhì)性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點(k≥1)。證明：性質(zhì)1給出了二叉樹每一層中含有的最大結(jié)點數(shù)，深度為k的二叉樹的結(jié)點總數(shù)至多為

故命題成立。11二叉樹的性質(zhì)在講性質(zhì)3之前，我們先了解什么是滿二叉樹和完全二叉樹。一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹。

滿二叉樹的特點是每一層的結(jié)點數(shù)都達到該層可具有的最大結(jié)點數(shù)。如果一個深度為k的二叉樹，它的結(jié)點按照從根結(jié)點開始，自上而下，從左至右進行連續(xù)編號后，得到的順序與滿二叉樹相應(yīng)結(jié)點編號順序一致，則稱這個二叉樹為完全二叉樹。完全二叉樹的1~k-1層上共有2k-1-1個結(jié)點，第k層的結(jié)點集中在左邊。滿二叉樹一定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。12二叉樹的性質(zhì)性質(zhì)3：對任何一棵二叉樹，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。證明：設(shè)度為1的結(jié)點數(shù)為n1，則一棵二叉樹的結(jié)點總數(shù)為：n=n0+n1+n2

因為除根結(jié)點外，其余結(jié)點都有一個進入的分支(邊)，設(shè)B為分支總數(shù)，則n=B+1。又考慮到分支是由度為1和2的結(jié)點發(fā)出的，故有

B=2n2+n1，即n=2n2+n1+1

比較兩式可得n0=n2+1，證畢。

13二叉樹的性質(zhì)性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為

log2n

+1或

log2(n+1)

。

其中，

x

表示不大于x的最大整數(shù)，

x

表示不小于x的最小整數(shù)。證明：設(shè)完全二叉樹的深度為k，則有

2k-1-1<n2k–1

2k-1

n<2k

取對數(shù)k-1log2n<k

因為k為整數(shù)，所以k=log2n

+114二叉樹的性質(zhì)性質(zhì)5：如果將一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序(自頂向下，同一層自左向右）連續(xù)編號1,2,…,n，第i個結(jié)點(1≤i≤n)具有以下關(guān)系：若i=1，則結(jié)點i是二叉樹的根結(jié)點，無雙親；若i>1，則結(jié)點i的雙親為結(jié)點

i/2

若2*i≤n，則結(jié)點i的左孩子為2*i，否則無左孩子若2*i+1≤n，則結(jié)點i的右孩子為2*i+1，否則無右孩子若i為偶數(shù)，且i!=n，則其右兄弟為i+1若i為奇數(shù)，且i!=1，則其左兄弟為i-1結(jié)點i所在層次為

log2i

+11516與二叉樹性質(zhì)相關(guān)的幾個例題【例1】若一棵二叉樹的葉子數(shù)為n，在該二叉樹中左、右指針域皆非空的結(jié)點個數(shù)為________?！纠?】任意一棵具有n個結(jié)點的二叉樹，若它有m個葉子，則該二叉樹上度為1的結(jié)點為________個?！纠?】深度為6的二叉樹最多有________個結(jié)點。根據(jù)性質(zhì)3分析：n0=m，n2=n0-1=m-1度為1的結(jié)點個數(shù)：n-m-(m-1)=n-2m+1根據(jù)性質(zhì)2分析：2k-1深度為6的二叉樹最多的結(jié)點個數(shù)：26-1=63根據(jù)性質(zhì)3分析：n0=n，n2=n0-1=n-1

子樹皆非空（度為2）的結(jié)點個數(shù)為n-1。17【例4】具有n個結(jié)點的完全二叉樹，若按層次從上到下、從左到右對其編號（根結(jié)點為1號），則編號最大的分支結(jié)點序號是__（1）__，編號最小的分支結(jié)點序號是__（2）__，編號最大的葉子結(jié)點序號是__（3）_，編號最小的葉子結(jié)點序號是__（4）__。

根據(jù)性質(zhì)5分析：（1）編號最大的分支結(jié)點序號是

n/2

（2）編號最小的分支結(jié)點的序號是1（3）編號最大的葉子結(jié)點序號是n（4）編號最小的葉子結(jié)點序號是

n/2+118【例5】將含有83個結(jié)點的完全二叉樹從根結(jié)點開始編號，根結(jié)點的編號為1，后面按從上到下、從左到右的順序?qū)Y(jié)點編號，那么編號為41的雙親結(jié)點編號為______?！纠?】設(shè)深度為k的二叉樹上只有度為0和度為2的結(jié)點，則這類二叉樹上所含結(jié)點總數(shù)最少______個?！纠?】深度為5的完全二叉樹最多有______個結(jié)點，最少有______個結(jié)點。根據(jù)性質(zhì)5分析，編號為41的雙親結(jié)點編號為：

41/2=20根據(jù)性質(zhì)2分析，1~k-1層為滿二叉樹，含有2k-1-1個結(jié)點，由于只有度為0和度為2的結(jié)點，所以第k層上至少有兩個結(jié)點，二叉樹上所含結(jié)點總數(shù)最少有2k-1+1個。根據(jù)性質(zhì)2分析，最多有25-1=31個結(jié)點，最少有24-1+1=16個結(jié)點。19【例8】如果將一棵有n個結(jié)點的完全二叉樹按層編號，則對任一編號為i(1≤i≤n)的結(jié)點X有：若i=1,則結(jié)點X是__（1）__；若i>1,則X的雙親PARENT(X)的編號為__（2）__。若2i>n，則結(jié)點X無__（3）__且無__（4）__；否則，X的左孩子LCHILD(X)的編號為__（5）__。若2i+1>n，則結(jié)點X無__（6）__；否則，X的右孩子RCHILD(X)的編號為__（7）__。根據(jù)性質(zhì)5分析：（1）根結(jié)點 （2）

i/2

（3）左孩子 （4）右兄弟（5）2i （6）右孩子 （7）2i+1二叉樹的存儲結(jié)構(gòu)（1）順序存儲結(jié)構(gòu)①存儲一棵完全二叉樹根據(jù)二叉樹性質(zhì)5，在一棵完全二叉樹中，按照從根結(jié)點起，自上而下，從左至右的方式對結(jié)點進行順序編號，便可得到一個反映結(jié)點之間關(guān)系的線性序列。完全二叉樹的順序存儲結(jié)構(gòu)：20②存儲一般二叉樹為了能夠通過下標(biāo)反映出結(jié)點之間的關(guān)系，必須通過增加虛結(jié)點的方法，將二叉樹映射為完全二叉樹。然后按照完全二叉樹進行存儲。21二叉樹順序存儲結(jié)構(gòu)的類型定義#definemaxsize1024;typedefchardatatype;typedefstruct{ datatypedata[maxsize];//存放二叉樹的向量

intlast;//最后一個結(jié)點的下標(biāo)}sequenlist;根據(jù)性質(zhì)2，采用順序存儲結(jié)構(gòu)存儲一棵深度為k的完全二叉樹或一般二叉樹，向量的長度是2k-1。22由于一般二叉樹必須按照完全二叉樹進行存儲，可能會浪費很多存儲空間。單支樹就是一個極端的情況。例如存儲一棵只有右分支的二叉樹，所需的向量長度為25-1=31，其中存放了5個結(jié)點和26個虛結(jié)點。23（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)①二叉鏈表每個結(jié)點含有數(shù)據(jù)域和2個指針域，左、右指針域分別用來指向左孩子和右孩子。二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)通常采用二叉鏈表。

二叉鏈表結(jié)點的結(jié)構(gòu)體類型定義：

typedefchardatatype；

typedefstructnode{

datatypedata；

structnode*lchild，*rchild；

}bitree；

bitree*root;

其中root是指向根結(jié)點的指針，當(dāng)二叉樹為空時，root為NULL值。若結(jié)點的某個孩子不存在時，該結(jié)點相應(yīng)的指針域為NULL值。24【例】采用二叉鏈表存儲二叉樹。25

在二叉鏈表中，只能找到某個結(jié)點的后繼結(jié)點，不能找到某個結(jié)點的前驅(qū)結(jié)點。

n個結(jié)點的二叉鏈表中，共有2n個指針域，其中n－1個指針域用于指示結(jié)點，其余n＋1個指針域必為空。②

三叉鏈表26每個結(jié)點含有數(shù)據(jù)域和3個指針域，左、右指針域分別用來指向左孩子和右孩子，雙親指針域指向直接前驅(qū)結(jié)點。二叉樹的建立（建立二叉鏈表）算法的基本思想按照結(jié)點的序號，依次輸入結(jié)點信息，若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點。若新結(jié)點是第1個結(jié)點，則令其為根結(jié)點，否則將新結(jié)點作為孩子鏈接到它的雙親結(jié)點上。如此反復(fù)進行，直到輸入結(jié)束標(biāo)志“＃”為止。27算法實現(xiàn)時的考慮設(shè)置一個指針數(shù)組作為隊列保存已輸入結(jié)點的地址（虛結(jié)點的地址為空），隊尾(rear)指向當(dāng)前輸入的結(jié)點，隊頭(front)指向這個結(jié)點的雙親結(jié)點。由于根結(jié)點的地址放在隊列的第一個單元里，所以當(dāng)rear為偶數(shù)時，則rear所指的結(jié)點應(yīng)作為左孩子與其雙親鏈接，否則rear所指的結(jié)點應(yīng)作為右孩子與其雙親鏈接。若雙親結(jié)點或孩子結(jié)點為虛結(jié)點，則無須鏈接。當(dāng)一個雙親結(jié)點與兩個孩子鏈接完畢，則進行出隊操作，使隊頭指針指向下一個待鏈接的雙親結(jié)點。28二叉樹的建立（建立二叉鏈表）算法bitree*CREATREE()//建立二叉樹函數(shù)，函數(shù)返回指向根結(jié)點的指針{

charch;//結(jié)點信息變量

bitree*Q[maxsize];//設(shè)置指針類型數(shù)組來構(gòu)成隊列

int front,rear;//隊頭和隊尾指針變量

bitree*root,*s;//根結(jié)點指針和中間指針變量

root=NULL;//二叉樹置空

front=1;//設(shè)置隊列指針變量初值

rear=0;

//以上為初始化

29

while((ch=getchar())!='#')//輸入一個字符，當(dāng)不是結(jié)束符時執(zhí)行以下操作

{s=NULL;

if(ch!='@')//@表示虛結(jié)點。若不是虛結(jié)點，則建立新結(jié)點

{ s=(bitree*)malloc(sizeof(bitree));

s->data=ch;

s->lchild=NULL;

s->rchild=NULL;

}

rear++;

//隊尾指針增1，指向新結(jié)點地址應(yīng)存放的單元

Q[rear]=s;//將新結(jié)點地址入隊或虛結(jié)點指針NULL入隊30

if(rear==1)

root=s;//輸入的第一個結(jié)點作為根結(jié)點

else

{

if(s&&Q[front])//孩子和雙親結(jié)點都不是虛結(jié)點

if(rear%2==0)

Q[front]->lchild=s;//rear為偶數(shù)，新結(jié)點是左孩子

else

Q[front]->rchild=s;//rear為奇數(shù)且不等于1，新結(jié)點是右孩子

if(rear%2==1)front++;//結(jié)點*Q[front]的兩個孩子處理完畢，出隊

}

}

returnroot;//返回根指針}316.3二叉樹的遍歷所謂樹的遍歷，就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。遍歷的結(jié)果：產(chǎn)生一個關(guān)于結(jié)點的線性序列。二叉樹的遍歷分為深度優(yōu)先和廣度優(yōu)先，深度優(yōu)先又分為遞歸和非遞歸兩種。32（1）深度優(yōu)先遞歸遍歷訪問根結(jié)點,記作D

遍歷根的左子樹,記作L

遍歷根的右子樹,記作R深度優(yōu)先可能的遍歷次序：先序DLR逆先序DRL

中序LDR逆中序RDL

后序LRD逆后序RLD33①先序遍歷DLR先序遍歷算法的遍歷過程若二叉樹非空，執(zhí)行以下操作：訪問根結(jié)點；先序遍歷左子樹；先序遍歷右子樹。voidpreorder(bitree*p)//先序遍歷二叉樹，p指向二叉樹的根結(jié)點{if(p!=NULL)//二叉樹p非空，則執(zhí)行以下操作

{printf(“%c”,p->data);//訪問p所指結(jié)點

preorder(p->lchild);//先序遍歷左子樹

preorder(p->rchild);//先序遍歷右子樹

}}34黑色箭頭表示遞歸調(diào)用，紅色箭頭表示從左子樹遞歸返回，藍(lán)色箭頭表示從右子樹遞歸返回②中序遍歷LDR中序遍歷算法的遍歷過程若二叉樹非空，執(zhí)行以下操作：中序遍歷左子樹；訪問根結(jié)點；中序遍歷右子樹。voidinorder(bitree*p)//先序遍歷二叉樹，p指向二叉樹的根結(jié)點{if(p!=NULL)//二叉樹p非空，則執(zhí)行以下操作

{inorder(p->lchild);//中序遍歷左子樹

printf(“%c”,p->data);//訪問p所指結(jié)點

inorder(p->rchild);//中序遍歷右子樹

}}35③后序遍歷LRD后序遍歷算法的遍歷過程若二叉樹非空，執(zhí)行以下操作：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點。voidpostorder(bitree*p)//后序遍歷二叉樹，p指向二叉樹的根結(jié)點{if(p!=NULL)//二叉樹p非空，則執(zhí)行以下操作

{postorder(p->lchild);//后序遍歷左子樹

postorder(p->rchild);//后序遍歷右子樹

printf(“%c”,p->data);//訪問p所指結(jié)點

}}36（2）深度優(yōu)先非遞歸遍歷中序遍歷：在遍歷左子樹之前，先把根結(jié)點入棧，當(dāng)左子樹遍歷結(jié)束后，根結(jié)點出棧并訪問，再遍歷右子樹。voidinorder(BiTree*T){ SqStack*S; BiTree*p=T; InitStack(S);//順序棧初始化

while(p!=NULL||!Empty(S))

{if(p!=NULL){Push(S,p);//根結(jié)點入棧

p=p->lchild;//遍歷左子樹}

else{Pop(S,p);//左子樹遍歷結(jié)束，出棧

printf(“%c”,p->data);//訪問出棧的結(jié)點

p=p->rchild;//遍歷右子樹} }}37深度優(yōu)先非遞歸遍歷的過程38（3）二叉樹的廣度優(yōu)先遍歷（按層次遍歷二叉樹）從根開始逐層訪問。先遍歷二叉樹的第一層結(jié)點，然后遍歷第二層結(jié)點，……最后遍歷最下層的結(jié)點。而對每一層的遍歷按照從左至右的順序進行?；舅枷耄?/p>

在上層中先被訪問的結(jié)點，它的下層孩子也必然先被訪問，因此在這種遍歷算法的實現(xiàn)時，需要使用一個隊列。在遍歷進行之前先把二叉樹的根結(jié)點的存儲地址入隊，然后依次從隊列中出隊結(jié)點的存儲地址，每出隊一個結(jié)點的存儲地址則對該結(jié)點進行訪問，然后依次將該結(jié)點的左孩子和右孩子的存儲地址入隊，如此反復(fù)，直到隊空為止。39二叉樹的廣度優(yōu)先遍歷算法voidlayer(BiTree*T){BiTree*p;SqQueue*Q;InitQueue(Q);//初始化隊列

if(T!=NULL)

{Q->rear=(Q->rear+1)%MAXSIZE;//修改循環(huán)隊列尾指針

Q->data[Q->rear]=T;//入隊

while(Q->front!=Q->rear)//循環(huán)隊列非空

{Q->front=(Q->front+1)%MAXSIZE;//修改隊頭指針

p=Q->data[Q->front];printf(“%c”,p->data);//出隊，輸出結(jié)點的元素值

if(p->lchild!=NULL)//出隊結(jié)點的左子樹非空

{Q->rear=(Q->rear+1)%MAXSIZE;

Q->data[Q->rear]=p->lchild;//左子樹根結(jié)點入隊

}

if(p->rchild!=NULL)//出隊結(jié)點的右子樹非空

{Q->rear=(Q->rear+1)%MAXSIZE;

Q->data[Q->rear]=p->rchild;//右子樹根結(jié)點入隊

}

}

}}40【例】二叉樹的廣度優(yōu)先遍歷輸出序列為：A,B,C,D,E,F,G41（4）由遍歷序列恢復(fù)二叉樹由DLR和LDR的遍歷序列可以唯一地確定一棵二叉樹；由LRD和LDR的遍歷序列可以唯一地確定一棵二叉樹。通過DLR或者LRD的遍歷序列確定二叉樹或子樹的根結(jié)點；通過LDR確定左、右子樹的序列。42【例】由先序序列{ABHFDECKG}和中序序列{HBDFAEKCG}恢復(fù)二叉樹的過程。43（5）深度優(yōu)先遞歸算法的應(yīng)用①統(tǒng)計二叉樹的葉子結(jié)點數(shù)intcount=0;intcountleaf(bitree*p){ if(p!=NULL){

count=countleaf(p->lchild); //對左子樹上的葉子結(jié)點計數(shù)

if((p->lchild==NULL)&&(p->rchild==NULL))

count=count+1;

count=countleaf(p->rchild);

//對右子樹上的葉子結(jié)點計數(shù)

}

returncount;}請考慮如何統(tǒng)計度為1的結(jié)點個數(shù)，度為2的結(jié)點個數(shù)。44②利用二叉樹后序遍歷計算二叉樹的深度intDepth(BiTree*T){ intdepL,depR; if(T!=NULL)

{ depL=Depth(T->lchild);//計算左子樹的深度

depR=Depth(T->rchild);//計算右子樹的深度

if(depL>=depR)return(depL+1); elsereturn(depR+1);

//二叉樹的深度為左右子樹深度較大者加一（根結(jié)點）

} elsereturn(0);}45③求二叉樹結(jié)點個數(shù)intSize(BiTree*T){if(T==NULL)return(0);

elsereturn(1+Size(T->lchild)+Size(T->rchild));

//二叉樹的結(jié)點個數(shù)是根結(jié)點、左右子樹結(jié)點個數(shù)之和}46④交換左右子樹voidExchange(BiTree*T){ BiTree*S; if(T!=NULL){S=T->lchild; T->lchild=T->rchild; T->rchild=S; Exchange(T->lchild);//在左子樹中交換

Exchange(T->rchild);//在右子樹中交換

}}47⑤利用先序遍歷方法，以廣義表（嵌套括號）的形式輸出二叉樹的層次結(jié)構(gòu)。voidOutBT(BiTree*p){if(p!=NULL){ printf(“%c”,p->data); //輸出根結(jié)點

if(p->lchild!=NULL||p->rchild!=NULL)//根結(jié)點有左子樹或右子樹

{ printf(“(”);

OutBT(p->lchild);//遍歷左子樹

if(p->rchild!=NULL)printf(“,”);

//有右子樹輸出逗號

OutBT(p->rchild);//遍歷右子樹

printf(“)”);

}}}486.4線索二叉樹按照不同的遍歷序列，可以得到先序、中序和后序線索二叉樹。線索二叉樹是將一個非線性結(jié)構(gòu)進行線性化的操作，使每個結(jié)點（除第一個和最后一個）在這些線性序列中有且僅有一個直接前趨和一個直接后繼。線索是指向遍歷序列中的結(jié)點前趨和后繼的指針，若結(jié)點有左孩子，則lchild指示其左孩子，否則lchild指示該結(jié)點的直接前趨結(jié)點；若結(jié)點有右孩子，則rchild指示其右孩子，否則rchild指示該結(jié)點的直接后繼結(jié)點。49線索二叉樹及其線索鏈表的表示50標(biāo)志域ltag、rtag：ltag=0,lchild為左孩子指針ltag=1,lchild為前趨線索指針rtag=0,rchild為右孩子指針rtag=1,rchild為后繼線索指針線索二叉樹的結(jié)點結(jié)構(gòu)類型定義typedef結(jié)點的數(shù)據(jù)域類型datatype;typedefstructBiThrNode{datatypedata；

structBiThrNode*lchild,*rchild;//左、右指針域

intltag,rtag；//左、右標(biāo)志域}BiThrNode；通過算法可以建立二叉樹的先序、中序和后序線索二叉樹。采用線索二叉樹作為二叉樹的存儲結(jié)構(gòu)，可以方便的查找某個結(jié)點在遍歷序列中的前趨和后繼。在先序和中序線索二叉樹中查找后繼結(jié)點比較簡單；在后序和中序線索二叉樹中查找前趨結(jié)點比較簡單。516.5樹和森林（1）樹的存儲結(jié)構(gòu)①雙親表示法樹的雙親表示法是用一組連續(xù)空間（向量）存儲樹的結(jié)點，同時在每個結(jié)點中附設(shè)一個指示器指示其雙親結(jié)點在向量中的位置。雙親表示法可以方便地查找結(jié)點的雙親或祖先，但是查找孩子結(jié)點或子孫時需要遍歷整個樹結(jié)構(gòu)。5253

雙親表示法的結(jié)構(gòu)類型定義#defineMAXSIZE100//

結(jié)點的最大數(shù)目typedefstruct//結(jié)點的結(jié)構(gòu){datatypedata；

intparent；//雙親位置域}PTNode；typedefstruct//樹的結(jié)構(gòu){PTNodenodes[MAXSIZE]；//存儲結(jié)點的向量

intn；//結(jié)點個數(shù)}PTree；54【例】采用雙親表示法存儲樹。55②孩子表示法

把所有結(jié)點以單鏈表形式儲存，同時以每個結(jié)點作為頭結(jié)點，對其孩子結(jié)點另建立一個孩子鏈表。則n個結(jié)點有n個孩子鏈表(葉子的孩子鏈表為空表)。孩子表示法可以方便地查找結(jié)點的孩子或子孫結(jié)點，但是查找雙親或祖先結(jié)點不方便。56

孩子表示法的結(jié)構(gòu)類型定義typedefstructCTNode//孩子結(jié)點{intchild；

structCTNode*next；}*ChildPtr；typedefstruct{datatypedata；

ChildPtrchild；//孩子鏈表頭指針

intparent;//雙親指針，在孩子雙親表示法中定義}CTBox；typedefstruct{CTBoxnodes[MAXSIZE]；

intn；//結(jié)點數(shù)}CTree；57【例】采用孩子表示法存儲樹。58③

孩子兄弟表示法

二叉鏈表中每個結(jié)點有兩個指針域child域和next域，分別指向該結(jié)點的最左邊的孩子結(jié)點和右鄰兄弟結(jié)點。孩子兄弟表示法可以方便地查找結(jié)點的孩子和孩子的兄弟結(jié)點，但是不能查找雙親或祖先結(jié)點。孩子兄弟表示法的結(jié)構(gòu)類型定義typedefstructCSNode{datatypedata；

structCSNode*child，*next；}CSNode，*CSTree；59【例】采用孩子兄弟表示法存儲樹。60（2）樹、森林轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹①樹T中結(jié)點N的第一個子結(jié)點N1在二叉樹T’中是對應(yīng)結(jié)點N的左孩子；②N1的兄弟在T’中被依次鏈接成一串開始于N1的右孩子。樹轉(zhuǎn)換成二叉樹，二叉樹的右子樹一定為空。樹轉(zhuǎn)換成二叉樹，實質(zhì)上就是樹的孩子兄弟表示法。61

森林轉(zhuǎn)換成二叉樹①把每一棵樹依次換換成二叉樹；②合并二叉樹，把第二棵二叉樹作為第一棵二叉樹的右子樹，第三棵二叉樹作為第二棵二叉樹的右子樹，……。即將第2，3，……棵二叉樹串接在第1棵二叉樹的右分支上。62

二叉樹轉(zhuǎn)為樹①將二叉樹T’中結(jié)點x的右孩子，右孩子的右孩子…，都與x的雙親結(jié)點Y用線相連；②去掉原有的雙親到右孩子的連線，得到樹T。63

二叉樹轉(zhuǎn)為森林①從二叉樹的根結(jié)點開始，將右指針斷開，分解二叉樹，使第一棵二叉樹的右子樹為空，不斷重復(fù)著一過程，直到所有二叉樹的右子樹均為空；②將每棵二叉樹分別轉(zhuǎn)換為樹，成為森林。646.6哈夫曼樹及其應(yīng)用（1）最優(yōu)二叉樹（哈夫曼樹）路徑長度

兩個結(jié)點之間的路徑長度是連接兩結(jié)點的路徑上的分支數(shù)。樹的路徑長度是各結(jié)點到根結(jié)點的路徑長度之和。具有不同路徑長度的二叉樹(a)PL=0+1*2+2*4+3=13(b)PL=0+1*2+2*3+3*2=1465

帶權(quán)路徑長度

樹的帶權(quán)路徑長度是樹的各葉子結(jié)點所帶的權(quán)值與該結(jié)點到根的路徑長度的乘積的和。

其中n為樹中葉子結(jié)點的數(shù)目，wi為葉子結(jié)點i的權(quán)值，li為葉子結(jié)點i到根結(jié)點之間的路徑長度。66

葉子結(jié)點的權(quán)值相同，具有不同帶權(quán)路徑長度的二叉樹哈夫曼樹帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹（最優(yōu)二叉樹），例如（c）是哈夫曼樹。在哈夫曼樹中，權(quán)值越大的結(jié)點離根越近。67

哈夫曼樹的不唯一性

權(quán)值為w1,w2,…,wn

的n個葉子結(jié)點構(gòu)成哈夫曼樹，可以有形態(tài)不同的多棵哈夫曼樹。68

完全二叉樹不一定是哈夫曼樹

在葉子數(shù)和權(quán)值相同的二叉樹中，完全二叉樹不一定是哈夫曼樹（最優(yōu)二叉樹）。69（2）哈夫曼樹的構(gòu)造由給定的n個權(quán)值{w0,w1,w2,…,wn-1}，構(gòu)造具有n棵二叉樹的森林F={T0,T1,T2,…,Tn-1}，其中每一棵二叉樹Ti只有一個帶有權(quán)值wi的根結(jié)點，其左、右子樹均為空。重復(fù)以下步驟,直到F中僅剩下一棵二叉樹為止：①在F中選取兩棵根結(jié)點的權(quán)值最小和次最小的二叉樹,分別作為左、右子樹構(gòu)造一棵新的二叉樹。置新的二叉樹根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和。②在F中刪去這兩棵二叉樹。③把新的二叉樹加入F。70

哈夫曼樹的構(gòu)造過程說明：①一個有n個葉子結(jié)點的初始集合，要生成哈夫曼樹共進行n-1次合并，產(chǎn)生n-1個新結(jié)點。②最終求得的哈夫曼樹共有n+n-1=2n-1個結(jié)點，并且哈夫曼樹中沒有度為1的分支結(jié)點。③沒有度為1的結(jié)點的二叉樹又稱為嚴(yán)格二叉樹。71

哈夫曼樹的存儲結(jié)構(gòu)＃definen16//葉子數(shù)目＃definem(2*n-1)//結(jié)點總數(shù)typedefchardatatype;typedefstruct{floatweight;//權(quán)值，設(shè)權(quán)值均大于零

datatypedata;intlchild,rchild,parent;//左、右孩子及雙親指針}hufmtree;hufmtreetree[m];//順序表的每個結(jié)點為一個結(jié)構(gòu)體。

72

哈夫曼樹構(gòu)造算法的基本思想

①對m=2n-1個結(jié)點初始化，將雙親域，左、右孩子域，權(quán)值，結(jié)點值置0②輸入n個葉子結(jié)點的權(quán)值和結(jié)點值③進行n-1次合并，產(chǎn)生n-1個新結(jié)點：在i個結(jié)點中找出兩個雙親域為0（沒有被合并的結(jié)點）且權(quán)值最小的結(jié)點，p1指示權(quán)值最小的結(jié)點，p2指示權(quán)值次最小的結(jié)點；將兩棵根結(jié)點權(quán)值最小的二叉樹進行合并：

tree[p1].parent=i;//i為新結(jié)點，即新產(chǎn)生的雙親結(jié)點

tree[p2].parent=i;tree[i].lchild=p1;//新產(chǎn)生的雙親結(jié)點指向左、右子樹的根結(jié)點

tree[i].rchild=p2;tree[i].weight=tree[p1].weight+tree[p2].weight;//新結(jié)點的權(quán)值是左、右子樹根結(jié)點權(quán)值之和。73

構(gòu)造哈夫曼樹的結(jié)果數(shù)組下標(biāo)lchilddataweightrchildparent00a70610b50520c20430d40442‘0’63551‘0’114660‘0’185-174

哈夫曼樹的構(gòu)造算法voidHUFFMAN(hufmtreetree[]){ inti,j,p1,p2;charch;

floatsmall1,small2,f;

for(i=0;i<m;i++)//對長度為2n-1的順序表初始化

{ree[i].parent=0;tree[i].lchild=0;tree[i].rchild=0;

tree[i].weight=0.0;tree[i].data=‘0’;

}

for(i=0;i<n;i++)//輸入n個葉子結(jié)點的權(quán)值和結(jié)點值

{scanf(“%f”,&f);tree[i].weight=f;scanf(“%c”,&ch);tree[i].data=ch;}75for(i=n;i<m;i++)//進行n-1次合并，產(chǎn)生n-1個新結(jié)點

{p1=p2=0;small1=small2=Maxval;//Maxval為足夠大的值

for(j=0;j<=i-1;j++)

if(tree[j].parent==0)

if(tree[j].weight<small1)

{small2=small1;//改變最小權(quán)，次最小權(quán)及位置

small1=tree[j].weight;p2=p1;p1=j;

}elseif(tree[j].weight<small2)//改變次小權(quán)及位置

{small2=tree[j].weight;p2=j;}

tree[p1].parent=i;tree[p2].parent=i;//合并兩個結(jié)點

tree[i].lchild=p1;tree[i].rchild=p2;tree[i].weight=tree[p1].weight+tree[p2].weight;}

}76（3）哈夫曼樹的應(yīng)用在解決某些判定問題時，利用哈夫曼樹可以得到最佳判定算法，減少比較的次數(shù)。用于通訊和數(shù)據(jù)傳送時的哈夫曼編碼和哈夫曼譯碼，實現(xiàn)數(shù)據(jù)的壓縮。最佳判定算法【例】編制一個將百分制轉(zhuǎn)換成五級制的算法，要求平均比較次數(shù)盡可能少。各分?jǐn)?shù)段分布情況如下：百分制0~5960~6970~7980~8990~100五級制不及格（E）及格

（D）中

（C）良

（B）優(yōu)

（A）比例數(shù)0.050.150.40.30.177哈夫曼樹判定流程10.40.60.30.30.150.150.050.1AEDBCs<80s<70s<90s<60EDCBA78②哈夫曼編碼設(shè)給出一段報文：abaccda

字符集合是{a,b,c,d}，各個字符出現(xiàn)的頻度(次數(shù))是W＝{3,1,2,1}。若給每個字符以等長編碼

a:00b:01c:10d:11

則總編碼為00010010101100

長度為(3+1+2+1)*2=14若按各個字符出現(xiàn)的概率不同而給予不等長編碼，有可能減少總編碼長度。各字符出現(xiàn)的概率為{3/7,1/7,2/7,1/7}，化整為{3,1,2,1}。79

以{3,1,2,1}作為各葉子結(jié)點上的權(quán)值，建立哈夫曼樹。左分支賦0，右分支賦1，得到哈夫曼編碼(不等長編碼)：a:0b

:110c:10d:111電文的編碼：0110010101110（abaccda）電文的總編碼長度：1*3+3*1+2*2+3*1=13。比等長編碼短。

n個葉子結(jié)點的最大編碼長度不會超過n-1。總編碼長度正好等于哈夫曼樹的路徑長度，例如字符a、b、c、d的總編碼長度為9，哈夫曼樹的路徑長度也是9。任一字符的編碼都不是另一字符編碼的前綴，稱為前綴編碼。哈夫曼編碼是一種前綴編碼，譯碼時不會混淆。80哈夫曼編碼的數(shù)據(jù)結(jié)構(gòu)typedefchardatatype;

typedefstruct

{charbits[n];//編碼數(shù)組位串，其中n為葉子結(jié)點數(shù)目

intstart;//編碼在位串的起始位置

datatypedata;//結(jié)點值

}codetype;

codetypecode[n];一個字符的哈夫曼編碼在數(shù)組bits中從高位到低位順序存儲，數(shù)組code存儲n個字符的哈夫曼編碼。81哈夫曼編碼算法的基本思想從葉子到根逆向求哈夫曼編碼從葉子tree[i]出發(fā)，利用雙親地址找到雙親結(jié)點tree[p]，再利用tree[p]的lchild和rchild指針域判斷tree[i]是tree[p]的左孩子還是右孩子，然后決定分配代碼的‘0’還是‘1’,然后以tree[p]為出發(fā)點繼續(xù)向上回溯，直到根結(jié)點為止。82哈夫曼編碼算法voidHUFFMANCode(codetypecode[]，hufmtreetree[])//code存放求出的哈夫曼編碼的數(shù)組，tree已知的哈夫曼樹{inti,c,p;

codetypecd;//緩沖變量

for(i=0;i<n;