第六章樹(shù)和二叉樹(shù)

紅樓夢(mèng)賈家家譜6.1樹(shù)的類(lèi)型定義6.2二叉樹(shù)6.3

遍歷二叉樹(shù)和線索二叉樹(shù)6.4樹(shù)和森林6.6哈夫曼樹(shù)及其應(yīng)用第6章樹(shù)和二叉樹(shù)6.1樹(shù)的類(lèi)型定義數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱(chēng)為空樹(shù)。否則:(1)在D中存在唯一的稱(chēng)為根的數(shù)據(jù)元素root；

(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹(shù)，稱(chēng)為根root的子樹(shù)。

數(shù)據(jù)關(guān)系R：ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹(shù)根例如:樹(shù)形圖表示的例子ABKELFDHMJICG嵌套集合表示法ABCDEKLFGHIJM凹入表示法（A(B(E(K,L),F),C(G),D(H(M),I,J)))廣義表表示法ABCDEFGHIJMKL對(duì)比樹(shù)型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素

(無(wú)前驅(qū))

根結(jié)點(diǎn)

(無(wú)前驅(qū))最后一個(gè)數(shù)據(jù)元素

(無(wú)后繼)多個(gè)葉子結(jié)點(diǎn)

(無(wú)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)基本術(shù)語(yǔ)結(jié)點(diǎn):結(jié)點(diǎn)的度:樹(shù)的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):一個(gè)數(shù)據(jù)元素+若干指向子樹(shù)的分支分支的個(gè)數(shù)樹(shù)中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM(從根到結(jié)點(diǎn)的)路徑：孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)結(jié)點(diǎn)的層次:樹(shù)的深度：

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l層的結(jié)點(diǎn)的子樹(shù)根結(jié)點(diǎn)的層次為l+1樹(shù)中葉子結(jié)點(diǎn)所在的最大層次(１)有確定的根；(２)樹(shù)根和子樹(shù)根之間為有向關(guān)系。有向樹(shù)：有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系。無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系。任何一棵非空樹(shù)是一個(gè)二元組

Tree=（root，F(xiàn)）其中：root被稱(chēng)為根結(jié)點(diǎn)

F被稱(chēng)為子樹(shù)森林森林：是m（m≥0）棵互不相交的樹(shù)的集合ArootBCDEFGHIJMKLF6.2

二叉樹(shù)的類(lèi)型定義

二叉樹(shù)或?yàn)榭諛?shù)，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱(chēng)為左子樹(shù)和右子樹(shù)的、互不交的二叉樹(shù)組成。ABCDEFGHK根結(jié)點(diǎn)左子樹(shù)右子樹(shù)二叉樹(shù)的五種基本形態(tài)：N空樹(shù)只含根結(jié)點(diǎn)NNNLRR右子樹(shù)為空樹(shù)L左子樹(shù)為空樹(shù)左右子樹(shù)均不為空樹(shù)二叉樹(shù)

的重要特性

性質(zhì)1：

在二叉樹(shù)的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)用歸納法證明：

i=1

層時(shí)，只有一個(gè)根結(jié)點(diǎn)：

2i-1=20=1；二叉樹(shù)中第5層上的結(jié)點(diǎn)個(gè)數(shù)最多為_(kāi)___A.8 B.15

C.16 D.32性質(zhì)2：

深度為k的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)（k≥1）。證明：

基于上一條性質(zhì)，深度為k的二叉樹(shù)上的結(jié)點(diǎn)數(shù)至多為

20+21+

+2k-1=2k-1

。深度為5的二叉樹(shù)至多有（

）結(jié)點(diǎn)。A．64 B．32C．31 D．63

性質(zhì)3：

對(duì)任何一棵二叉樹(shù)，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為

2

的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹(shù)上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹(shù)上分支總數(shù)b=n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。度為1的結(jié)點(diǎn)1、一棵二叉樹(shù)有67個(gè)結(jié)點(diǎn),這些結(jié)點(diǎn)的度要么是0，要么是2。這棵二叉樹(shù)中度數(shù)為2的結(jié)點(diǎn)有

個(gè)。兩類(lèi)特殊的二叉樹(shù)：滿(mǎn)二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)：樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿(mǎn)二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij

性質(zhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為

log2n+1。證明：設(shè)完全二叉樹(shù)的深度為k則根據(jù)第二條性質(zhì)得2k-1-1<n≤2k

-1計(jì)算得出：2k-1≤n<2k即

k-1≤log2n<k

因?yàn)閗只能是整數(shù)，因此，k=log2n

+1。性質(zhì)5：若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)行1

至n

的編號(hào)，則對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為i

的結(jié)點(diǎn)：

(1)若i=1，則該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親，否則，編號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；

(2)若2i>n，則該結(jié)點(diǎn)無(wú)左孩子，

否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，

否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。1.將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下，從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為_(kāi)_____。A.98 B.99C.50 D.486.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹(shù)的順序存儲(chǔ)表示例如:ABCDEF

ABDCEF

0123456789101112131401326一、二叉樹(shù)的順序存儲(chǔ)表示二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表ADEBCFrootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表typedefstruct

BiTNode

{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述如下:ADEBCFroot2．三叉鏈表parent

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):

typedefstruct

TriTNode

{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指針

structTriTNode

*parent;//雙親指針

}TriTNode,*TriTree;parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述如下:6.4二叉樹(shù)的遍歷

順著某一條搜索路徑巡訪二叉樹(shù)中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。一、問(wèn)題的提出“訪問(wèn)”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。

“遍歷”是任何類(lèi)型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，不需要另加討論。而二叉樹(shù)是非線性結(jié)構(gòu)。

二叉樹(shù)每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問(wèn)題。二、按層次遍歷二叉樹(shù)

實(shí)現(xiàn)方法為從上層到下層，每層中從左側(cè)到右側(cè)依次訪問(wèn)每個(gè)結(jié)點(diǎn)。下面我們將給出一棵二叉樹(shù)及其按層次順序訪問(wèn)其中每個(gè)結(jié)點(diǎn)的遍歷序列。按層次遍歷該二叉樹(shù)的序列為：

ABECFDGHKABCDEFGHK三、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法

若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。先（根）序的遍歷算法：四、算法的遞歸描述voidPreorder(BiTreeT,void(*visit)(TElemType&e)){//

先序遍歷二叉樹(shù)

if(T){

visit(T->data);//訪問(wèn)結(jié)點(diǎn)

Preorder(T->lchild,visit);//遍歷左子樹(shù)

Preorder(T->rchild,visit);//遍歷右子樹(shù)

}}ABCDEFGD

L

RTD

L

RD

L

RABED

L

RD

L

RDLRDLRCFDG先序遍歷結(jié)果:ABCDEFGT

若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。中（根）序的遍歷算法：voidInorder(BiTreeT,

void(*visit)(TElemType&e)){//

中序遍歷二叉樹(shù)

if(T){

Inreorder(T->lchild,visit);//遍歷左子樹(shù)

visit(T->data);//訪問(wèn)結(jié)點(diǎn)

Inreorder(T->rchild,visit);//遍歷右子樹(shù)

}}ABCDEFGL

D

RTL

D

RL

D

RABEL

D

RLD

RLDRLDRCFDG中序遍歷結(jié)果:BDCAGFET

若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。后（根）序的遍歷算法：voidPostorder(BiTreeT,

void(*visit)(TElemType&e)){//

后序遍歷二叉樹(shù)

if(T){

Postreorder(T->lchild,visit);//遍歷左子樹(shù)

Postreorder(T->rchild,visit);//遍歷右子樹(shù)

visit(T->data);//訪問(wèn)結(jié)點(diǎn)

}}ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA練習(xí)：設(shè)二叉樹(shù)結(jié)點(diǎn)的先序序列為ABDECFGH，中序序列為DEBAFCHG,則二叉樹(shù)的后序序列是

。

五、中序遍歷算法的非遞歸描述

中序遍歷示意圖圖中序遍歷二叉樹(shù)的非遞歸算法處理流程

算法思想為：從二叉樹(shù)根結(jié)點(diǎn)開(kāi)始，沿左子樹(shù)一直走到末端(左孩子為空)為止，在走的過(guò)程中，把依次遇到的結(jié)點(diǎn)進(jìn)棧,待左子樹(shù)為空時(shí),從棧中退出結(jié)點(diǎn)并訪問(wèn),然后再轉(zhuǎn)向它的右子樹(shù)。如此重復(fù)，直到?？栈蛑羔槥榭罩埂BCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問(wèn)：C(4)中序遍歷非遞歸算法pABCDEFGiP->A訪問(wèn)：CB(5)ABCDEFGiP->AP->D訪問(wèn)：CBp(6)ABCDEFGiP->AP->DP->E訪問(wèn)：CBp(7)ABCDEFGiP->AP->D訪問(wèn)：CBEp(8)ABCDEFGiP->AP->DP->G訪問(wèn)：CBEP=NULL(9)ABCDEFGiP->A訪問(wèn)：CBEGDp(11)ABCDEFGiP->AP->F訪問(wèn)：CBEGDp(12)ABCDEFGiP->AP->D訪問(wèn)：CBEGp(10)ABCDEFGiP->A訪問(wèn)：CBEGDFp=NULL(13)ABCDEFGi訪問(wèn)：CBEGDFAp(14)ABCDEFGi訪問(wèn)：CBEGDFAp=NULL(15)算法一：StatusInorderTraverse(BitreeT,Status(*Visit)(TElemTypee)){

InitStack(S);Push(S,T);//根指針進(jìn)棧

while(!StackEmpty(S)){

while(GetTop(S,p)&&p)Push(S,p->lchild);

//向左走到盡頭

Pop(S,p);

//空指針退棧

if(!StackEmpty(S)){//訪問(wèn)結(jié)點(diǎn)，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR; Push(S,p->rchild); }}returnOK;}StatusInorderTraverse(BitreeT,Status(*Visit)(TElemTypee)){

InitStack(S);p=T;while(p||!StackEmpty(S)){

if(p){Push(S,p);p=p->lchild;}

//根指針進(jìn)棧，遍歷左子樹(shù)

else{//根指針退棧，訪問(wèn)根結(jié)點(diǎn)

Pop(S,p);if(!Visit(p->data))returnERROR; p=p->rchild; }}returnOK;}算法二：六、遍歷算法的應(yīng)用舉例2、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)(先序遍歷)3、求二叉樹(shù)的深度(后序遍歷)1、輸入結(jié)點(diǎn)值，構(gòu)造二叉樹(shù)(先序遍歷）1、輸入結(jié)點(diǎn)值，構(gòu)造二叉樹(shù)算法基本思想:

先序(或中序或后序)遍歷二叉樹(shù)，讀入一個(gè)字符，若讀入字符為空，則二叉樹(shù)為空,若讀入字符非空，則生成一個(gè)結(jié)點(diǎn)。將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為：生成一個(gè)結(jié)點(diǎn)，輸入結(jié)點(diǎn)的值。VoidCreateBiTree

(BiTree*T){charch;scanf(“%c”&ch);if(ch＝＝’’)

（*T）=NULL;

else{if(!(（*T）=(BiTNode*)malloc(sizeof(BiTNode)))

exit(0);

（*T）->data=ch;//生成根結(jié)點(diǎn)

CreateBiTree(&（*T）->lchild);//構(gòu)造左子樹(shù)

CreateBiTree(&（*T）>rchild);//構(gòu)造右子樹(shù)

}}//CreateBiTree2、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想:

先序(或中序或后序)遍歷二叉樹(shù)，在遍歷過(guò)程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問(wèn)結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增1。void

CountLeaf

(BiTreeT,int&count){

if(T){

if

((!T->lchild)&&

(!T->rchild))count++;//對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);

}}

3、求二叉樹(shù)的深度(后序遍歷)算法基本思想:

從二叉樹(shù)深度的定義可知，二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加1。由此，需先分別求得左、右子樹(shù)的深度，算法中“訪問(wèn)結(jié)點(diǎn)”的操作為：求得左、右子樹(shù)深度的最大值，然后加1。

首先分析二叉樹(shù)的深度和它的左、右子樹(shù)深度之間的關(guān)系。int

Depth(BiTreeT){//返回二叉樹(shù)的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}6.3.2線索二叉樹(shù)

何謂線索二叉樹(shù)？線索鏈表的遍歷算法如何建立線索鏈表？一、何謂線索二叉樹(shù)？遍歷二叉樹(shù)的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱(chēng)作“線索”與其相應(yīng)的二叉樹(shù)，稱(chēng)作“線索二叉樹(shù)”包含“線索”的存儲(chǔ)結(jié)構(gòu)，稱(chēng)作“線索鏈表”ABCDEFGHK^D^

C^^B

E^線索鏈表的結(jié)點(diǎn)結(jié)構(gòu)

ltag和rtag是增加的兩個(gè)標(biāo)志域，用來(lái)區(qū)分結(jié)點(diǎn)的左、右指針域是指向其左、右孩子的指針，還是指向其前驅(qū)或后繼的線索。

lchildLTagdataRTagrchild例如：ABCDEABDCET中序序列：BCAED中序線索二叉樹(shù)00001111^11^ABCDE0A01B00D11C11E1T中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹(shù)

0

1頭結(jié)點(diǎn)：ltag=0,lchild指向根結(jié)點(diǎn)rtag=1,rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的lchild域和最后一個(gè)結(jié)點(diǎn)的rchild域都指向頭結(jié)點(diǎn)ABDCET中序序列：BCAED中序線索二叉樹(shù)00001111^11^二、線索鏈表的遍歷算法:由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。例如:

對(duì)中序線索化鏈表的遍歷算法

※中序遍歷的第一個(gè)結(jié)點(diǎn)？

※在中序線索化鏈表中結(jié)點(diǎn)的后繼？左子樹(shù)上處于“最左下”（沒(méi)有左子樹(shù)）的結(jié)點(diǎn)。若無(wú)右子樹(shù)，則為后繼線索所指結(jié)點(diǎn)；否則為對(duì)其右子樹(shù)進(jìn)行中序遍歷時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)。voidInOrderTraverse_Thr(BiThrTreeT,

void(*Visit)(TElemTypee))

{p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T){//空樹(shù)或遍歷結(jié)束時(shí)，p==T

while(p->LTag==Link)p=p->lchild;//先找到中序遍歷起點(diǎn)

if(!Visit(p->data))returnERROR;//訪問(wèn)其左子樹(shù)為空的結(jié)點(diǎn)

while(p->RTag==Thread&&p->rchild!=T)

{p=p->rchild;Visit(p->data);}//訪問(wèn)后繼結(jié)點(diǎn)

p=p->rchild;//當(dāng)前結(jié)點(diǎn)右域不空或已經(jīng)找好了后繼，則一律從結(jié)點(diǎn)的右子樹(shù)開(kāi)始重復(fù){}的全部過(guò)程

}}//InOrderTraverse_Thr

在中序遍歷過(guò)程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問(wèn)結(jié)點(diǎn)的前驅(qū)”和“后繼”信息。遍歷過(guò)程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問(wèn)的、指針p所指結(jié)點(diǎn)的前驅(qū)。三、如何建立線索鏈表？線索二叉樹(shù)的生成算法目的：在依某種順序遍歷二叉樹(shù)時(shí)修改空指針，添加前驅(qū)或后繼。注解：為方便添加結(jié)點(diǎn)的前驅(qū)或后繼，需要設(shè)置兩個(gè)指針：

p指針→當(dāng)前結(jié)點(diǎn)之指針；pre指針→前驅(qū)結(jié)點(diǎn)之指針。技巧：當(dāng)結(jié)點(diǎn)p的左/右域?yàn)榭諘r(shí)，只改寫(xiě)它的左域（裝入前驅(qū)pre），而其右域（后繼）留給下一結(jié)點(diǎn)來(lái)填寫(xiě)?；蛘哒f(shuō)，當(dāng)前結(jié)點(diǎn)的指針p應(yīng)當(dāng)送到前驅(qū)結(jié)點(diǎn)的空右域中。若p->lchild＝NULL,則{p->Ltag=1;p->lchild＝pre;}//p的前驅(qū)結(jié)點(diǎn)指針pre存入左空域若pre->rchild＝NULL,則{pre->Rtag＝1;pre->rchild=p;}//p存入其前驅(qū)結(jié)點(diǎn)pre的右空域void

InThreading(BiThrTreep)

{

if(p){//對(duì)以p為根的非空二叉樹(shù)進(jìn)行線索化

InThreading(p->lchild);

//左子樹(shù)線索化

if(!p->lchild)//建前驅(qū)線索

{p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=p;}

pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);

//右子樹(shù)線索化

}//if}//InThreadingStatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//構(gòu)建中序線索鏈表

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))

exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;//建頭結(jié)點(diǎn)

Thrt->rchild=Thrt;//右指針回指

if(!T)

Thrt->lchild=Thrt;

//若二叉樹(shù)空，則左指針回指else{Thrt->lchild=T;

pre=Thrt;InThreading(T);//中序遍歷進(jìn)行中序線索化

pre->rchild=Thrt;pre->RTag=Thread;

//最后一個(gè)結(jié)點(diǎn)線索化

Thrt->rchild=pre;

}

returnOK;}//InOrderThreading

6.4樹(shù)和森林樹(shù)的三種存儲(chǔ)結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹(shù)的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent一、雙親表示法:

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類(lèi)型描述:typedefstruct{PTNodenodes[MAX_TREE_SIZE];

int

r,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹(shù)結(jié)構(gòu):ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4r=0n=7dataparentfirstchild123456二、孩子鏈表表示法:-1000224typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextC語(yǔ)言的類(lèi)型描述:

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)

datafirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}CTree;樹(shù)結(jié)構(gòu):三、樹(shù)的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法ABCDEFGABCEDFGrootABCEDFG

typedefstructCSNode{Elemdata;

struct

CSNode*firstchild,*nextsibling;}CSNode,*CSTree;C語(yǔ)言的類(lèi)型描述:結(jié)點(diǎn)結(jié)構(gòu):

firstchilddatanextsibling樹(shù)與二叉樹(shù)轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù)A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對(duì)應(yīng)存儲(chǔ)存儲(chǔ)解釋解釋將樹(shù)轉(zhuǎn)換成二叉樹(shù)加線：在兄弟之間加一連線抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹(shù)的根結(jié)點(diǎn)為軸心，將整樹(shù)順時(shí)針轉(zhuǎn)45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空樹(shù)根結(jié)點(diǎn)X的第一個(gè)孩子結(jié)點(diǎn)X緊鄰的右兄弟二叉樹(shù)根結(jié)點(diǎn)X的左孩子結(jié)點(diǎn)X的右孩子樹(shù)與二叉樹(shù)的轉(zhuǎn)換將二叉樹(shù)轉(zhuǎn)換成樹(shù)加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林轉(zhuǎn)換成二叉樹(shù)將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)將每棵樹(shù)的根結(jié)點(diǎn)用線相連以第一棵樹(shù)根結(jié)點(diǎn)為二叉樹(shù)的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹(shù)型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹(shù)轉(zhuǎn)換成森林抹線：將二叉樹(shù)中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù)還原：將孤立的二叉樹(shù)還原成樹(shù)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ

由此，樹(shù)的各種操作均可對(duì)應(yīng)二叉樹(shù)的操作來(lái)完成。

應(yīng)當(dāng)注意的是，和樹(shù)對(duì)應(yīng)的二叉樹(shù)，其左、右子樹(shù)的概念已改變?yōu)椋?/p>

左是孩子，右是兄弟。6.6哈夫曼樹(shù)與

哈夫曼編碼

最優(yōu)樹(shù)(哈夫曼樹(shù))的定義

如何構(gòu)造最優(yōu)樹(shù)

前綴編碼哈夫曼編碼

一、最優(yōu)樹(shù)的定義樹(shù)的路徑長(zhǎng)度定義為：

樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。

結(jié)點(diǎn)的路徑長(zhǎng)度定義為：

從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。

樹(shù)的帶權(quán)路徑長(zhǎng)度定義為：

樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和

WPL(T)=wklk(對(duì)所有葉子結(jié)點(diǎn))。

在所有含n個(gè)葉子結(jié)點(diǎn)、并帶相同權(quán)值的m叉樹(shù)中，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的樹(shù)，稱(chēng)為“最優(yōu)樹(shù)”。例如：WPL(T)=72+52+22+42=36WPL(T)=71+52+23+43=35WPL(T)=73+53+42+21=46

根據(jù)給定的n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造n棵二叉樹(shù)的集合

F={T1,T2,…,Tn}，其中每棵二叉樹(shù)Ti中均只含一個(gè)帶權(quán)值為wi的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；二、如何構(gòu)造最優(yōu)樹(shù)(1)(哈夫曼算法)以二叉樹(shù)為例：

在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹(shù)，分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；(2)

從F中刪去這兩棵樹(shù)，同時(shí)加入剛生成的新樹(shù)；

重復(fù)

(2)

和

(3)

兩步，直至F中只含一棵樹(shù)為止。這棵樹(shù)便是哈夫曼樹(shù)(3)(4)9例如:已知權(quán)值W={5,6,2,9,7}562752769767139527952716671329注意：

①n個(gè)葉子的哈夫曼樹(shù)要經(jīng)過(guò)n-1次合并，產(chǎn)生n-1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹(shù)中共有2n-1個(gè)結(jié)點(diǎn)。

②哈夫曼樹(shù)是嚴(yán)格的二叉樹(shù)，沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)。前綴編碼

在電文傳輸中，需要將電文中出現(xiàn)的每個(gè)字符進(jìn)行二進(jìn)制編碼。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則：（1）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有唯一性，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣；（2）發(fā)送的二進(jìn)制編碼盡可能地短。下面我們介紹兩種編碼的方式。

1.等長(zhǎng)編碼

這種編碼方式的特點(diǎn):

每個(gè)字符的編碼長(zhǎng)度相同。設(shè)字符集只含有4個(gè)字符A，B，C，D，用兩位二進(jìn)制表示的編碼分別為00，01，10，11。若現(xiàn)在電文為：ABACCDA，則應(yīng)發(fā)送二進(jìn)制序列：00010010101100，總長(zhǎng)度為14位。當(dāng)接收方接收到這段電文后，將按兩位一段進(jìn)行譯碼。這種編碼的特點(diǎn):譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是最短的。2.不等長(zhǎng)編碼

在傳送電文時(shí)，為了使其二進(jìn)制位數(shù)盡可能地少，可以將每個(gè)字符的編碼設(shè)計(jì)為不等長(zhǎng)的，使用頻度較高的字符分配一個(gè)相對(duì)比較短的編碼，使用頻度較低的字符分配一個(gè)比較長(zhǎng)的編碼。例如，可以為A，B，C，D四個(gè)字符分別分配0，00，1，01，并可將上述電文用二進(jìn)制序列：000011010發(fā)送，其長(zhǎng)度只有9個(gè)二進(jìn)制位。問(wèn)題：接收方接到這段電文后無(wú)法進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前面4個(gè)0是4個(gè)A，1個(gè)B、2個(gè)A，還是2個(gè)B，即譯碼不唯一，因此這種編碼方法不可使用。CDBA111000A:0B:10C:110D:111電文為：ABACCDA發(fā)送二進(jìn)制序列：01001101101110

利用哈夫曼樹(shù)可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。稱(chēng)為哈夫曼編碼哈夫曼編碼（1）利用字符集中每個(gè)字符的使用頻率作為權(quán)值構(gòu)造一個(gè)哈夫曼樹(shù)；（2）從根結(jié)點(diǎn)開(kāi)始，為到每個(gè)葉子結(jié)點(diǎn)路徑上的左分支賦予0，右分支賦予1，并從根到葉子方向形成該葉子結(jié)點(diǎn)的編碼。哈夫曼編碼的構(gòu)造方法：例如：

假設(shè)有一個(gè)電文字符集中有8個(gè)字符，每個(gè)字符的使用頻率分別為{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，現(xiàn)以此為例設(shè)計(jì)哈夫曼編碼。為方便計(jì)算，將所有字符的頻度乘以100，使其轉(zhuǎn)換成整型數(shù)值集合，得到{5,29,7,8,14,23,3,11}；哈夫曼編碼設(shè)計(jì)如下圖：115297814233100011558290001118421900011100010011001111110111111010Weightparentlchildrchild12345678910111213141552978142331101234567W529870000000000000000000000000000000000000000000001423311999178101034151111128191414121313151552942581002101161412130HC0cd01234567123456780011↑start00111111111111111000000001求哈夫曼編碼過(guò)程的實(shí)例:HT數(shù)組哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)

用一個(gè)大小為2n-1的一維數(shù)組來(lái)存儲(chǔ)哈夫曼樹(shù)中的結(jié)點(diǎn)，其存儲(chǔ)結(jié)構(gòu)為：

typedefstruct{

//結(jié)點(diǎn)類(lèi)型

intweight；

//權(quán)值，不妨設(shè)權(quán)值均大于零

intlchild，rchild，parent；

//左右孩子及雙親指針

}HTNode，*HuffmanTree;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)Typedefchar**Huffmancode;//動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表哈夫曼編碼的存儲(chǔ)結(jié)構(gòu)

if(n<=1)return;

m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號(hào)單元未用

求哈夫曼編碼的算法:for(p=HT+1,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0}

for(;i<=m;++i,++p)

*p={0,0,0,0}

for(i=n+1