數(shù)據(jù)結(jié)構(gòu)new第六章二叉樹

6.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲(chǔ)結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼第六章樹和二叉樹6.1樹的類型定義

A

C

GT2D

HIT3J

M

BEL

KT1F例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。結(jié)點(diǎn)間有明顯的層次結(jié)構(gòu)關(guān)系數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。

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

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

基本操作：查找類

插入類刪除類

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棵子樹樹的表示樹根T1T2T3(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。對(duì)比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(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è)后繼)基本術(shù)語結(jié)點(diǎn):結(jié)點(diǎn)的度:樹的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支分支的個(gè)數(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)的層次:樹的深度：

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次任何一棵非空樹是一個(gè)二元組

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

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF6.2

二叉樹的類型定義

二叉樹或?yàn)榭諛洌蚴怯梢粋€(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹

二叉樹的主要基本操作：查找類插入類刪除類

Root(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,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);二叉樹

的重要特性

性質(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-2

2=2i-1

。423167891011121314155第三層上(i=3)，有23-1=4個(gè)節(jié)點(diǎn)。第四層上(i=4)，有24-1=8個(gè)節(jié)點(diǎn)。性質(zhì)2：

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

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

20+21+

+2k-1=2k-1

。423167891011121314155此樹的深度k

=4，共有24-1=15個(gè)節(jié)點(diǎn)。

性質(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。423167891011121314155n0=8n2=7兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij特點(diǎn)：每一層上都含有最大結(jié)點(diǎn)數(shù)。深度為K的滿二叉樹，結(jié)點(diǎn)個(gè)數(shù)為2k-1

性質(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。423167891011121314155性質(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)。423167891011125

完全二叉樹6.3二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹的順序存儲(chǔ)表示#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;一、二叉樹的順序存儲(chǔ)表示用一組連續(xù)的存儲(chǔ)單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。二叉樹順序存儲(chǔ)結(jié)構(gòu)

bt[16]若父結(jié)點(diǎn)在數(shù)組中i下標(biāo)處，其左孩子在2*i處，右孩子在2*i+1處。11ABcFED

●●●●●●●●●124

8

9105637121314152h-1=24-1=15用一組連續(xù)的存儲(chǔ)單元存放二叉樹的數(shù)據(jù)元素。結(jié)點(diǎn)在數(shù)組中的相對(duì)位置蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。0000FE000DC0BA15141312111098765432100一般二叉樹必須按完全二叉樹的形式存儲(chǔ)，將造成存儲(chǔ)的浪費(fèi)。typedefTElemTypeSqBiTree[MAX_TREE_SIZE+1];//0號(hào)單元未用SqBiTreebt例如:ABCDEF

ABDCEF

0123456789101112131401326typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表ADEBCF

rootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;ADEBCF

root

2．三叉鏈表parent

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

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

structTriTNode*parent;//雙親指針

}TriTNode,*TriTree;0123456dataparent結(jié)點(diǎn)結(jié)構(gòu):3．雙親鏈表LRTagLRRRLtypedefstruct

BPTNode

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

TElemTypedata;

int

*parent;//指向雙親的指針

charLRTag;//左、右孩子標(biāo)志域

}BPTNodetypedefstructBPTree{//樹結(jié)構(gòu)

BPTNodenodes[MAX_TREE_SIZE];

intnum_node;//結(jié)點(diǎn)數(shù)目

introot;//根結(jié)點(diǎn)的位置

}BPTree6.4二叉樹的遍歷一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、中序遍歷算法的非遞歸描述五、遍歷算法的應(yīng)用舉例遍歷：按某條搜索路線尋訪樹中每個(gè)結(jié)點(diǎn)且只被訪問一次。一、問題的提出“訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。查找某個(gè)結(jié)點(diǎn)，或?qū)Χ鏄渲腥拷Y(jié)點(diǎn)進(jìn)行某種處理，就需要遍歷。

“遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。對(duì)“二叉樹”而言，可以有三條搜索路徑1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。二、先左后右的遍歷算法按先左后右的原則，一般使用三種遍歷：先根遍歷(DLR):

訪問根結(jié)點(diǎn)，按先序遍歷左子樹，按先序遍歷右子樹。中根遍歷(LDR):

按中序遍歷左子樹，訪問根結(jié)點(diǎn)，按中序遍歷右子樹。后根遍歷(LRD):

按后序遍歷左子樹，按后序遍歷右子樹，訪問根結(jié)點(diǎn)。二叉樹為空時(shí)，執(zhí)行空操作，即空二叉樹已遍歷完。遍歷算法例：先序遍歷：DLR中序遍歷：LDR后序遍歷：LRDADBCT1T2T3DLRADLRDLR>B>>D>>CDLR以先序遍歷DLR為例演示遍歷過程ABDCBDACDBCA三、算法的遞歸描述voidPreorder(BiTreeT,void(*visit)(TElemTypee)){//

先序遍歷二叉樹

//初始條件：二叉樹T存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)。修改算法6.1//操作結(jié)果：先序遞歸遍歷T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次

if(T){//T不空

visit(T->data);

//先訪問根結(jié)點(diǎn).如printf(“%c”,T->data)

Preorder(T->lchild,visit);

//再先序遍歷左子樹

Preorder(T->rchild,visit);//最后先序遍歷右子樹

}}四、中序遍歷算法的非遞歸描述voidInOrderTraverse1(BiTreeT,void(*Visit)(TElemType)){//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。修改算法6.3//中序遍歷二叉樹T的非遞歸算法(利用棧)，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)VisitSqStackS;InitStack(S);//初始化棧Swhile(T||!StackEmpty(S))//當(dāng)二叉樹T不空或者棧不空

{if(T)//二叉樹T不空

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

Push(S,T);//入棧根指針

T=T->lchild;//T指向其左孩子

}else//根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹

{Pop(S,T);//出棧根指針

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

T=T->rchild;//T指向其右孩子

}}printf("\n");}T五、遍歷算法的應(yīng)用舉例1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)

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

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(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);}//if}//CountLeaf2、求二叉樹的深度(后序遍歷)算法基本思想:

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

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

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

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

}

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

*GetTreeNode(TElemTypeitem,

BiTNode

*lptr,BiTNode*rptr){

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

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)BiTNode

*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);

returnnewT;}//CopyTreeABCDEFGHK^D^C^^B^H^^K^G^F^E^A例如：下列二叉樹的復(fù)制過程如下：newT4、建立二叉樹的存儲(chǔ)結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法

以字符串的形式根左子樹右子樹定義一棵二叉樹例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空樹只含一個(gè)根結(jié)點(diǎn)的二叉樹A以字符串“A”表示以下列字符串表示AB

C

D

ABCD算法執(zhí)行過程舉例如下：ATBCD^^^^^scanf(&ch);//輸入結(jié)點(diǎn)的值

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

else{T=(BiTree)malloc(sizeof(BiTNode));//生成根結(jié)點(diǎn)

if(!T)exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);//遞歸構(gòu)造左子樹

CreateBiTree(T->rchild);//遞歸構(gòu)造右子樹}}voidCreateBiTree(BiTree&T){voidCreateBiTree(BiTree&T)//算法6.4：按先序次序輸入二叉樹中結(jié)點(diǎn)的值(字符型)，構(gòu)造二叉鏈表表示的二叉樹T。

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

不能唯一確定一棵二叉樹，5、由遍歷序列確定二叉樹

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

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根由二叉樹的先序和中序序列確定二叉樹abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.5

線索二叉樹

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

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

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

C^^B

E^意義：保存遍歷二叉樹后得到的線性序列，避免重復(fù)遍歷。對(duì)線索鏈表中結(jié)點(diǎn)的約定：

在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域，規(guī)定如下：如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表”。左標(biāo)志ltag:0表示lchild指向左孩子結(jié)點(diǎn)

1表示lchild指向前驅(qū)結(jié)點(diǎn)右標(biāo)志rtag:0表示rchild指向右孩子結(jié)點(diǎn)

1表示rchild指向后繼結(jié)點(diǎn)這樣,每個(gè)結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)如下：LChildLtagDataRtagRChildtypedefstruct

BiThrNod{

TElemTypedata;

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

PointerThrLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;線索鏈表的類型描述：

typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索LChildLtagDataRtagRChild二、線索鏈表的遍歷算法:由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。例如:對(duì)中序線索化鏈表的遍歷算法

※中序遍歷的第一個(gè)結(jié)點(diǎn)？左子樹上處于“最左下”（沒有左子樹）的結(jié)點(diǎn)。

※在中序線索化鏈表中結(jié)點(diǎn)的后繼？若無右子樹，則為后繼線索所指結(jié)點(diǎn)；否則為對(duì)其右子樹進(jìn)行中序遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)。LChildLtagDataRtagRChild二叉樹voidInOrderTraverse_Thr(BiThrTreeT,void(*Visit)(TElemType))

{//中序遍歷線索二叉樹T(頭結(jié)點(diǎn))的非遞歸算法。算法6.5BiThrTreep;p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T)

{

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

while(p->LTag==Link)

//由根結(jié)點(diǎn)一直找到二叉樹的最左結(jié)點(diǎn)

p=p->lchild;

//p指向其左孩子

Visit(p->data);//訪問此結(jié)點(diǎn)

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

{

//p->rchild是線索(后繼)，且不是遍歷的最后一個(gè)結(jié)點(diǎn)

p=p->rchild;//p指向其后繼

Visit(p->data);//訪問后繼結(jié)點(diǎn)

}

//若p->rchild不是線索(是右孩子)，p指向右孩子，返回循環(huán)，找這棵子樹中序遍歷的第1個(gè)結(jié)點(diǎn)

p=p->rchild;

}}

typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索LChildLtagDataRtagRChild

在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向剛剛訪問過的結(jié)點(diǎn)，指針p指向當(dāng)前訪問的結(jié)點(diǎn)。即pre指向當(dāng)前訪問結(jié)點(diǎn)的前驅(qū)。三、如何建立線索鏈表？BiThrTreepre;//全局變量，始終指向剛剛訪問過的結(jié)點(diǎn)

voidInThreading(BiThrTreep)

{//通過中序遍歷進(jìn)行中序線索化，線索化之后pre指向最后一個(gè)結(jié)點(diǎn)。算法6.7if(p)//線索二叉樹不空

{InThreading(p->lchild);//遞歸左子樹線索化

if(!p->lchild)//沒有左孩子

{p->LTag=Thread;//左標(biāo)志為線索(前驅(qū))p->lchild=pre;//左孩子指針指向前驅(qū)

}if(!pre->rchild)//前驅(qū)沒有右孩子

{pre->RTag=Thread;//前驅(qū)的右標(biāo)志為線索(后繼)pre->rchild=p;//前驅(qū)右孩子指針指向其后繼(當(dāng)前結(jié)點(diǎn)p)}pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);//遞歸右子樹線索化

}}voidInOrderThreading(BiThrTree&Thrt,BiThrTreeT)

{//中序遍歷二叉樹T，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)。算法6.6

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))//生成頭結(jié)點(diǎn)不成功

exit(OVERFLOW);Thrt->LTag=Link;//建頭結(jié)點(diǎn)，左標(biāo)志為指針

Thrt->RTag=Thread;//右標(biāo)志為線索

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

if(!T)//若二叉樹T空，則左孩子指針回指

Thrt->lchild=Thrt;

else

//二叉樹T非空

{Thrt->lchild=T;//頭結(jié)點(diǎn)的左孩子指針指向根結(jié)點(diǎn)

pre=Thrt;//pre(前驅(qū))的初值指向頭結(jié)點(diǎn)，全局變量

InThreading(T);

//中序遍歷進(jìn)行中序線索化，pre指向中序遍歷的最后一個(gè)結(jié)點(diǎn)

pre->rchild=Thrt;//最后一個(gè)結(jié)點(diǎn)的右孩子指針指向頭結(jié)點(diǎn)

pre->RTag=Thread;//最后一個(gè)結(jié)點(diǎn)的右標(biāo)志為線索

Thrt->rchild=pre;//頭結(jié)點(diǎn)的右孩子指針指向中序遍歷的最后一個(gè)結(jié)點(diǎn)

}}

6.6樹和森林的表示方法樹的三種存儲(chǔ)結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法四、樹、森林與二叉樹的相互轉(zhuǎn)換ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

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

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;結(jié)點(diǎn)結(jié)構(gòu):樹結(jié)構(gòu):#defineMAX_TREE_SIZE100ABCDEFG0

A1

B

2

C

3

D

4

E

5

F

6

G

r=0n=7123456二、孩子鏈表表示法:parent

1000224datafirstchildABCDEFGABCEDFGrootABCEDFG

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

firstchilddatanextsibling結(jié)點(diǎn)結(jié)構(gòu)typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;CSTreeroot四、樹、森林與二叉樹的相互轉(zhuǎn)換1.樹轉(zhuǎn)換為二叉樹由于二叉樹可以用二叉鏈表表示，為了使一般樹也能用二叉鏈表表示，必須找出樹與二叉樹之間的關(guān)系。這樣，給定一棵樹，可以找到唯一的一棵二叉樹與之對(duì)應(yīng)。(1)樹中所有相鄰兄弟之間加一條連線。(2)對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留其與第一個(gè)孩子結(jié)點(diǎn)之間的連線，刪去其與其它孩子結(jié)點(diǎn)之間的連線。(3)以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針旋轉(zhuǎn)一定的角度，使之結(jié)構(gòu)層次分明。

I

A

B

C

DEF

G

H(b)

A

B

CDE

G

HFI(a)樹轉(zhuǎn)換為二叉樹ABEFCDGHI(d)ABCDEFGHI(c)注意：樹轉(zhuǎn)換為二叉樹后，根無右子樹。樹與二叉樹的對(duì)應(yīng)樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法二叉樹二叉鏈表存儲(chǔ)表示法2.森林轉(zhuǎn)換為二叉樹

（1）將森林中的每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹。（2）第一棵二叉樹不動(dòng)，從第二棵二叉樹開始，依次把后一棵二叉樹的根結(jié)點(diǎn)作為前一棵二叉樹根結(jié)點(diǎn)的右孩子，當(dāng)所有二叉樹連在一起后，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹。森林轉(zhuǎn)換為二叉樹的過程森林轉(zhuǎn)換后的二叉樹，其根結(jié)點(diǎn)有右孩子由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:若F=Φ，則B=Φ；否則，由ROOT(T1)

對(duì)應(yīng)得到B的根

root；由(t11,t12,…,t1m1)

對(duì)應(yīng)得到LB；由(T2,T3,…,Tm)

對(duì)應(yīng)得到RB。設(shè)森林

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

B=(root,LB,RB);由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為：若B=Φ，則F=Φ；否則，由root

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

)；由LB

對(duì)應(yīng)得到T1中的子森林（t11,t12,…，t1m)；由RB

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

3.二叉樹還原為樹或森林（1）若某結(jié)點(diǎn)是其雙親的左孩子，則把該結(jié)點(diǎn)的右孩子、右孩子的右孩子……都與該結(jié)點(diǎn)的雙親結(jié)點(diǎn)用線連起來。（2）刪掉原二叉樹中所有雙親結(jié)點(diǎn)與右孩子結(jié)點(diǎn)的連線。（3）整理由（1）、（2）兩步所得到的樹或森林。二叉樹到森林的轉(zhuǎn)換示例

設(shè)二叉樹

B=(root,LB,RB);森林

F=(T1,T2,…,Tm);

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

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

左是孩子，右是兄弟。6.7樹和森林的遍歷一、樹的遍歷二、森林的遍歷樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹不空，則先訪問根結(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)行先根遍歷。例如，P138圖6.17中森林的先序遍歷序列為ABCDEFGHIJ。２．中序遍歷若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。即：依次從左至右對(duì)森林中的每一棵樹進(jìn)行后根遍歷。森林的遍歷例如，P138圖6.17中森林的中序遍歷序列為BCDAFEHJIG。

樹的遍歷和二叉樹遍歷的對(duì)應(yīng)關(guān)系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷6.8哈夫曼樹與應(yīng)用

最優(yōu)樹的定義

如何構(gòu)造最優(yōu)樹哈夫曼樹與應(yīng)用

一、最優(yōu)樹的定義樹的路徑長度定義為：

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

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

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

樹的帶權(quán)路徑長度定義為：

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

WPL(T)=

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

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