數(shù)據(jù)結(jié)構(gòu)課件

第六章樹和二叉樹定義：樹(Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集T，T為空時(shí)稱為空樹，否則它滿足如下兩個(gè)條件：（1）有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；（2）其余的結(jié)點(diǎn)可分為m(m>=0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集又是一棵樹，并稱其為子樹(Subtree)。6.1樹的定義和基本術(shù)語.樹定義T1T2T3ACBGFEHIJDMKLA.ADTTree{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹；

若D僅含有一個(gè)數(shù)據(jù)元素，則R為空集，否則R={H}，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；（2）若D-{root}

,則存在D-{root}的一個(gè)劃分D1，D2…Dm（m>0）,對(duì)任意j

k(1

j,k

m)有DJ

DK=

,且對(duì)任意的i(1

i

m),存在唯一數(shù)據(jù)元素xi

Di,<root,xi>

H;（3）對(duì)應(yīng)于D-{root}的劃分，H-{<root,x1>,…<root,xm>}有唯一的一個(gè)劃分H1,H2,…Hm(m>0),對(duì)任意j

k(1

j,k

m)有Hj

Hk=

,且對(duì)任意i(1

i

m)，Hi是Di上的二元關(guān)系，（Di，{Hi}）是一棵符合本定義的樹，稱為根root的子樹。

基本操作P：}ADTTree.

基本操作：查找插入刪除.

Root(T)//求樹的根結(jié)點(diǎn)查找類：Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷.InitTree(&T)//初始化置空樹插入類：CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結(jié)點(diǎn)p的第i棵子樹.

ClearTree(&T)//將樹清空刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹.樹的其它表示方式凹入表示嵌套集合廣義表.基本術(shù)語1.結(jié)點(diǎn)

指樹中的一個(gè)數(shù)據(jù)元素，一般用一個(gè)字母表示。

2.度

一個(gè)結(jié)點(diǎn)包含子樹的數(shù)目，稱為該結(jié)點(diǎn)的度。

3.樹葉（葉子）

度為0的結(jié)點(diǎn)，稱為葉子結(jié)點(diǎn)或樹葉，也叫終端結(jié)點(diǎn)。

4.孩子結(jié)點(diǎn)

若結(jié)點(diǎn)X有子樹，則子樹的根結(jié)點(diǎn)為X的孩子結(jié)點(diǎn)，也稱為孩子，兒子，子女等。如圖6-1（c）中A的孩子為B，C，D。

5.雙親結(jié)點(diǎn)

若結(jié)點(diǎn)X有子女Y，則X為Y的雙親結(jié)點(diǎn)。.6.祖先結(jié)點(diǎn)

從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)過分支上的所有結(jié)點(diǎn)為該結(jié)點(diǎn)的祖先。

7.子孫結(jié)點(diǎn)

某一結(jié)點(diǎn)的子女及子女的子女都為該結(jié)點(diǎn)子孫。

8.兄弟結(jié)點(diǎn)

具有同一個(gè)雙親的結(jié)點(diǎn)，稱為兄弟結(jié)點(diǎn)。

9.分支結(jié)點(diǎn)

除葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn)，為分枝結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)。

10．層數(shù)

根結(jié)點(diǎn)的層數(shù)為1，其它結(jié)點(diǎn)的層數(shù)為從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)過的分支數(shù)目再加1。

.11.樹的高度（深度）

樹中結(jié)點(diǎn)所處的最大層數(shù)稱為樹的高度，如空樹的高度為0，只有一個(gè)根結(jié)點(diǎn)的樹高度1。

12.樹的度

樹中結(jié)點(diǎn)度的最大值稱為樹的度。

13.有序樹

若一棵樹中所有子樹從左到右的排序是有順序的，不能顛倒次序。稱該樹為有序樹。

14.無序樹

若一棵樹中所有子樹的次序無關(guān)緊要，則稱為無序樹。

15．森林（樹林）

若干棵互不相交的樹組成的集合為森林。一棵樹可以看成是一個(gè)特殊的森林。.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無前驅(qū))

根結(jié)點(diǎn)(無前驅(qū))最后一個(gè)數(shù)據(jù)元素(無后繼)多個(gè)葉子結(jié)點(diǎn)(無后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)對(duì)比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn).二叉樹或?yàn)榭諛?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹6.2二叉樹6.2.1二叉樹的定義.二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹.二叉樹的抽象數(shù)據(jù)類型ADTBinaryTree{

數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D=

，則R=

，稱二叉樹為空二叉樹；若D

，則R={H}，H是如下二元關(guān)系：（1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；（2）若D-{root}

,則存在D-{root}={D1,Dr},且

D1

Dr

；（3）若D1

，則D1中存在唯一的元素x1,<root,x1>

H,且存在D1上的關(guān)系H1

H；若Dr

,則Dr中存在唯一的元素xr,<root,xr>

H,且存在Dr上的關(guān)系Hr

H；H={<root,x1>,<root,xr>,H1,Hr};（4）（D1，{H1}）是一棵符合本定義的二叉樹，稱為根的左子樹，（Dr，{Hr}）是一棵符合本定義的二叉樹，稱為根的右子樹?；静僮鳎簘ADTBinaryTree.性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

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

2i-1=20=1；假設(shè)對(duì)j，1<=j<i，命題成立2j-1

；證明j=i時(shí)命題也成立，由歸納假設(shè)，第i-1層至多有2i-2個(gè)結(jié)點(diǎn)，二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，故第i層時(shí)結(jié)點(diǎn)數(shù)最多=2i-2

2=2i-1

。6.2.2二叉樹的性質(zhì).性質(zhì)2：

深度為k的二叉樹上至多含2k-1個(gè)結(jié)點(diǎn)（k≥1）。證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為

20+21++2k-1=2k-1。.

性質(zhì)3：

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

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

而b=n-1=n0+n1+n2-1由此，n0=n2+1。.兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij.

性質(zhì)4：具有n

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

log2n

+1

。證明：設(shè)完全二叉樹的深度為k

則根據(jù)第二條性質(zhì)得2k-1≤n<2k即k-1≤log2n<k

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

+1。.性質(zhì)5：若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：

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

i/2

的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；

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

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

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

否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。.示意圖2i2i+1i2i+22i+3i+1

i/2

j層j+1層2j-12j2j+1.示意圖2i+22i+3i+12i2i+1i......2i2i+1i2i+22i+3i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1)….6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹的順序存儲(chǔ)表示.一、二叉樹的順序存儲(chǔ)結(jié)構(gòu)整個(gè)二叉樹可以按照從上到下，從左到右的順序排序，做標(biāo)號(hào)；對(duì)于滿/完全二叉樹，可以從根結(jié)點(diǎn)開始按序號(hào)存放對(duì)于一般的二叉樹，可以參照滿二叉樹的編碼方法進(jìn)行編碼，位置空的結(jié)點(diǎn)空置。.#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;二叉樹的順序存儲(chǔ)表示.1234567891018910452673完全二叉樹.ABCDEF

ABDCEF

0123456789101112131401326.ABC非完全二叉樹ABC????AB????C.二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表3．線索鏈表…….ADEBCF

rootlchilddatarchild1.二叉鏈表datalchildrchild.typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:.2．三叉鏈表A∧∧∧BCDEF∧∧∧∧∧lchilddatarchildparentdatalchildrchildparent.

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

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

structTriTNode

*parent;//雙親指針

}TriTNode,*TriTree;lchilddataparentrchild結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:.假如以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點(diǎn)和遍歷右子樹，遍歷整個(gè)二叉樹則有：DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。6.3遍歷二叉樹和線索二叉樹6.3.1遍歷二叉樹.前序遍歷二叉樹中序遍歷二叉樹后序遍歷二叉樹訪問根結(jié)點(diǎn)；前序遍歷左子樹；前序遍歷右子樹；中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹；后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)；.遍歷圖例ACFEDB中序序列為：前序序列為：后序序列為：DBEACFABDECFDEBFCA.二叉樹表達(dá)式(a+b*(c-d)-e/f)遍歷此二叉樹其先序序列為：-+a*b-cd/ef

按中序遍歷,其中序序列為：a+b*c-d-e/f按后序遍歷,其后序序列為：abcd-*+ef/-－＋*a/b-dcfe.圖例ab*c-ba*-cab*c-－×abcacb×--*abca*b-cab*c-.先（根）序的遍歷算法的遞歸描述voidPreorderTraverse(BiTreeT,status(*visit)(TElemType&e)){

//先序遍歷二叉樹

if(T){

if(Visit(T->data))

if(PreOrderTraverse(T->lchild，Visit))

if(PreOrderTraverse(T->rchild，Visit))

returnOK;

returnERROR；

}elsereturnOK；}p129.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)){//訪問結(jié)點(diǎn)，向右

Pop(S，p)；

if(!Visit(p->data))returnERROR；

Push(S，p->rchild)；

}

}//While

returnOK；

}

p130acb×-.StatusInOrderTraverse(BiTreeT，Status(*Visit)(TElemTypee)){

InitStack(S)；

p=T；

while(p||!StackEmpty(S)){

if(p){

Push(S，p)；

p=p->lchild；

}

else{

Pop(S，p)；

if(!Visit(p->data))returnERROR；

p=p->rchild；

}//else

}//While

returnOK；

}P131了解.StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);

T->data=ch;//生成根結(jié)點(diǎn)CreateBiTree(T->lchild);//構(gòu)造左子樹CreateBiTree(T->rchild);//構(gòu)造右子樹}returnOK;}//CreateBiTree建立二叉樹p131.‘’A‘’‘’ABC‘’‘’‘’DE‘’‘’‘’.6.3.2線索二叉樹

n個(gè)結(jié)點(diǎn)的二叉鏈表中含有n+1個(gè)空指針域，可以利用這些空指針域來存放某結(jié)點(diǎn)的前驅(qū)和后繼的信息。這些附加的指針稱為“線索”，加上了線索的二叉鏈表稱為線索鏈表，加上線索的二叉樹就是線索二叉樹（ThreadedBinaryTree）。將二叉樹變?yōu)榫€索二叉樹的過程稱為線索化。

lchildltagdata

rtagrchildltag=

rtag=

?íì指向結(jié)點(diǎn)前驅(qū)指向結(jié)點(diǎn)的左孩子lchildlchild:1:0?íì指向結(jié)點(diǎn)后繼指向結(jié)點(diǎn)的右孩子rchildrchild:1:0.中序線索二叉樹NULLACFEDBNULLA00E11C01D11F11B00NULLNULL.類型定義typedefstructBinhrNode{TelemTypedata;structBinhrNode*lchild,*rchild;

左、右孩子指針intltag,rtag;

}BinhrNode，

*BinhrTree

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

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

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

P=T–>lchild;while(p!=T){

while(p–>LTag==Link)p=p–>lchild;

if(!visit(p–>data))returnerror;while(p–>RTag==Thread&&p

–>rchild!=T){p=p–>rchild;Visit(p–>data);}p=p–>rchild;}

returnOK;}P134.在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前驅(qū)。如何建立線索鏈表？.StatusInorderThreading(BiThrTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt–>LTag=Link;Thrt–>RTag=Thread;Thrt–>rchild=Thrt;if(!T)Thrt–>lchild=Thrt;else{Thrt–>lchild=T;pre=Thrt;

InThrTreading(T);pre–>rchild=Thrt;pre–>RTag=Thread;Thrt–>rchild=pre;}returnOK;}//InorderThreadingP134.VoidInThreading(BiThrTreep){if(p){InThreading(p–>lchild);

if(!p–>lchild){p–>LTag=Thread;p–>lchild=pre;}if(!pre–>rchild){pre–>rchild){pre–>RTag=Thread;pre–>rchild=p;}pre=p;InThreading(p–>rchild);}}P135.6.6樹和森林樹的三種存儲(chǔ)結(jié)構(gòu)一、雙親表示法二、孩子表示法三、樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法.ABCDEFG0

A

-11

B

02

C

03

D

04

E

2

5

F

26

G

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

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述:.typedefstruct{

PTNodenodes[MAX_TREE_SIZE];intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)}PTree;樹結(jié)構(gòu):.二、孩子表示法①②.③.typedefstructCTNode{intchild;structCTNode*next;}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextC語言的類型描述:.

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

datafirstchild樹結(jié)構(gòu):typedefstruct{

CTBoxnodes[MAX_TREE_SIZE];intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置}CTree;.ABCDEFG0A

1B

2C

3D

4E

5F

6G

r=0n=7datafirstchild123456-1000225.ABCDEFGABCEDFGrootABCEDFG

三、孩子-兄弟表示法(樹的二叉鏈表表示法).typedefstructCSNode{Elemdata;

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

firstchilddatanextsibling.6.4.2森林和二叉樹的轉(zhuǎn)換.若樹采用孩子兄弟表示法，二叉樹采用二叉鏈表表示，則從存儲(chǔ)結(jié)構(gòu)上看，結(jié)點(diǎn)定義完全相同。因此，在使用該存儲(chǔ)結(jié)構(gòu)下，樹可以轉(zhuǎn)化為二叉樹。樹和二叉樹轉(zhuǎn)化步驟（1）連線：在所有的兄弟結(jié)點(diǎn)之間加一條連線。（2）切線：對(duì)于每個(gè)結(jié)點(diǎn)，除了保留與其最左孩子的連線外，去掉該結(jié)點(diǎn)與其它孩子之間的連線。（3）旋轉(zhuǎn)：將按（1）、（2）的方法形成的二叉樹，沿順時(shí)針方向旋轉(zhuǎn)450,就可以得到一棵形式上更為清楚的二叉樹。

.

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

左是孩子，右是兄弟。.樹和二叉樹轉(zhuǎn)化例FGHABCEDFGHABCEDFGHABCEDFHABGCED.森林到二叉樹的轉(zhuǎn)換若樹采用孩子兄弟表示法，二叉樹采用二叉鏈表表示，則：任一棵樹，都可以找到唯一的一棵二叉樹和它對(duì)應(yīng)，而且該二叉樹沒有右子樹(因此一棵二叉樹，不一定保證能轉(zhuǎn)換為一棵樹)若把森林中的第二棵樹的根結(jié)點(diǎn)，看成是第一棵樹的根結(jié)點(diǎn)的兄弟結(jié)點(diǎn)，則這兩棵樹可以轉(zhuǎn)換為一棵二叉樹。依次類推，可以認(rèn)為森林和二叉樹是一一對(duì)應(yīng)的，從而得到二叉樹和森林的轉(zhuǎn)換規(guī)則.轉(zhuǎn)換示例ABCDFGHIEABCDFGHIECABDFGHIE.二叉樹到森林的轉(zhuǎn)換例IABDFGHKCEJIABDJHCEFGK.6.4.3樹和森林的遍歷一、樹的遍歷二、森林的遍歷.樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。.ABCDEFGHIJK先根遍歷時(shí)頂點(diǎn)的訪問次序：ABEFCDGHIJK后根遍歷時(shí)頂點(diǎn)的訪問次序：EFBCIJKHGDA層次遍歷時(shí)頂點(diǎn)的訪問次序：ABCDEFGHIJK.

BCDEFGHIJK1．森林中第一棵樹的根結(jié)點(diǎn)；2．森林中第一棵樹的子樹森林；3．森林中其它樹構(gòu)成的森林。森林由三部分構(gòu)成：.1.先序遍歷森林的遍歷若森林不空，則訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行先根遍歷。.２．中序遍歷若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。.6.6哈夫曼樹及其應(yīng)用

最優(yōu)樹的定義

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

前綴編碼

.

一、最優(yōu)樹的定義樹的路徑長(zhǎng)度定義為：樹中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。

結(jié)點(diǎn)的路徑長(zhǎng)度定義為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上分支的數(shù)目。.結(jié)點(diǎn)的帶權(quán)的路徑長(zhǎng)度：該結(jié)點(diǎn)到根結(jié)點(diǎn)之間的路程長(zhǎng)度與該結(jié)點(diǎn)上權(quán)的乘積樹的帶權(quán)路徑長(zhǎng)度定義為：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和

WPL(T)=

wklk(對(duì)所有葉子結(jié)點(diǎn))。由n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)構(gòu)成的二叉樹中，WPL最小的二叉樹稱為最優(yōu)二叉樹，或Huffman樹.27975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954.if(a<60)b=“bad”;elseif(a<70)b=“pass”;elseif(a<80)b=“general”;else…分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.101*0.05+2*0.15+3*0.4+4*0.3+4*0.1=3.1510000個(gè)數(shù)據(jù)需比較31500次.分?jǐn)?shù)0-5960-6970-7980-8990-100比例數(shù)0.050.150.400.300.102*0.1+2*0.3+2*0.4+3*0.15+3*0.05=2.2.例如:已知權(quán)值W={5,6,2,9,7}9562752769767139527二、如何構(gòu)造最優(yōu)樹.67139527952716671329.dcba9653ba96358a9614358962314538abcdcbd哈夫曼樹.三、哈夫曼編碼

數(shù)據(jù)通訊中，經(jīng)常采用0、1序列來表示不同的字符。在發(fā)送端需要將待發(fā)送的字符轉(zhuǎn)化成二進(jìn)制的0、1序列（編碼），在接受端又要把接受的0、1序列轉(zhuǎn)化成對(duì)應(yīng)的字符序列（譯碼）。字符串：“ABACCDA”,每個(gè)字符采用2比特表示，共14比特；考慮到出現(xiàn)頻率，A：’0’,C：’1’,B：’00’,D：’01’，則編碼為：“000011010”，共9比特。譯碼有困難：“0000”有多種譯法：ABA,AAAA,BB,BAA…….指的是，任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。前綴編碼利用赫夫曼樹可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。.ACBDEF160000111364125736912G0112801A：100B：11C：001D：1011E：1010F：000G：011、利用二叉樹編碼得到的是二進(jìn)制前綴編碼？2、得到電文總長(zhǎng)最短？.哈夫曼編碼

設(shè)有n種字符，在一個(gè)電文中，第i種字符出現(xiàn)的次數(shù)為Wi,編碼長(zhǎng)度為li，使L最小，可以看作是已知n個(gè)結(jié)點(diǎn)的權(quán)wi，求一棵Huffman樹的問