第6章 二叉樹和樹

1數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)配套課件2第6章二叉樹和樹

前面的章節(jié)主要討論的是線性結(jié)構(gòu)，二叉樹和樹屬于非線性的結(jié)構(gòu)。遍歷非線性結(jié)構(gòu)比線性結(jié)構(gòu)要麻煩。二叉樹及樹的遍歷技術(shù)是本章各種算法的核心，而且大多是以遞歸的形式表現(xiàn)的，閱讀和編寫遞歸算法是學(xué)習(xí)本章的難點(diǎn)。講授本章課程大約需8課時(shí)。3

樹結(jié)構(gòu)的特點(diǎn)及基本術(shù)語(yǔ)

6.1二叉樹

6.2二叉樹的遍歷

6.3樹和森林

6.4樹的應(yīng)用4樹結(jié)構(gòu)的特點(diǎn)及基本術(shù)語(yǔ)

5線性結(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)6結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支結(jié)點(diǎn)的度:分支的個(gè)數(shù)樹的度:樹中所有結(jié)點(diǎn)的度的最大值葉子結(jié)點(diǎn):度為零的結(jié)點(diǎn)分支結(jié)點(diǎn):度大于零的結(jié)點(diǎn)DHIJM基本術(shù)語(yǔ)7(從根到結(jié)點(diǎn)的)路徑：孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL結(jié)點(diǎn)的層次:假設(shè)根結(jié)點(diǎn)的層次為1,第l

層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹的深度：樹中葉子結(jié)點(diǎn)所在的最大層次層次-深度-高度，86.1二叉樹一、二叉樹的定義和基本術(shù)語(yǔ)二、二叉樹的幾個(gè)基本性質(zhì)三、二叉樹的存儲(chǔ)結(jié)構(gòu)9一、二叉樹的定義和基本術(shù)語(yǔ)

10

二叉樹的定義

二叉樹是n（n≥0）個(gè)元素的有限集，它或?yàn)榭諛?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。根結(jié)點(diǎn)左子樹右子樹ABCDEFGHKLB11二叉樹可以表現(xiàn)出五種基本形態(tài)：空樹N只含根結(jié)點(diǎn)右子樹為空樹NL左子樹為空樹NR左右子樹均不為空樹NLR12

二叉樹的基本操作：

查找類的操作

插入類的操作

刪除類的操作13Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T);InOrderTraverse(T);PostOrderTraverse(T);LevelOrderTraverse(T);查找類的操作：14InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入類的操作：15ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);刪除類的操作：16二、二叉樹的幾個(gè)基本性質(zhì)17

性質(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，命題成立；二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1

。18

性質(zhì)2：

深度為k

的二叉樹上至多含

2k-1

個(gè)結(jié)點(diǎn)（k≥1）。證明：

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

20+21+

+2k-1=2k-1

。19

性質(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。20兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。abcdefghij12345678910111213141521

性質(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。22

性質(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)。23三、二叉樹的存儲(chǔ)結(jié)構(gòu)

二叉樹順序存儲(chǔ)表示二叉樹鏈?zhǔn)酱鎯?chǔ)表示24#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)typedef

TElemTypeSqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;

二叉樹順序存儲(chǔ)表示25例如:

ABDCEF012345678910111213ABCDEF140132626

二叉樹鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表3．線索鏈表27ADEBCFroot結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表lchilddatarchild28typedefstruct

BiTNode

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

TElemTypedata;

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

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

typedefstruct

TriTNode

{

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

TElemTypedata;

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

struct

TriTNode

*parent;//雙親指針

}TriTNode,*TriTree;parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語(yǔ)言的類型描述如下:31（請(qǐng)見后面的線索二叉樹）3．線索鏈表326.2二叉樹遍歷一、問題的提出二、遍歷算法描述三、遍歷算法應(yīng)用舉例四、線索二叉樹33

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

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

每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。35

對(duì)“二叉樹”而言，可以有三條搜索路徑：

1．先上后下的按層次遍歷；

2．先左（子樹）后右（子樹）的遍歷；

3．先右（子樹）后左（子樹）的遍歷。36先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法37若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：ABCDFGEH38若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。中（根）序的遍歷算法：ABCDFGEH39若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。后（根）序的遍歷算法：ABCDFGEH40ABCDEFGHA前序遍歷：ABCDEFGHBDCEGHFB中序遍歷：DAGEHCFD后序遍歷：BGHEFCA二叉樹遍歷的輸出順序示例演示41NULLNULLNULLNULLNULLNULLNULLNULLNULLABCDEFGH先序遍歷：中序遍歷：后序遍歷：ABDBDCEGHFDAGEHCFBGHEFCA二叉樹遍歷過程的示例演示42二、遍歷算法描述

先序（前序）遍歷二叉樹的遞歸算法

中序遍歷二叉樹的遞歸算法

后序遍歷二叉樹的遞歸算法43先序遍歷二叉樹的遞歸算法voidpreorder(BiTreeT){

//

先序遍歷二叉樹

if(T==NULL)exit；

{

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

preorder(T->lchild);//遍歷左子樹

preorder(T->rchild);//遍歷右子樹

}}44void

inorder(BiTreeT）{

//

中序遍歷二叉樹

if(T==NULL)exit；{

inorder(T->lchild);

//遍歷左子樹

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

inorder(T->rchild);//遍歷右子樹

}}中序遍歷二叉樹的遞歸算法45void

postorder(BiTreeT）

{

//

后序遍歷二叉樹

if(T==NULL)

{

postorder(T->lchild);//遍歷左子樹

postorder(T->rchild);//遍歷右子樹

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

}}后序遍歷二叉樹的遞歸算法46三、遍歷算法應(yīng)用舉例1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)

(先序遍歷)2、求二叉樹的深度(后序遍歷)3、復(fù)制二叉樹(后序遍歷)4、建立二叉樹的存儲(chǔ)結(jié)構(gòu)471、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想:

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

}

//if}

//CountLeaf492.求二叉樹的深度(后序遍歷)算法基本思想:

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

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

Depth(BiTreeT

){//返回二叉樹的深度

if

(!T)depthval=0;else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

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

}

return

depthval;}513、復(fù)制二叉樹(后序遍歷)核心操作：生成一個(gè)根結(jié)點(diǎn),并鏈接左右子樹根元素T根元素NEWT遞歸操作：完成左右子樹的復(fù)制52BiTNode*CopyTree(BiTNode*T)

{

if

(!T)returnNULL;

if(T->lchild)

newlptr=CopyTree(T->lchild);//復(fù)制左子樹

elsenewlptr=NULL;

if

(T->rchild)

newrptr=CopyTree(T->rchild);//復(fù)制右子樹

elsenewrptr=NULL;

newT=GetTreeNode(T->data,newlptr,

newrptr);

return

newT;}

//CopyTree53BiTNode*GetTreeNode(TElemTypeitem,BiTNode*lptr,BiTNode*rptr){

if

(!(T=newBiTNode))

exit(1);T->data=item;T->lchild=lptr;T->rchild=rptr;

returnT;}

生成一個(gè)二叉樹的結(jié)點(diǎn)的操作算法：(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr)54ABCDEFGHK^D^C^^H^^K^G^F^E^A例如：下列二叉樹的復(fù)制過程如下：^BnewTT554、建立二叉樹的存儲(chǔ)結(jié)構(gòu)

不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法。以下建立以二叉鏈表表示的存儲(chǔ)結(jié)構(gòu)。從輸入的字符串建立二叉樹由前序和中序的序列建立二叉樹56

以字符串的形式

根

左子樹

右子樹定義一棵二叉樹例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空樹只含一個(gè)根結(jié)點(diǎn)的二叉樹A以字符串“A”表示以下列字符串表示57voidCreateBiTree(BiTree&T){cin>>ch;

if(ch=='')T=NULL;

else{

if

(!(T=newBiTNode))exit(OVERFLOW);T->data=ch;//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹

CreateBiTree(T->rchild);//構(gòu)造右子樹

}}//CreateBiTree58AB

C

D

ABCD上頁(yè)算法執(zhí)行過程舉例如下：ATBCD^^^^^59

僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹

如果同時(shí)已知二叉樹的中序序列“cbdaegf”，則會(huì)如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根60abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列61preinopsps+n-1isis+n-1pre[ps]kps+1k-isps+1+(k-is)k+1n-(k-is)-1子樹序列下標(biāo)位置的確定62void

CrtBT(BiTree&T,charpre[],charino[],

intps,intis,intn){

//已知pre[ps..ps+n-1]為二叉樹的先序序列，//ins[is..is+n-1]為二叉樹的中序序列，//本算法由此兩個(gè)序列構(gòu)造二叉鏈表

if

(n==0)T=NULL;

else{k=Search(ino,pre[ps]);//在中序序列中查詢

if(k==-1)T=NULL;

else{}//遞歸程序段

}}//CrtBT……

63T=newBiTNode;T->data=pre[ps];if(k==is)T->Lchild=NULL;else

CrtBT(T->Lchild,

pre[],ino[],

ps+1,is,k-is

);if(k==is+n-1)T->Rchild=NULL;else

CrtBT(T->Rchild,

pre[],ino[],

ps+1+(k-is),k+1,n-(k-is)-1);遞歸語(yǔ)句程序段：64四、線索二叉樹一、何謂線索二叉樹？二、線索鏈表的遍歷算法三、如何建立線索鏈表？65一、何謂線索二叉樹？

遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列，例如:先序序列:

ABDEGHCFIJ中序序列:

DBGEHACIJF后序序列:

DGHEBJIFCA66

遍歷引起的思考：

遍歷二叉樹把非線性結(jié)構(gòu)以序列的形式加以“線性化”了，那么所得序列信息可否長(zhǎng)期利用？信息保持可否盡量少占用額外的存儲(chǔ)空間？是否能否形成一般化的方法？

處理辦法：

在遍歷時(shí)，串聯(lián)起前驅(qū)、后繼的關(guān)系鏈，以備后期的再利用。67

指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”DBG

E

H

A

CIJF

以中序?yàn)槔?看結(jié)點(diǎn)H的前驅(qū)線索和后繼線索ABCFDGEHIJ的前驅(qū)線索H的后繼線索H68

與其相應(yīng)的二叉樹，稱作“線索二叉樹”

包含“線索”的存儲(chǔ)結(jié)構(gòu)，稱作“線索鏈表”

按“序”來講，可分成：“先序線索二叉樹”、“中序線索二叉樹”和“后序線索二叉樹”69typedefstruct

BiThrNode

{

TElemTypedata;

struct

BiThrNode*lchild,rchild;

struct

BiThrNode*pred,succ;

//前驅(qū)、后繼線索}

BiThrNode,*BiThrTree;線索二叉樹的類型定義：70HABCDEGHFIJT中序線索化二叉樹示例71DBGEHACIJF線索關(guān)系表現(xiàn)為雙向循環(huán)鏈表查找前驅(qū)和后繼變得異常容易72

遍歷帶有線索的二叉樹，既無需重新遞歸遍歷，也無需棧的協(xié)助，只進(jìn)行相當(dāng)“線性結(jié)構(gòu)”的尋訪即可，而且可正反雙向進(jìn)行。二、線索鏈表的遍歷算法:73void

InOrder(BiThrTreeH,void(*visit)(BiTree))

{

//H為指向中序線索鏈表中頭結(jié)點(diǎn)的指針

p=H->succ;

while(p!=H)

{

visit(p);p=p->succ;

}}74三、如何建立線索鏈表？

建立中序線索化的過程，是在中序遍歷的過程中串聯(lián)起前驅(qū)和后繼的線索指針鏈。（線索化過程參照教科書）756.3樹和森林一、樹和森林的定義二、樹和森林的存儲(chǔ)結(jié)構(gòu)三、樹和森林的遍歷76一、樹和森林的定義

77

樹的定義：樹是n（n≥0）個(gè)元素的有限集D，若D為空集，則為空樹。否則：

(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；

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

查找類的操作

插入類的操作

刪除類的操作79Root(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)//遍歷80InitTree(&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棵子樹81

ClearTree(&T)//將樹清空

刪除類的操作：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)

//刪除結(jié)點(diǎn)p的第i棵子樹82ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:83(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。84任何一棵非空樹是一個(gè)二元組

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

F

被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootCGDHIJMFBEFKL85二、樹和森林的存儲(chǔ)結(jié)構(gòu)1.雙親表示法2.孩子鏈表表示法3.樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法86ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6dataparent1.雙親表示法:87

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;

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

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)}PTree;樹結(jié)構(gòu):89r=0n=6data,firstchild0

A

-11

B

02

C

03

D

04

E

25

F

26

G

56451232.孩子鏈表表示法:ABCDEFG90typedefstruct

CTNode{

intchild;

struct

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

childnextC語(yǔ)言的類型描述:91

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

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

datafirstchild92typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

int

n,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置}CTree;樹結(jié)構(gòu):93ABCEDFG

3.樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法ABCDEFGrootABCDEFG94typedefstructCSNode{Elemdata;

structCSNode

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

firstchilddatanextsibling

樹—二叉樹

將一棵樹轉(zhuǎn)換為二叉樹的方法是：

(1)樹中所有相鄰兄弟之間加一條連線。

(2)對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。(刪線）

(3)以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。樹做這樣的轉(zhuǎn)換所構(gòu)成的二叉樹是唯一的。圖

樹到二叉樹的轉(zhuǎn)換圖

樹與二叉樹的對(duì)應(yīng)2.森林轉(zhuǎn)換為二叉樹森林是若干棵樹的集合。樹可以轉(zhuǎn)換為二叉樹，森林同樣也可以轉(zhuǎn)換為二叉樹。因此，森林也可以方便地用孩子兄弟鏈表表示。森林轉(zhuǎn)換為二叉樹的方法如下：（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。（2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。圖

森林轉(zhuǎn)換為二叉樹的過程100

森林和二叉樹的對(duì)應(yīng)關(guān)系設(shè)森林

F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉樹

B=(LBT,Node(root),RBT);101由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若

F=Φ，則

B=Φ；否則，

由

ROOT(T1)

對(duì)應(yīng)得到

Node(root)；

由

(t11,t12,…,t1m)

對(duì)應(yīng)得到

LBT；

由

(T2,T3,…,Tn)

對(duì)應(yīng)得到

RBT。102由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若B=Φ，則F=Φ；否則，由Node(root)

對(duì)應(yīng)得到ROOT(T1

)；由LBT

對(duì)應(yīng)得到(t11,t12,…，t1m)；由RBT

對(duì)應(yīng)得到(T2,T3,…,Tn)。103

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

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

左是孩子，右是兄弟。104

三、樹和森林的遍歷

1.樹的遍歷2.森林的遍歷3.樹的遍歷的應(yīng)用1051.樹的遍歷(可有三條搜索路徑):按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。

若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點(diǎn)。

若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。106ABCDEFGHIJK

先根遍歷時(shí)頂點(diǎn)的訪問次序：ABEFCDGHIJK

后根遍歷時(shí)頂點(diǎn)的訪問次序：EFBCIJKHGDA

層次遍歷時(shí)頂點(diǎn)的訪問次序：ABCDEFGHIJK1072．森林中第一棵樹的子樹森林；1．森林中第一棵樹的根結(jié)點(diǎn)；

BCDEFGHIJK3．森林中其它樹構(gòu)成的森林。森林由三部分構(gòu)成：2.森林的遍歷108

先序遍歷

即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行先根遍歷。

若森林不空，則訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。109中序遍歷

若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷森林中(除第一棵樹之外)其

余樹構(gòu)成的森林。

即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行后根遍歷。110

樹的遍歷和二叉樹遍歷的對(duì)應(yīng)關(guān)系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷111(設(shè)樹的存儲(chǔ)結(jié)構(gòu)為孩子兄弟鏈表)typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

求樹的深度

輸出樹中所有從根到葉子的路徑

建樹的存儲(chǔ)結(jié)構(gòu)3.樹的遍歷的應(yīng)用112intTreeDepth(CSTreeT){

if(!T)return0;

else{h1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);

}}//TreeDepthreturn(max(h1+1,h2));

求樹的深度的算法：113ABCDABCD求樹深算法的理解(max(h1+1,h2))的圖解

114

輸出樹中所有從根到葉子的路徑的算法:例如：對(duì)左圖所示的樹，其輸出結(jié)果應(yīng)為：ABEABFACADGHIADGHJADGHK

ABCDEFGHIJK115void

AllPath(BitreeT,Stack&S)

{

if

(T)

{

Push(S,T->data);if(!T->Lchild&&!T->Rchild)PrintStack(S);else{

AllPath(T->Lchild,S);AllPath(T->Rchild,S);

}

Pop(S);

}//

if(T)}

//AllPath//輸出二叉樹上從根到所有葉子結(jié)點(diǎn)的路徑116ABCDEFGHABA-B-D-FDFGA-B-D-GCEHA-C-E-H輸出二叉樹上從根到所有葉子結(jié)點(diǎn)的路徑演示117ABCDEFGHIJKABEABFACADGHIADGHJADGHK輸出樹中所有從根到葉子的路徑??????如何判定葉子？118void

OutPath(BitreeT,Stack&S){

while(!T){

Push(S,T->data);

if(!T->firstchild)Printstack(s);

else

OutPath(T->firstchild,s);

Pop(S);

T=T->nextsibling;

}

//while}

//OutPath//輸出森林中所有從根到葉的路徑119

建樹的存儲(chǔ)結(jié)構(gòu)的算法:

和二叉樹類似，不同的定義相應(yīng)有不同的算法。

假設(shè)以二元組(F，C)的形式自上而下、自左而右依次輸入樹的各邊，建立樹的孩子-兄弟鏈表。120ABCDEFG例如:對(duì)下列所示樹的輸入序列應(yīng)為:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)

算法中需要一個(gè)隊(duì)列保存已建好的結(jié)點(diǎn)的指針。121voidCreatTree(CSTree&T){T=NULL;

for(scanf(&fa,&ch);ch!=#;

scanf(&fa,&ch);)

{ p=GetTreeNode(ch);//創(chuàng)建結(jié)點(diǎn)

EnQueue(Q,p);//指針入隊(duì)列

if(fa==

#)T=p;//所建為根結(jié)點(diǎn)

else{ }

//非根結(jié)點(diǎn)的情況

}

//for}

//CreateTree

……

122GetHead(Q,s);//取隊(duì)列頭元素(指針值)while(s->data!=fa){

//查詢雙親結(jié)點(diǎn)

DeQueue(Q,s);GetHead(Q,s);}

if(!(s->firstchild))

{s->firstchild=p;r=p;}

//鏈接第一個(gè)孩子結(jié)點(diǎn)else

{r->nextsibling=p;r=p;

}

//鏈接其它孩子結(jié)點(diǎn)

非根結(jié)點(diǎn)的情況的代碼段：123

6.4樹的應(yīng)用

一、堆排序的實(shí)現(xiàn)二、二叉排序樹三、赫夫曼樹及其應(yīng)用124一、堆排序的實(shí)現(xiàn)125堆是滿足下列性質(zhì)的數(shù)列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小頂堆{12,36,27,65,40,14,98,81,73,55,49}不是堆(小頂堆)(大頂堆)復(fù)習(xí)第4章排序126rir2ir2i+1

若將該數(shù)列視作完全二叉樹，則r2i

是ri

的左孩子;r2i+1

是

ri

的右孩子。1236276549817355403498例如:是堆14不127如何“建堆”？?jī)蓚€(gè)問題:如何“篩選”？定義堆類型為:typedef

SqListHeapType;//堆采用順序表表示之HeapAdjust(.,.,.);12812998814973556412362740例如:是大頂堆12但在98

和12

進(jìn)行互換之后，它就不是堆了因此，需要對(duì)它進(jìn)行“篩選”98128173641298比較比較130void

HeapAdjust(RcdType&R[],int

s,int

m){//已知R[s..m]中記錄的關(guān)鍵字除R[s]之外均

//滿足堆的特征，本函數(shù)自上而下調(diào)整R[s]的

//關(guān)鍵字，使R[s..m]也成為一個(gè)大頂堆}//HeapAdjustrc=R[s];//暫存R[s]for

(j=2*s;j<=m;j*=2

){//j初值指向左孩子

自上而下的篩選過程;}R[s]=rc;

//將調(diào)整前的堆頂記錄插入到s位置131if(rc.key>=R[j].key)break;//再作“根”和“子樹根”之間的比較，

//若“>=”成立，則說明已找到rc的插

//入位置s，不需要繼續(xù)往下調(diào)整R[s]=R[j];s=j;

//否則記錄上移，尚需繼續(xù)往下調(diào)整if(j<m

&&R[j].key<R[j+1].key)++j;//左/右“子樹根”之間先進(jìn)行相互比較

//令j指示關(guān)鍵字較大記錄的位置自上而下的篩選過程的代碼段：132

建堆是一個(gè)從下往上進(jìn)行“篩選”的反復(fù)過程40554973816436122798例如:排序之前的關(guān)鍵字序列為123681734998817355

現(xiàn)在，左/右子樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹是個(gè)“堆”即可。98494064361227133voidHeapSort(HeapType&H){

//對(duì)順序表H進(jìn)行堆排序。}

//HeapSortfor

(i=H.length/2;i>0;--i)

//建大頂堆

HeapAdjust(H.r,i,H.length);

for(i=H.length;i>1;--i)

{//調(diào)整堆來實(shí)現(xiàn)排序

H.r[1]←→H.r[i];

//將堆頂記錄和當(dāng)前未經(jīng)排序子序列

//H.r[1..i]中最后一個(gè)記錄相互交換

HeapAdjust(H.r,1,i-1);

//對(duì)H.r[1]進(jìn)行篩選

}13412345678910405549731227988164363612738181559849557340984049

堆排序的邏輯結(jié)構(gòu)是一棵完全二叉樹，而實(shí)現(xiàn)的空間則是順序表。以數(shù)據(jù)模型演示數(shù)據(jù)在順序空間的動(dòng)態(tài)變化。初始堆的建立過程：初始堆的建立過程有比較大的消耗，可達(dá)4n135堆排序第一趟：1234567891098814973362740556412129881127312641281堆排序第二趟：123456789108173496436274055121298128112731264125573堆排序第三趟：1234567891073644955362740128112988173121264125564可以看出，每趟的調(diào)整只牽涉少量的數(shù)據(jù)……

有序段136堆排序的時(shí)間復(fù)雜度分析(建堆+

n-1

次調(diào)整)：

以后的每次調(diào)整，耗費(fèi)將顯著減少。因?yàn)檫@樣調(diào)整所耗用的比較操作次數(shù)都不超過堆的樹深，是一種消耗很少的局部調(diào)整。

初始堆的建立過程:O(n)

建成深度為

h=(log2n+1)的堆,需要調(diào)整n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過

2*(log2(n-1)+log2(n-2)+

…+log22)<2n(log2n)

因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)137二、二叉排序樹

138（1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；1．二叉排序的定義：

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉排序樹。（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；139503080209010854035252388例如:是二叉排序樹。66不140（49，38，65，76，49，13，27，52）4938657649132752構(gòu)造二叉排序樹

構(gòu)建二叉排序樹的過程，是一個(gè)從空樹起不斷插入結(jié)點(diǎn)的過程。每插入一個(gè)結(jié)點(diǎn)都應(yīng)保證遵從二叉排序樹的定義。141（，，，，，，，）1327384949526576（49，38，65，76，49，13，27，52）原始序列數(shù)據(jù)4938657649132752構(gòu)造的二叉排序樹中序遍歷二叉排序樹

如果中序遍歷二叉排序樹，所得序列將是有序的，即實(shí)現(xiàn)了對(duì)原始數(shù)據(jù)的排序，二叉排序樹即由此得名。142

有關(guān)二叉排序樹更詳細(xì)的討論及算法，請(qǐng)見第8章查找表的二叉查找樹一節(jié)143三、赫夫曼樹及其應(yīng)用

（哈夫曼樹）最優(yōu)樹的定義如何構(gòu)造最優(yōu)樹前綴編碼壓縮的本質(zhì)就是--赫夫曼樹abaabaabadbcaabcabadababa計(jì)算機(jī)內(nèi)部：ASCII碼，定長(zhǎng)編碼；8bit-一個(gè)字節(jié)，共256個(gè)字符；（漢字-雙字節(jié)表示一個(gè)漢字，共6萬字符，康熙字典多于這個(gè)；）25*8=200bit,144哈夫曼編碼：非定長(zhǎng)編碼原則：根據(jù)如字符出現(xiàn)頻率高，則其編碼越短。在軍事情報(bào)中，根據(jù)截留的代碼，分析每串字符出現(xiàn)的頻率，分析可能是代表什么文字？慢慢湊成一句話，就能找出每個(gè)字的代碼是什么。因?yàn)檎f話的頻率難以更改：比如我，的之類的。145

abaabaabadbcaabcabadababa等長(zhǎng)編碼：總共才四個(gè)字符，等長(zhǎng)編碼：都用兩個(gè)bit表示，2*25=50bit用哈夫曼樹可以更省空間跟時(shí)間計(jì)數(shù)：統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)a：13次---0；b：8次---10；c:2次----110，d：2次----111；13*1+8*2+2*3+2*3=45bit在軍事上，就可能取得時(shí)間上的勝利。146如何獲得不等長(zhǎng)的編碼-建立哈夫曼樹來進(jìn)行編碼---二叉樹的應(yīng)用哈夫曼編碼的實(shí)質(zhì)就是為了壓縮，那如何譯碼呢？147問題：如何獲得哈夫曼編碼-----如何解出實(shí)際內(nèi)容（字符）：譯碼哈夫曼法--哈夫曼樹-輸入一串字符，計(jì)算每個(gè)字符出現(xiàn)頻率--哈夫曼樹（最優(yōu)二叉樹）-哈夫曼編碼-實(shí)現(xiàn)壓縮（輸出編碼序列）編碼過程-哈夫曼樹（解壓縮）輸出字符序列：譯碼過程什么是哈夫曼樹----最優(yōu)二叉樹？148149

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

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

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

從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑上

分支的數(shù)目。150

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

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

含n個(gè)葉子結(jié)點(diǎn)、每個(gè)葉子結(jié)點(diǎn)帶權(quán)為w，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的二叉樹，稱為“最優(yōu)二叉樹”或者哈夫曼樹PL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954152

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

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

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

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

重復(fù)(2)

和(3)

兩步，直至F中只含一棵樹為止。(3)(4)1559例如:已知權(quán)值W={

5,6,2,9,7

}5627527697671395271566713952795271667132900001111000110110111157

指的是，任何一個(gè)字符的編碼都不是同一字符集中另一個(gè)字符的編碼的前綴。前綴編碼

利用赫夫曼樹可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。158出現(xiàn)頻度:5,6,2,9,7編碼:

101,00,100,11,01字母集:

s,t,a,e,i電文:eat編碼:eat111000025701100101911160167130100012901tiase譯電文:eat

符合前綴編碼規(guī)則才能按唯一性進(jìn)行譯碼問題：如何獲得哈夫曼編碼-----如何解出實(shí)際內(nèi)容（字符）：譯碼哈夫曼法--哈夫曼樹-輸入一串字符，計(jì)算每個(gè)字符出現(xiàn)頻率--哈夫曼樹（最優(yōu)二叉樹）-哈夫曼編碼-實(shí)現(xiàn)壓縮（輸出編碼序列）編碼過程-哈夫曼樹（解壓縮）輸出字符序列：譯碼過程什么是哈夫曼樹----最優(yōu)二叉樹？159哈夫曼算法：就是找到最優(yōu)二叉樹，就是構(gòu)造最優(yōu)二叉樹的過程，WPL總和最小。哈夫曼算法：輸入：n個(gè)帶權(quán)值的字符---將其看成H[]數(shù)組輸出：最優(yōu)二叉樹就是哈夫曼樹。160算法流程（步驟）：1、從H[]中選擇兩個(gè)權(quán)值最小的字符x,y;2、利用x，y構(gòu)建一棵二叉樹Z,權(quán)值為xw+yw；3、將新產(chǎn)生的二叉樹Z,加入到集合中，同時(shí)將x，y刪除；4、不斷重復(fù)1、2、3，直到H[]中只剩下一個(gè)元素為止。161哈夫曼樹----哈夫曼編碼？規(guī)則：1、沿著哈樹分支，左邊為0，右邊為1；2、每個(gè)葉子結(jié)點(diǎn)的路徑：從根—該葉子結(jié)點(diǎn)所形成的01代碼串---就為該葉子結(jié)點(diǎn)對(duì)應(yīng)字符編碼。162壓縮---編碼字符----01串解壓縮—譯碼01串—字符1、從哈樹的根開始，遇0走左分支，遇1走右分支，直至葉子結(jié)點(diǎn)----輸出相應(yīng)字符；2、不斷重復(fù)1，直到01串結(jié)束。163難點(diǎn)：哈夫曼樹的構(gòu)造

采用技巧：用數(shù)組表示二叉樹。Typedefstructleafnode{intweight;權(quán)值intleft;intright;intparent;}HNODEHNODEH[];

}164Parent，left，right表示該結(jié)點(diǎn)父結(jié)點(diǎn)，孩子結(jié)點(diǎn)的下標(biāo)Parent,left,right=-1,表示無父結(jié)點(diǎn)，無左右孩子準(zhǔn)備：建立H[]數(shù)組表示葉子結(jié)點(diǎn)，其父結(jié)點(diǎn)、左右孩子均為-1；weight，data值求哈夫曼樹函數(shù)Huffman（HNODEH[],intn）（n為葉子結(jié)點(diǎn)數(shù)）165Huffman（HNODEH[],intn）Count=n；While(count>1){If(H[].parent=-1)Selecttwomin(H,n,&index1,&index2);//找當(dāng)前數(shù)組中權(quán)值最小的兩個(gè)數(shù),其下標(biāo)用Index1，index2表示Index=creatBiTree(H,n,index1,index2)//兩結(jié)點(diǎn)建立二叉樹，新生成的結(jié)點(diǎn)為indexDelecttwomin（H，n，index1，index2；）Count--;}166Index=creatBiTree(H,n,index1,index2){H[n]為新結(jié)點(diǎn)，H[0—n-1]為放原葉子結(jié)點(diǎn)值H[n].left=index1;H[n].right=index2;H[n].parent=-1;H[n].weight=H[index1].weight+H[index2].weightH[index1].parent=n;H[index2].parent=n;}技巧：當(dāng)parent==-1，表示已經(jīng)用過該結(jié)點(diǎn)。167作業(yè)：編碼：輸入：一串英文txt（都為小寫，不考慮空格）輸出：該txt的01壓縮串（編碼）譯碼：輸入：01串輸出：該01串表示的字符串（解壓縮譯碼）168輸入：一串英文txt（都為小寫，不考慮空格）---1、計(jì)數(shù)（求權(quán)值weight）2、建立哈樹（數(shù)組H[]）3、哈編碼：txt的編碼（01串）4、譯碼169輸入：一串英文txt（都為小寫，不考慮空格）1、計(jì)數(shù)—求權(quán)值：每個(gè)字母出現(xiàn)的頻率.intA[26];//放每個(gè)字符出現(xiàn)的次數(shù)chardoc[];//英文txtinti=1;

while(i<n){A[doc[i]-’a’]++;i++;}//后兩條語(yǔ)句可用A[doc[i++]-’a’]++;A[doc[i]-’a’]++;//-’a’得到該字符在A[]中的下標(biāo)位置，對(duì)其++運(yùn)算，等于累計(jì)該字符在txt中出現(xiàn)的次數(shù)，也就是它的weight。1702、建立哈樹（H[]）:哈夫曼算法計(jì)數(shù)后，得到每個(gè)字母的權(quán)值weight，就可以求得哈夫曼樹---將此樹用H[]數(shù)組表示。(程序見前面)1713、哈編碼：txt的編碼（01串）輸出每個(gè)葉子結(jié)點(diǎn)（每個(gè)字母）的編碼。算法思路：1、從哈樹根開始，沿著哈樹分支，左分支為0，右分支為1；2、每個(gè)葉子結(jié)點(diǎn)的編碼：從根—>該葉子結(jié)點(diǎn)所形成的01代碼串---就為該葉子結(jié)點(diǎn)對(duì)應(yīng)字符編碼。172Outputcode(H,n){

for(i=1;i<n;i++){1、Index=found(H,n)//找到每個(gè)葉子結(jié)點(diǎn)H[i].left=H[i].right=-12、沿著H[index].parent不斷往上尋找，判斷該index是其父親的左孩子還是右孩子，如為左則將0，右則將1壓入棧中。3、,重復(fù)2，直到找到根，然后將代碼出棧，就得到該葉子結(jié)點(diǎn)代表的字符的編碼。}1734、譯碼輸入一串01串----輸出字符串算法思想：1、從根開始走，看到1就走右分支，看0就走左分支，直到走到葉子結(jié)點(diǎn)為止（left=right=-1），輸出該葉子結(jié)點(diǎn)對(duì)應(yīng)的字符。2、重復(fù)1，直到01串結(jié)束174遷移：1、可實(shí)現(xiàn)壓縮圖像圖像RGB表示，分別用8位（一個(gè)字節(jié)）表示，如R用256個(gè)字符表示。判斷每個(gè)256個(gè)字符出現(xiàn)的概率---哈夫曼樹（數(shù)組）---每個(gè)字符的編碼---壓縮2、中文txt3、視頻壓縮175176本章學(xué)習(xí)要點(diǎn)177

1.熟練掌握二叉樹的結(jié)構(gòu)特性，了解相應(yīng)性質(zhì)的證明方法。

2.熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍。

3.遍歷二叉樹是二叉樹各種操作的基礎(chǔ)。實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。掌握各種遍歷策略的遞歸算法，靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進(jìn)行的遍歷。178

4.理解二叉樹線索化的實(shí)質(zhì)是建立結(jié)點(diǎn)與其在相應(yīng)序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟悉二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對(duì)二叉樹進(jìn)行遍歷，而線索二叉樹上的線索又為相應(yīng)的遍歷提供了方便。179

5.熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng)掌握1至2種建立二叉樹和樹的存儲(chǔ)結(jié)構(gòu)的方法。

6.學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。

7.