第六章樹和二叉樹學(xué)習(xí)目標(biāo)

掌握樹的定義、表示方法、基本性質(zhì)、存儲結(jié)構(gòu)和遍歷算法；掌握二叉樹的定義、基本性質(zhì)、存儲結(jié)構(gòu)、和各種運算。6.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8

哈夫曼樹與哈夫曼編碼6.1樹的類型定義6.1樹的邏輯結(jié)構(gòu)及其操作.樹（Tree)

是一個非空的有限元素的集合，元素之間具有如下關(guān)系：由且僅有一個特殊元素，他沒有前驅(qū)（稱為樹根Root）,其余元素都有且僅有一個前驅(qū)，所有元素可以有零個或多個后繼。ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:樹形結(jié)構(gòu)全校學(xué)生檔案管理的組織方式ABCDEFGH樹形結(jié)構(gòu)——結(jié)點間具有分層次的連接關(guān)系HBCDEFGA現(xiàn)實世界中，能用樹的結(jié)構(gòu)表示的例子：學(xué)校的行政關(guān)系、書的層次結(jié)構(gòu)、人類的家族血緣關(guān)系等。對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點

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

(無后繼)多個葉子結(jié)點

(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

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

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

數(shù)據(jù)關(guān)系R：

基本操作：查找類

插入類刪除類

Root(T)//求樹的根結(jié)點

查找類：Value(T,cur_e)//求當(dāng)前結(jié)點的元素值

Parent(T,cur_e)//求當(dāng)前結(jié)點的雙親結(jié)點LeftChild(T,cur_e)//求當(dāng)前結(jié)點的最左孩子

RightSibling(T,cur_e)//求當(dāng)前結(jié)點的右兄弟TreeEmpty(T)//判定樹是否為空樹

TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷InitTree(&T)//初始化置空樹

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

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹基本術(shù)語結(jié)點:結(jié)點的度:樹的度:葉子結(jié)點:分支結(jié)點:樹中的一個數(shù)據(jù)元素分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM內(nèi)部結(jié)點:孩子結(jié)點:雙親結(jié)點:兄弟結(jié)點:除根之外的分支結(jié)點結(jié)點的子樹的根稱為該結(jié)點的孩子（后繼）一個結(jié)點是它各子樹的根結(jié)點的雙親（前驅(qū)）具有相同雙親的結(jié)點DHIJM祖先:子孫:從根結(jié)點到該結(jié)點路徑上所有結(jié)點都稱為該結(jié)點的祖先。該結(jié)點所有子樹上的結(jié)點都稱為該結(jié)點的子孫MDHIJ(從根到結(jié)點的)路徑：結(jié)點的層次:樹的深度：

由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL根結(jié)點定義為第１層，根的兒子定義為第２層，以此類推，記作Ｌ（ｖ）樹中葉子結(jié)點所在的最大層次堂兄弟:雙親在同一層上的結(jié)點(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。任何一棵非空樹是一個二元組

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

F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF注意：１．根沒有雙親，葉子沒有孩子２．堂兄弟的雙親是兄弟關(guān)系嗎？ABCDEFGHIJMKL樹的常見表示方法1.直觀表示法用圓圈表示結(jié)點，元素寫在圓圈中，連線表示元素之間的關(guān)系，根在上，葉子在下（即樹向下生長）ABCDEFGHIJMKL樹的常見表示方法2.集合表示法根據(jù)樹的集合定義，寫出集合劃分。{a,{b,{e},{f}},{c},{d,{g}}}3.文氏圖表示法集合表示的一種直觀表示，用圖表示集合。ABEHICGFD4、目錄表示法將樹描述成一本書。書—章節(jié)—節(jié)—小節(jié)5、廣義表表示法將樹描述成廣義表。子樹對應(yīng)的是子表(a(b(e),(f)),(c),(d,(g)))ABCDEFGKHIJ已知一棵二叉樹的廣義表表示為a(b(c),d(e(,g(h)),f))，則該二叉樹的高度為（）。假定根結(jié)點的高度為0。

A.3 B.4 C.5 D.6B6.2

二叉樹的類型定義為何要重點研究每結(jié)點最多只有兩個“叉”的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強；可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。ABCDEFGHK根結(jié)點左子樹右子樹

二叉樹或為空樹，或是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。二叉樹的特點（和樹比較）二叉樹有兩棵子樹（可以為空）；而樹可以有多棵。二叉樹是有序樹（有左右之分）；而樹是無序樹.二叉樹結(jié)點的度最大是2；二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹問：具有3個結(jié)點的二叉樹可能有幾種不同形態(tài)？

應(yīng)用舉例以用二叉樹表示表達式

a+b*(c-d)-e/f

e

dc

b

f

a

+

*

/

-

-

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

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);刪除類二叉樹

的重要特性用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時，只有一個根結(jié)點：

2i-1=20=1；假設(shè)對所有的j，1≤j

i，命題成立；二叉樹上每個結(jié)點至多有兩棵子樹，則第i層的結(jié)點數(shù)=2i-22=2i-1

。性質(zhì)1：

在二叉樹的第i

層上至多有2i-1個結(jié)點。(i≥1)性質(zhì)2：

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

20+21+

+2k-1=2k-1

。一棵高度為5的二叉樹中，最多包含有______個結(jié)點。假定根結(jié)點的高度為0。

63

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結(jié)點、n2個度為

2

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

而b=n-1=n0+n1+n2-1

由此，n0=n2+1。abcdefghij

在一棵具有n個結(jié)點的二叉樹中，所有結(jié)點的空子樹個數(shù)等于（）。

A.n B.n-1 C.n+1 D.2*n思考題：C求空子樹的個數(shù)等價于：2n0+n1得值有n=n0+n1+n2和n0=n2+12n0+n1=n+1兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結(jié)點的二叉樹。對二叉樹的結(jié)點按照逐層從上到下、每層從左到右進行編號，于是每個結(jié)點都有一個序號。123456789101112131415完全二叉樹：樹中所含的n個結(jié)點和滿二叉樹中編號為1至n的結(jié)點一一對應(yīng)。abcdefghij完全二叉樹的特點：

1、只有最后一層是不滿的，不滿層的結(jié)點最先出現(xiàn)在左邊

2、至多只有最下面的兩層結(jié)點的度小于23、任何左子樹的高度不會小于右子樹的高度，且左右子樹的高度最大相差1；

4。葉子結(jié)點最多出現(xiàn)在最后2層上。abcdefghij

性質(zhì)4：

具有n個結(jié)點的完全二叉樹的深度為

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

-1≤n<2k

-1

即

k-1≤log2n<k

因為k只能是整數(shù)，因此，

k=log2n

+1。在一棵具有35個結(jié)點的完全二叉樹中，該樹的高度為（）。

A.5 B.6 C.7 D.8練習(xí)題：B性質(zhì)5：若對含n個結(jié)點的完全二叉樹從上到下且從左至右進行1

至n

的編號，則對完全二叉樹中任意一個編號為i

（1<=i<=n)的結(jié)點：123456789101112(1)若i=1，則該結(jié)點是二叉樹的根，無雙親，否則，編號為i/2的結(jié)點為其雙親結(jié)點；

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

否則，編號為2i的結(jié)點為其左孩子結(jié)點；

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

否則，編號為2i+1的結(jié)點為其右孩子結(jié)點。1.

在一棵完全二叉樹中，若編號為i的結(jié)點存在左孩子，則左子女結(jié)點的編號為（）。假定根結(jié)點的編號為0A.2iB.2i-1C.2i+1D.2i+2C練習(xí)題：6.3二叉樹的存儲結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯Ρ硎疽弧⒍鏄涞捻樞虼鎯Ρ硎疽?、二叉樹的順序存儲表示一、存儲結(jié)構(gòu)1、存儲方式：用地址連續(xù)的空間單元存儲二叉樹的各個元素，但為了表示關(guān)系，元素存放時，首先確定一個序號，該序號是對二叉樹按照完全二叉樹形式編號而得適合完全二叉樹，最差的情況是右斜樹T[16]11ABCFED

●●●●●●●●●124

8

9105637121314150000FE000DC0BA15141312111098765432100例如:

特點：層次關(guān)系非常明確，雙親i/2,孩子2i,2i+1，但是必須知道結(jié)點的編號。

必須按完全二叉樹的形式存儲，將造成存儲的浪費。例如:ABCDEF

ABDCEF

0123456789101112131401326缺點：插入、刪除需要移動元素，空間效率低。#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點數(shù)typedef

TElemType

SqBiTree[MAX_TREE_SIZE];//0號單元存儲根結(jié)點SqBiTree

bt;二叉樹的順序存儲表示虛擬實現(xiàn)二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表

存儲方式：用任意的空間單元來存儲二叉樹的各個元素，在存儲元素的同時，也存儲其左右孩子的地址。ADEBCFrootlchilddatarchild結(jié)點結(jié)構(gòu):1.二叉鏈表特點:占用空間不隨樹的形態(tài)變化

n個結(jié)點的二叉樹，占用空間為：

n*(存儲一個元素的空間+2*存儲一個指針的空間）對求孩子操作容易，但求雙親難；插入、刪除元素不需要移動，但調(diào)整指針多；空指針多

多少?typedef

struct

BiTNode

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

TElemTypedata;

struct

BiTNode

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

BiTNode,*BiTree;lchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:ADEBCFroot2．三叉鏈表parent

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

typedef

struct

TriTNode

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

TElemTypedata;

struct

TriTNode

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

struct

TriTNode

*parent;//雙親指針

}

TriTNode,*TriTree;parent

lchilddatarchild結(jié)點結(jié)構(gòu):C語言的類型描述如下:0123456dataparent結(jié)點結(jié)構(gòu):3．雙親鏈表LRTagLRRRLABCDEF

typedef

struct

BPTNode

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

TElemTypedata;

int

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

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

}

BPTNode

typedef

struct

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

BPTNodenodes[MAX_TREE_SIZE];

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

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

}

BPTree6.4二叉樹的遍歷一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述五、遍歷算法的應(yīng)用舉例四、中序遍歷算法的非遞歸描述

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

“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。對“二叉樹”而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。一、按層遍歷算法voidLevelorder(BiTree*BT){constMaxLength=30;

BiTree*q[MaxLength];//定義隊列

intfront=0,rear=0;//定義隊首和隊尾指針

BiTree*p;if(BT!=NULL){//將樹根指針進隊

q[rear]=BT;rear=(rear+1)%MaxLength;}AEBDCGFwhile(front!=rear){p=q[front];front=(front+1)%MaxLength;

cout<<p->data<<'';if(p->left!=NULL){q[rear]=p->left;rear=(rear+1)%MaxLength;}if(p->right!=NULL){q[rear]=p->right;rear=(rear+1)%MaxLength;}}//whileendAEBDCGF}二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：ABCDEFGH000000000biginend先序遍歷順序:ABDFGCEHABDFGCEH先（根）序的遍歷算法：123456789101112輸出序列：1,2,4,8,9,5,10,11,3,6,12,7

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。中（根）序的遍歷算法：ABCDEFGH000000000biginend中序遍歷順序:ABDFGCEHBFDGACEH中（根）序的遍歷算法：12345679101112輸出序列：4,9,2,10,5,11,1,12,6,3,7

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。后（根）序的遍歷算法：ABCDEFGH000000000biginend后序遍歷順序:FGDBHECAABDFGCEH后（根）序的遍歷算法：12345679101112輸出序列：9,4,10,11,5,2,12,6,7,3,1序號0123456789101112data20846515300001018035已知一棵二叉樹的靜態(tài)數(shù)組表示（即順序存儲表示）如下，其中0表示空指針，請分別寫出該二叉樹的前序、中序、后序遍歷的序列。

前序序列：2085151018463035

中序序列：5810151820303546

后序序列：5101815835304620

假定一棵二叉樹的廣義表表示為a(b(c),d(e,f))，分別寫出對它進行前序、中序、后序、按層遍歷的結(jié)果。前序：__________________

中序：__________________

后序：__________________

按層：__________________abcdefcbaedfcbefdaabdcef軟件設(shè)計師2004上半年設(shè)結(jié)點x和y是二叉樹中任意的兩個結(jié)點，在該二叉樹的先根遍歷序列中x在y之前，而在其后根遍歷序列中x在y之后，則x和y的關(guān)系是__(10)__。A．x是y的左兄弟B．x是y的右兄弟C．x是y的祖先

D．x是y的后裔

C三、算法的遞歸描述voidPreorder(BiTreeT,

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

先序遍歷二叉樹

if(T){

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

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

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

}}VoidPreOderTraverse(BiTreeT){if(T!=NULL){visit(T->data);

PreOrderTraverse(T->lchild);

PreOrderTraverser(T->rchild);}}/*先序遍歷*/主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBvisit(B);pre(TL);BTAvisit(A);pre(TL);ATDvisit(D);pre(TL);DTCvisit(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);void

InorderTraverse(BiTreeT,

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

中序遍歷二叉樹

if(T){

InorderTraverse(T->lchild,visit);

//遍歷左子樹

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

InorderTraverse

(T->rchild,visit);

//遍歷右子樹

}}中序遍歷算法void

PostOrderTraverse(BiTreeT,

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

中序遍歷二叉樹

if(T){PostOrderTraverse(T->lchild,visit);//遍歷左子樹

PostOrderTraverse(T->rchild,visit);//遍歷右子樹

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

}}后序遍歷算法四、中序遍歷算法的非遞歸描述BiTNode

*GoFarLeft(BiTreeT,Stack*S){

if(!T)returnNULL;

while(T->lchild){Push(S,T);T=T->lchild;

}

returnT;}void

Inorder_I(BiTreeT,void(*visit)(TelemType&e)){

Stack*S;

t=GoFarLeft(T,S);//找到最左下的結(jié)點

while(t){

visit(t->data);

if(t->rchild)t=

GoFarLeft(t->rchild,S);

elseif(!StackEmpty(S))//棧不空時退棧

t=Pop(S);

elset=NULL;//

?？毡砻鞅闅v結(jié)束

}//while}//Inorder_I

五、遍歷算法的應(yīng)用舉例1、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)

(先序遍歷)2、求二叉樹的深度(后序遍歷)3、復(fù)制二叉樹(后序遍歷)4、建立二叉樹的存儲結(jié)構(gòu)5、二叉樹的其他運算和習(xí)題1、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)算法基本思想:

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

CountLeaf

(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;//對葉子結(jié)點計數(shù)

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf2、求二叉樹的深度(后序遍歷)算法基本思想:從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點”的操作為：求得左、右子樹深度的最大值，然后加1。

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

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

if(!T)depthval=0;else{

depthLeft=Depth(T->lchild);

depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?

depthLeft:depthRight);

}

return

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

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

生成一個二叉樹的結(jié)點(其數(shù)據(jù)域為item,左指針域為lptr,右指針域為rptr)BiTNode

*CopyTree(BiTNode

*T){

if(!T)returnNULL;

if(T->lchild)

newlptr=

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

else

newlptr=NULL;

if(T->rchild)

newrptr

=

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

else

newrptr=NULL;

newT=GetTreeNode(T->data,newlptr,

newrptr);

return

newT;}//CopyTreeABCDEFGHK^D^

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

按照給定的先序序列建立二叉鏈表由二叉樹的先序和中序序列建樹

按照給定的先序序列建立二叉鏈表根左子樹右子樹定義一棵二叉樹例如:ABCD以空白字符“

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

”表示以下列字符串表示Status

CreateBiTree(BiTree

&T)

{

scanf(“%c”,&ch);

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

else{

if(!(T=(BiTNode

*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);T->data=ch;//生成根結(jié)點

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

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

}

returnOK;}//CreateBiTreeAB

C

D

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

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

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

如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列

已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,E,F,D,I,H,J,G后序序列：______________________

C,B,F,E,I,J,H,G,D,A

已知一棵二叉樹的中序和后序序列如下，求該二叉樹的高度（假定空樹的高度為0）和度為2、度為1的結(jié)點及葉結(jié)點個數(shù)。中根序列：c,b,d,e,a,g,i,h,j,f后根序列：c,e,d,b,i,j,h,g,f,a

高度：________度為2：________度為1：________葉子：_________

高度：5

度為2：3

度為1：3

葉子：4五、二叉樹其他運算1.初始化二叉樹

voidInitBTree(BiTree&T){T=NULL;}2.檢查二叉樹是否為空

bool

BTreeEmpty(BiTree&T){returnT==NULL;}3.清除二叉樹

voidDeleteBTree(BiTree&T){if(T!=NULL){DeleteBTree(T->left);//刪除左子樹

DeleteBTree(T->right);//刪除右子樹

deleteT;//刪除根結(jié)點

}}voidClearBTree(BiTree&T){DeleteBTree(T);T=NULL;}1、

已知二叉樹中的結(jié)點類型用比BiTreeNode表示，被定義為:

struct

BiTreeNode

{

datatypedata;

BiTreeNode*leftChild,*rightChild,*parent;};

其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域，parent為指向父結(jié)點的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)T指向一棵二叉樹的樹根結(jié)點，x保存一個結(jié)點的值。

BiTreeNode*PN(BiTreeNode*T,datatype&x){

if(T==NULL)returnNULL;else{BiTreeNode*mt;

if(T->data==x)returnT->parent; elseif(mt=PN(T->leftChild,x))return

mt; elseif(mt=PN(T->rightChild,x))return

mt; returnNULL; }}

算法功能：2已知二叉搜索樹中的結(jié)點類型用BinTreeNode表示，被定義:struct

BinTreeNode

{

ElemTypedata;

BinTreeNode*leftChild,*rightChild;};其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域。假定pt所指向的二叉搜索樹的廣義表表示為:25(10(5,16(12)),40(32(,38)))，按照下面算法，(1)執(zhí)行unknown(pt,40)調(diào)用后返回的值為_____。(2)執(zhí)行unknown(pt,38)調(diào)用后返回的值為______。(3)執(zhí)行unknown(pt,5)調(diào)用后返回的值為______。(4)執(zhí)行unknown(pt,60)調(diào)用后返回的值為______。

int

unknown(BinTreeNode*t,

ElemTypex){if(t==NULL)return0;elseif(t->data==x)return1; elseif(t->data>x) return1+unknown(t->leftChild,x); elsereturn1+unknown(t->rightChild,x); }3、

已知二叉樹中的結(jié)點類型用比BiTreeNode表示，被定義為:

struct

BiTreeNode

{

datatypedata;

BiTreeNode*leftChild,*rightChild,*parent;};

其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域，parent為指向父結(jié)點的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)T指向一棵二叉樹的樹根結(jié)點，x保存一個結(jié)點的值。

BiTreeNode*PN(BiTreeNode*T,datatype&x){if(T==NULL)returnNULL;else{BiTreeNode*mt; if(T->data==x)returnT->parent; elseif(mt=PN(T->leftChild,x))returnmt; elseif(mt=PN(T->rightChild,x))returnmt; returnNULL; }}

算法功能：從樹根指針為T的二叉樹中查找值為x的結(jié)點，返回指向父結(jié)點的指針

4、

已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為:

struct

BinTreeNode{chardata;BinTreeNode*leftChild,*rightChild;};其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域。假定指針bt指向一棵二叉樹，該二叉樹的廣義表表示為a(b(a,d(f)),c(e(,a(k)),b))，整數(shù)變量C的值為0，若：(1)執(zhí)行BTC1(bt,’a’,C)調(diào)用后，C的值為_____;(2)執(zhí)行BTC1(bt,’b’,C)調(diào)用后，C的值為_____;(3)執(zhí)行BTC1(bt,’c’,C)調(diào)用后，C的值為_____;(4)執(zhí)行BTC1(bt,’g’,C)調(diào)用后，C的值為______;

voidBTC1(BinTreeNode*BT,charx,int&k){ if(BT!=NULL){ if(BT->data==x)k++; BTC1(BT->leftChild,x,k); BTC1(BT->rightChild,x,k); }}5、

已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為:

struct

BinTreeNode{ElemTypedata; BinTreeNode*leftChild,*rightChild;};

其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹的根結(jié)點。

intDST(BinTreeNode*&BT,ElemTypex){ if(BT==NULL)return0; else{ if(BT->data==x){BT=NULL;return1;} else{ if(DST(BT->leftChild,x))return1; if(DST(BT->rightChild,x))return1; elsereturn0; } }}算法功能：刪除根結(jié)點為x的子樹，若刪除成功則返回1，否則返回06.5

線索二叉樹

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

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA空指針的個數(shù)=n+1ABCDEFGHKABECDFGHK

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

C^^B

E^ABCDEFGHKABECDFGHK

^^^^^^^^^^①每個結(jié)點增加兩個域：fwd和bwd；存放前驅(qū)指針存放后繼指針如何預(yù)存這類信息？有兩種解決方法：②與原有的左右孩子指針域“復(fù)用”，充分利用那n+1個空鏈域。規(guī)定：1）若結(jié)點有左子樹，則lchild指向其左孩子；否則，lchild指向其直接前驅(qū)(即線索)；2）若結(jié)點有右子樹，則rchild指向其右孩子；否則，rchild指向其直接后繼(即線索)

。datalchildrchildfwdbwddatalchildrchild缺點：空間效率太低！問題：計算機如何判斷是孩子指針還是線索指針？如何區(qū)別？lchildLTagdataRTagrchild約定:當(dāng)Tag域為0時,表示正常情況;當(dāng)Tag域為1時,表示線索情況.前驅(qū)(后繼)左(右)孩子問：增加了前驅(qū)和后繼等線索有什么好處？——能方便找出當(dāng)前結(jié)點的前驅(qū)和后繼，不用堆棧（遞歸）也能遍歷整個樹。各1bit如何區(qū)分是子樹還是線索？

線索方法：利用二叉樹的空指針來記錄線索假設(shè)二叉樹有N個結(jié)點，于是有N+1個空指針，所以可以記錄N+1個線索。要記錄所有的線索，需要2N個指針，因此，這種線索方法，只是記錄了部分線索。結(jié)點的左子樹為空，則左指針記錄該結(jié)點的前驅(qū)線索。結(jié)點的右子樹為空，則右指針記錄該結(jié)點的后繼線索。typedef

struct

BiThrNod

{

TElemTypedata;

struct

BiThrNode

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

PointerThr

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

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

typedef

enum

{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索ABCGEIDHFroot懸空？

NIL懸空？NIL解：對該二叉樹中序遍歷的結(jié)果為:

H,D,I,B,E,A,F,C,G所以添加線索應(yīng)當(dāng)按如下路徑進行：為避免懸空態(tài)，應(yīng)增設(shè)一個頭結(jié)點例：畫出以下二叉樹對應(yīng)的中序線索二叉樹。線索二叉樹的生成——線索化線索化過程就是在遍歷過程中修改空指針的過程00A00C00B11E11F11G00D11I11H注：此圖中序遍歷結(jié)果為:H,D,I,B,E,A,F,C,G0T0對應(yīng)的中序線索二叉樹存儲結(jié)構(gòu)如圖所示：二、線索鏈表的遍歷算法:

for(p=

firstNode(T);p;p=Succ(p))Visit(p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。例如:

對中序線索化鏈表的遍歷算法

※中序遍歷的第一個結(jié)點？

※在中序線索化鏈表中結(jié)點的后繼？左子樹上處于“最左下”（沒有左子樹）的結(jié)點。若無右子樹，則為后繼線索所指結(jié)點；否則為對其右子樹進行中序遍歷時訪問的第一個結(jié)點。void

InOrderTraverse_Thr(BiThrTreeT,

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

while(p!=T){

//空樹或遍歷結(jié)束時，p==Twhile(p->LTag==Link)p=p->lchild;//第一個結(jié)點

if(!Visit(p->data))returenERROR;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//訪問后繼結(jié)點

}p=p->rchild;//p進至其右子樹根

}}//InOrderTraverse_Thr在中序遍歷過程中修改結(jié)點的左、右指針域，以保存當(dāng)前訪問結(jié)點的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點的前驅(qū)。三、如何建立線索鏈表？按中序建立線索鏈表（按中序線索化二叉樹）

1、若結(jié)點沒有左子樹，則令其左指針指向它的“前驅(qū)”并將左指針類型標(biāo)志改為“1”；

2、若結(jié)點沒有右子樹，則令其右指針指向它的“后繼”并將右指針類型標(biāo)志改為“1”；

－＋

a

×

b－

c

d／

e

fT

void

InThreading(BiThrTreep)

{

if(p){//對以p為根的非空二叉樹進行線索化

InThreading(p->lchild);

//左子樹線索化

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

//右子樹線索化

}//if}//InThreadingStatus

InOrderThreading(BiThrTree

&Thrt,

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

if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

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

Thrt->rchild=Thrt;

//添加頭結(jié)點

returnOK;}//InOrderThreading

……if(!T)

Thrt->lchild=Thrt;

else{

Thrt->lchild=T;

pre=Thrt;

InThreading(T);

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

pre->RTag=Thread;

Thrt->rchild=pre;

}StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt－>LTag=0;Thrt－>RTag=1;//

建頭結(jié)點

Thrt

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

if(!T)Thrt

－>lchild=Thrt;//若二叉樹空，則左指針回指

else{Thrt

－>lchild=T;pre=Thrt;

InThreading(T);//中序遍歷進行中序線索化

pre－>rchild=Thrt;pre－>RTag=1;//最后一個結(jié)點線索化

Thrt

－>rchild=pre;}

returnOK;

}//InOrderThreadingvoidInThreading(BiThrTreep){

if(p){InThreading(p－>lchild);//左子樹線索化

if(!p－>

lchild){p－>

LTag=1;p－>

lchild=pre;}

if(!pre－>

rchild){pre－>

RTag=1;pre－>

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

InThreading(p－>

rchild);}

//右子樹線索化

}

}//InThreading

－＋

a

×

b－

c

d／

e

f111111111111T

0Thrt

pre

▲StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt－>LTag=0;Thrt－>RTag=1;//

建頭結(jié)點

Thrt

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

if(!T)Thrt

－>lchild=Thrt;//若二叉樹空，則左指針回指

else{Thrt

－>lchild=T;pre=Thrt;

InThreading(T);//中序遍歷進行中序線索化

pre－>rchild=Thrt;pre－>RTag=1;//最后一個結(jié)點線索化

Thrt

－>rchild=pre;}

returnOK;

}//InOrderThreading－＋

a

×

b－

c

d／

e

f1111111111111T

0Thrt

pre

dataAGEIDJHCFBLtag0011110101Rtag0001010111AGEIDJHCFB例：帶了兩個標(biāo)志的某先序遍歷結(jié)果如下表所示，請畫出對應(yīng)的二叉樹。ATag=1表示線索:Ltag=1表示前驅(qū)Rtag=1表示后繼

6.6樹和森林的表示方法樹的四種存儲結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法四：樹的存儲結(jié)構(gòu)（孩子存儲）樹的存儲結(jié)構(gòu)之一（雙親存儲）1、存儲方式：用任意空間單元來存放樹的各個元素，在存放的同時還存放其雙親的位置?！?.……..dataparentdataparent

編號ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent特點：求雙親容易，求孩子難

typedef

struct

PTNode

{

Elemdata;

intparent;//雙親位置域

}

PTNode;

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

struct{

PTNodenodes[MAX_TREE_SIZE];

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

}

PTree;樹結(jié)構(gòu):存儲方式：用連續(xù)單元空間來存放樹的各個元素，在存放該元素的同時還存放所有孩子的存儲地址（鏈表）。……..……..

sonlinkdatanext

snopdata:數(shù)據(jù)元素的值sonlink:指針，第一個孩子的結(jié)點。snop:孩子的存儲位置next:下一個孩子的結(jié)點二、孩子鏈表表示法:ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7

datafirstchild

123456-1000224特點：求孩子、找兄弟容易，但求雙親難typedef

struct

CTNode

{

intchild;

struct

CTNode

*next;

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

childnextC語言的類型描述:

typedef

struct{

Elemdata;

intparent;

ChildPtr

firstchild;//孩子鏈的頭指針

}

CTBox;雙親結(jié)點結(jié)構(gòu)

datafirstchildtypedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

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

}

CTree;樹結(jié)構(gòu):存儲方式：用任意空間單元來存放樹的各個元素，在存放該元素的同時還存放第一個孩子的存儲地址。和右兄弟的存儲地址。datafchnsibdata:數(shù)據(jù)元素的值fch:指針，指向第一個兒子結(jié)點nsib:指針，指向其右兄弟結(jié)點三、樹的二叉鏈表(孩子-兄弟）存儲表示法ABCDEFG

ABCE