樹(shù)和二叉樹(shù)概念

6.樹(shù)和二叉樹(shù)16.1樹(shù)的定義和基本概念6.2二叉樹(shù)

6.2.1樹(shù)的定義和基本術(shù)語(yǔ)

6.2.2二叉樹(shù)的性質(zhì)

6.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.3遍歷二叉樹(shù)

6.3.1遍歷二叉樹(shù)

6.3.2線索二叉樹(shù)2

6.4樹(shù)和森林

6.4.1樹(shù)的存儲(chǔ)結(jié)構(gòu)

6.4.2森林與二叉樹(shù)的轉(zhuǎn)換

6.4.3樹(shù)和森林的遍歷6.6赫夫曼樹(shù)及其應(yīng)用

6.6.1最優(yōu)二叉樹(shù)（赫夫曼樹(shù)）

6.6.2赫夫曼編碼36.1樹(shù)的定義和基本術(shù)語(yǔ)4樹(shù)的邏輯定義

樹(shù)(Tree)：是包括n(n>=0)個(gè)結(jié)點(diǎn)的有限集T。當(dāng)T非空時(shí)，滿足：（1）有且僅有一個(gè)特別標(biāo)出的稱為根的結(jié)點(diǎn)；（2）除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)可分為m（m>=0）個(gè)互不相交非空的有限集T1,T2,…,Tm,其中每一個(gè)集合本身又是一棵樹(shù)，稱為根的子樹(shù)(Subtree)。

ABCDEFIJGH5

樹(shù)結(jié)構(gòu)的特點(diǎn)：（1）樹(shù)的根的結(jié)點(diǎn)沒(méi)前驅(qū)結(jié)點(diǎn)，除了根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)都有且只有一個(gè)前驅(qū)結(jié)點(diǎn)；（2）樹(shù)的結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)。樹(shù)結(jié)構(gòu)描述的是層次關(guān)系。ABCDEFIJGH6A只有根結(jié)點(diǎn)的樹(shù)ABCDEFGHIJKLM有子樹(shù)的樹(shù)根子樹(shù)7數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。

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

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

數(shù)據(jù)關(guān)系R：樹(shù)的定義8

基本操作：查找類Root(T)//求樹(shù)的根結(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)的最左孩子

TreeEmpty(T)//判定樹(shù)是否為空樹(shù)

TreeDepth(T)//求樹(shù)的深度TraverseTree(T,Visit())//遍歷RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟9InitTree(&T)//初始化置空樹(shù)

CreateTree(&T,definition)//按定義構(gòu)造樹(shù)Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹(shù)插入為結(jié)點(diǎn)p的第i棵子樹(shù)

插入類刪除類

ClearTree(&T)//將樹(shù)清空

DestroyTree(&T)//銷(xiāo)毀樹(shù)的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹(shù)10ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹(shù)根例如:11(１)有確定的根；(２)樹(shù)根和子樹(shù)根之間為有向關(guān)系。有向樹(shù)：有序樹(shù)：子樹(shù)之間存在確定的次序關(guān)系。無(wú)序樹(shù)：子樹(shù)之間不存在確定的次序關(guān)系。12~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(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è)后繼)13

2、基本術(shù)語(yǔ)結(jié)點(diǎn)(node)——表示樹(shù)中的元素，包括數(shù)據(jù)項(xiàng)及若干指向其子樹(shù)的分支結(jié)點(diǎn)的度(degree)——結(jié)點(diǎn)擁有的子樹(shù)數(shù)葉子(leaf)——度為0的結(jié)點(diǎn)分支結(jié)點(diǎn)——度不為0的結(jié)點(diǎn)樹(shù)的度——一棵樹(shù)中各結(jié)點(diǎn)的度的最大值孩子(child)——結(jié)點(diǎn)子樹(shù)的根稱為該結(jié)點(diǎn)的孩子雙親(parents)——孩子結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的~兄弟(sibling)——同一雙親的孩子14祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的所有結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)的層次(level)——從根結(jié)點(diǎn)算起，根為第一層，它的孩子為第二層……堂兄弟：雙親在同一層的結(jié)點(diǎn)互為堂兄弟深度(depth)——樹(shù)中結(jié)點(diǎn)的最大層次數(shù)有序樹(shù)：如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)左右次序不能互換，則該樹(shù)為有序樹(shù)無(wú)序樹(shù)：如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)左右次序能互換，則該樹(shù)為無(wú)序樹(shù)森林(forest)——m(m

0)棵互不相交的樹(shù)的集合15ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹(shù)的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹(shù)的深度：4結(jié)點(diǎn)F，G為堂兄弟結(jié)點(diǎn)F的祖先是結(jié)點(diǎn)B，A結(jié)點(diǎn)D的子孫是H,I,J,M166.2二叉樹(shù)176.2.1二叉樹(shù)的定義

定義：二叉樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，它或?yàn)榭諛?shù)(n=0)，或由一個(gè)根結(jié)點(diǎn)和兩棵分別稱為左子樹(shù)和右子樹(shù)的互不相交的二叉樹(shù)構(gòu)成.

特點(diǎn):每個(gè)結(jié)點(diǎn)至多有二棵子樹(shù)(即不存在度大于2的結(jié)點(diǎn));二叉樹(shù)的子樹(shù)有左、右之分，且其次序不能任意顛倒.18二叉樹(shù)的定義b)僅有根結(jié)點(diǎn)的二叉樹(shù)a)空二叉樹(shù)c)右子樹(shù)為空的二叉樹(shù)d)左、右子樹(shù)均非空的二叉樹(shù)e)左子樹(shù)為空的二叉樹(shù)19

性質(zhì)1：

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

2=2i-1

。6.2.2二叉樹(shù)的性質(zhì)20性質(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

。21

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

性質(zhì)4：

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

log2n

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

即

k-1≤log2n<k因?yàn)閗只能是整數(shù)，因此，

k=log2n

+1。25性質(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)。266.2.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)1、順序存儲(chǔ)結(jié)構(gòu)按滿二叉樹(shù)的結(jié)點(diǎn)按層編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素.結(jié)點(diǎn)在這個(gè)序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系：

#defineMax_Tree_Size100Typedef

TElemType

SqBiTree[Max_Tree_Size];SqBiTree

bt;

缺點(diǎn)是有可能對(duì)存儲(chǔ)空間造成極大的浪費(fèi)，在最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的右單支樹(shù)確需要2k-1個(gè)結(jié)點(diǎn)存儲(chǔ)空間。27abcdefghijkl

123456789101112abcdefghijkl完全二叉樹(shù)28ABCDEFG?????表示該處沒(méi)有元素存在僅僅為了好理解ABCDE????FG一般二叉樹(shù)292、二叉鏈表法

lchilddatarchild二叉鏈表存儲(chǔ)表示Typedef

struct

BiTNode{

TelemTypedata;

struct

BiTNode*lchild,*rchild;}BiTNode,*BiTree;30ABCDEFGAB

CD

E

F

G^^^^^^^^313、三叉鏈表lchilddatarchildparent三叉鏈表存儲(chǔ)表示Typedef

struct

BiTNode{

TelemTypedata;

struct

BiTNode*lchild,*rchild,*perent;}BiTNode,*BiTree;32ABCDEFGABCDEF

G^^^^^^^^^336.3遍歷二叉樹(shù)和線索二叉樹(shù)

346.3.1遍歷二叉樹(shù)在二叉樹(shù)的一些應(yīng)用中，常常要求在樹(shù)中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)樹(shù)中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。這就引入了遍歷二叉樹(shù)的問(wèn)題，即如何按某條搜索路徑巡訪樹(shù)中的每一個(gè)結(jié)點(diǎn)，使得每一個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。遍歷對(duì)線性結(jié)構(gòu)是容易解決的，而二叉樹(shù)是非線性的，因而需要尋找一種規(guī)律，以便使二叉樹(shù)上的結(jié)點(diǎn)能排列在一個(gè)線性隊(duì)列上，從而便于遍歷。35

假如以L、D、R分別表示遍歷左子樹(shù)、遍歷根結(jié)點(diǎn)和遍歷右子樹(shù)，遍歷整個(gè)二叉樹(shù)則有DLR、LDR、LRD、DRL、RDL、RLD六種遍歷方案。若規(guī)定先左后右，則只有前三種情況，分別規(guī)定為：

DLR——先（根）序遍歷，

LDR——中（根）序遍歷，

LRD——后（根）序遍歷。361、先序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空，則空操作；否則（1）訪問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。2、中序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空，則空操作；否則（1）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。3、后序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空，則空操作；否則（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。37若先序遍歷此二叉樹(shù),按訪問(wèn)結(jié)點(diǎn)的先后次序?qū)⒔Y(jié)點(diǎn)排列起來(lái),其先序序列為：-+a*b-cd/ef

按中序遍歷,其中序序列為：a+b*c-d-e/f按后序遍歷,其后序序列為：abcd-*+ef/-

－＋*a/b-dcfe38先序遍歷遞歸算法：voidpreorder(BiTreeT){if(T!=NULL){printf("%d\n",T->data);

preorder(T->lchild);

preorder(T->rchild);}}39ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:40主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC41中序遍歷遞歸算法：voidinorder(BiTreeT){if(T!=NULL){inorder(T->lchild);

printf("%d\n",T->data);

inorder(T->rchild);}}42ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:43后序遍歷遞歸算法：voidpostorder(BiTreeT){if(T!=NULL){postorder(T->lchild);

postorder(T->rchild);

printf("%d\n",T->data);}}44ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B45四、遍歷算法的應(yīng)用舉例1、統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)

(先序遍歷)2、求二叉樹(shù)的深度(后序遍歷)3、復(fù)制二叉樹(shù)(后序遍歷)4、建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)461、統(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。47void

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);}//if}//CountLeaf482、求二叉樹(shù)的深度(后序遍歷)算法基本思想:

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

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

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

if(!T)depthval=0;else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?

depthLeft:depthRight);

}

return

depthval;}503、復(fù)制二叉樹(shù)其基本操作為：生成一個(gè)結(jié)點(diǎn)。根元素T左子樹(shù)右子樹(shù)根元素NEWT左子樹(shù)右子樹(shù)左子樹(shù)右子樹(shù)(后序遍歷)51BiTNode

*GetTreeNode(TElemType

item,

BiTNode

*lptr,BiTNode

*rptr){

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(1);

T->data=item;

T->lchild=

lptr;T->rchild=

rptr;

returnT;}

生成一個(gè)二叉樹(shù)的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr)52BiTNode

*CopyTree(BiTNode

*T){

if(!T)returnNULL;

if(T->lchild)

newlptr=

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

else

newlptr=NULL;

if(T->rchild)

newrptr

=

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

else

newrptr=NULL;

newT=GetTreeNode(T->data,newlptr,

newrptr);

return

newT;}//CopyTree53ABCDEFGHK^D^

C^^B^H^^K^G^F^E^A例如：下列二叉樹(shù)的復(fù)制過(guò)程如下：newT54

以字符串的形式根左子樹(shù)右子樹(shù)定義一棵二叉樹(shù)例如:ABCD以空白字符“

”表示A(B(,C(,)),D(,))空樹(shù)只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)A以字符串“A

”表示以下列字符串表示4、建立二叉樹(shù)55Status

CreateBiTree(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)造左子樹(shù)

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

}

returnOK;}//CreateBiTree56AB

C

D

ABCD上頁(yè)算法執(zhí)行過(guò)程舉例如下：ATBCD^^^^^57建立二叉樹(shù)的二叉鏈表，已知輸入序列為：

ABCDEGFABCDEFG58

僅知二叉樹(shù)的先序序列“abcdefg”

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

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

二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根59abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列60void

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

int

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

if(n==0)T=NULL;

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

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

else{}}//}//CrtBT

……61T=(BiTNode*)malloc(sizeof(BiTNode));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);62練習(xí)：已知二叉樹(shù)的先序遍歷次序?yàn)椋篈BCDEGF，中序遍歷次序?yàn)椋篊BEDAGF，則該二叉樹(shù)的后序遍歷次序?yàn)楹?？ABCDEFG后序遍歷次序CEDBFGA63作業(yè)五：1、編寫(xiě)求兩棵二叉樹(shù)是否完全相等的遞歸算法,若相等函數(shù)返回真，否則返回假。Statusequal(BiTreeT1,BiTreeT2)2、編寫(xiě)把一棵二叉樹(shù)復(fù)制生成另一棵二叉樹(shù)的遞歸算法。voidcopy(BiTreeT1,BiTree&T2)641、編寫(xiě)求兩棵二叉樹(shù)是否完全相等的遞歸算法,若相等函數(shù)返回真，否則返回假。Statusequal(BiTreeT1,BiTreeT2){if(T1==NULL&&T2==NULL)returnTRUE;elseif(T1==NULL||T2==NULL)returnFALSE;elseif(T1->data!=T2->data)returnFALSE;elsereturnequal(T1->lchild,T2->lchild)&&equal(T1->rchild,T2->rchild);}652、編寫(xiě)把一棵二叉樹(shù)復(fù)制生成另一棵二叉樹(shù)的遞歸算法。voidcopy(BiTreeT1,BiTree&T2){if(T1==NULL)T2=NULL;else{if(!(T2=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);T2->data=T1->data;T2->lchild=T1->lchild;T2->rchild=T1->rchild;copy(T1->lchild,T2->lchild);copy(T1->rchild,T2->rchild);}}66中序遍歷非遞歸算法:voidinorder(BiTreeT){InitStack(S);p=T;while(p||!StackEmpty(S)){

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

Pop(S,p);

printf(p->data);p=p->rchild;}}}67ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問(wèn)：C(4)68pABCDEFGiP->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)69ABCDEFGiP->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)70ABCDEFGiP->A訪問(wèn)：CBEGDFp=NULL(13)ABCDEFGi訪問(wèn)：CBEGDFAp(14)ABCDEFGi訪問(wèn)：CBEGDFAp=NULL(15)71

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

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

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

C^^B

E^74對(duì)線索鏈表中結(jié)點(diǎn)的約定：在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹(shù)不空，則Lchild域的指針指向其左子樹(shù)，且左標(biāo)志域的值為“指針Link”；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“線索Thread”

。若該結(jié)點(diǎn)的右子樹(shù)不空，則rchild域的指針指向其右子樹(shù)，且右標(biāo)志域的值為“指針Link”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“線索Thread”。

如此定義的二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表”。75typedef

struct

BiThrNod

{

TElemTypedata;

struct

BiThrNode

*lchild,*rchild;//左右指針

PointerThr

LTag,RTag;//左右標(biāo)志}

BiThrNode,*BiThrTree;線索鏈表的類型描述：

typedef

enum

{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索76二、線索鏈表的遍歷算法:

for(p=

firstNode(T);p;p=Succ(p))Visit(p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。77例如:對(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)。78void

InOrderTraverse_Thr(BiThrTreeT,

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

while(p!=T){//空樹(shù)或遍歷結(jié)束時(shí)，p==Twhile(p->LTag==Link)p=p->lchild;//第一個(gè)結(jié)點(diǎn)

Visit(p->data);while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//訪問(wèn)后繼結(jié)點(diǎn)

}p=p->rchild;//p進(jìn)至其右子樹(shù)根

}}//InOrderTraverse_Thr79在中序遍歷過(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ū)。三、如何建立線索鏈表？80void

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}//InThreading81Status

InOrderThreading(BiThrTree

&Thrt,

BiThrTreeT){//構(gòu)建中序線索鏈表

if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;

Thrt->rchild=Thrt;

//添加頭結(jié)點(diǎn)

returnOK;}//InOrderThreading

……82if(!T)

Thrt->lchild=Thrt;

else{

Thrt->lchild=T;

pre=Thrt;

InThreading(T);

pre->rchild=Thrt;//處理最后一個(gè)結(jié)點(diǎn)

pre->RTag=Thread;

Thrt->rchild=pre;

}836.4樹(shù)和森林

84ABCDEFGr=0n=70

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、雙親表示法:85

typedef

struct

PTNode

{

Elemdata;

intparent;//雙親位置域

}

PTNode;

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

struct{

PTNodenodes[MAX_TREE_SIZE];

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

}

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

A

1

B

2

C

3

D

4

E

5

F

6

G

r=0n=7

datafirstchild

123456二、孩子鏈表表示法:-100022487typedef

struct

CTNode

{

intchild;

struct

CTNode

*next;

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

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

datafirstchild雙親結(jié)點(diǎn)結(jié)構(gòu)

typedef

struct{

Elemdata;

ChildPtr

firstchild;//孩子鏈的頭指針

}

CTBox;typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

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

}

CTree;樹(shù)結(jié)構(gòu):88ABCDEFGrootABCEDFG

ABCEDFG三、樹(shù)的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法89typedef

struct

CSNode{

Elemdata;

struct

CSNode

*firstchild,*nextsibling;}

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

firstchilddatanextsibling90

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

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

B=(LBT,Node(root),RBT);91由森林轉(zhuǎn)換成二叉樹(shù)的轉(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。92由二叉樹(shù)轉(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)。93一、樹(shù)的遍歷二、森林的遍歷三、樹(shù)的遍歷的應(yīng)用樹(shù)和森林的遍歷94樹(shù)的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:若樹(shù)不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。若樹(shù)不空，則先依次后根遍歷各棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。若樹(shù)不空，則自上而下自左至右訪問(wèn)樹(shù)中每個(gè)結(jié)點(diǎn)。95ABCDEFGHIJK先根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：ABEFCDGHIJK后根遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：EFBCIJKHGDA層次遍歷時(shí)頂點(diǎn)的訪問(wèn)次序：ABCDEFGHIJK96

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

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

余樹(shù)構(gòu)成的森林。即：依次從左至右對(duì)森林中的每一棵樹(shù)進(jìn)行后根遍歷。99樹(shù)的遍歷和二叉樹(shù)遍歷的對(duì)應(yīng)關(guān)系？先根遍歷后根遍歷樹(shù)二叉樹(shù)森林先序遍歷先序遍歷中序遍歷中序遍歷100設(shè)樹(shù)的存儲(chǔ)結(jié)構(gòu)為孩子兄弟鏈表typedef

struct

CSNode{

Elemdata;

struct

CSNode

*firstchild,*nextsibling;}

CSNode,*CSTree;一、求樹(shù)的深度二、輸出樹(shù)中所有從根到葉子的路徑101int

TreeDepth(CSTreeT){if(!T)return0;else{h1=TreeDepth(T->firstchild);h2=TreeDepth(T->nextsibling);

}}//TreeDepthreturn(max(h1+1,h2));一、求樹(shù)的深度的算法：102二、輸出樹(shù)中所有從根到葉子的路徑的算法:ABCDEFGHIJK例如：對(duì)左圖所示的樹(shù)，其輸出結(jié)果應(yīng)為：ABEABFACADGHIADGHJADGHK103void

AllPath(BitreeT,Stack&S){

//輸出二叉樹(shù)上從根到所有葉子結(jié)點(diǎn)的路徑

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)}//AllPath104voidOutPath(BitreeT,Stack&S){

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

while(!T){

Push(S,T->data);

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

Pop(S);

T=T->nextsibling;

}//while}//OutPath1056.6赫夫曼樹(shù)106一、最優(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ù)目。107最優(yōu)二叉樹(shù)：在所有含n個(gè)葉子結(jié)點(diǎn)、并帶不同權(quán)值的二叉樹(shù)中，必存在一棵其帶權(quán)路徑長(zhǎng)度取最小值的樹(shù)，稱為“最優(yōu)二叉樹(shù)”。樹(shù)的帶權(quán)路徑長(zhǎng)度定義為：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和

WPL(T)=

wklk

(對(duì)所有葉子結(jié)點(diǎn))。10827975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954109

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

F={T1,T2,…,Tn}，其中每棵二叉樹(shù)中均只含一個(gè)帶權(quán)值為wi

的根結(jié)點(diǎn)，其左、右子樹(shù)為空樹(shù)；二、如何構(gòu)造最優(yōu)樹(shù)(赫夫曼算法)以二叉樹(shù)為例：110（2）在F中選取其根結(jié)點(diǎn)的權(quán)值為最小的兩棵二叉樹(shù)，分別作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，并置這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和；（3）從F中刪去這兩棵樹(shù)，同時(shí)加入剛生成的新樹(shù)；（4）重復(fù)(2)和(3)兩步，直至F中只含一棵樹(shù)為止。1119例如:已知權(quán)值W={5,6,2,9,7}5627527697671395271126713952795271667132900001111000110110111113

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

利用赫夫曼樹(shù)可以構(gòu)造一種不等長(zhǎng)的二進(jìn)制編碼，并且構(gòu)造所得的赫夫曼編碼是一種最優(yōu)前綴編碼，即使所傳電文的總長(zhǎng)度最短。114例：已知某系統(tǒng)在通信中只可能出現(xiàn)八種字符，其概率分別為0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)赫夫曼編碼。115Huffman樹(shù)應(yīng)用：