數(shù)據(jù)結(jié)構(gòu)：二叉樹及遍歷

6.2二叉樹概念和性質(zhì)6.2.1二叉樹概念6.2.2二叉樹性質(zhì)6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)6.2.1二叉樹定義度不大于2的有序樹。

是n0個(gè)結(jié)點(diǎn)的有窮集合K與K上關(guān)系的集合R構(gòu)成的結(jié)構(gòu)。當(dāng)n=0時(shí)，稱該二叉樹為空二叉樹；否則，它為包含了一個(gè)根結(jié)點(diǎn)以及兩棵不相交的、分別稱之為左子樹與右子樹的二叉樹。

二叉樹遞歸定義二叉樹是有序樹

二叉樹有五種基本形態(tài),如下圖所示,任何復(fù)雜的二叉樹都是這五種基本形態(tài)的復(fù)合。

1.度為2的是二叉樹。樹結(jié)論:子樹有嚴(yán)格的左右之分且度≤2的樹是二叉樹。下面兩種說(shuō)法正確與否?應(yīng)該怎樣說(shuō)才合適?

2.具有三個(gè)結(jié)點(diǎn)的可以有以下五種形態(tài):樹

結(jié)論:具有三個(gè)結(jié)點(diǎn)的樹只有兩種形態(tài)。結(jié)點(diǎn)數(shù)為3的二叉樹有三種形態(tài)：二叉樹的主要術(shù)語(yǔ)雙親右孩子左孩子葉子根葉子

是沒(méi)有孩子的結(jié)點(diǎn)。

從定義看到，二叉樹是一種特殊的樹，其表示法也與樹的表示法一樣，有樹形表示法、文氏圖表示法、凹入表示法和括號(hào)表示法等。二叉樹的表示

在一棵二叉樹中,如果所有分支結(jié)點(diǎn)都有左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn),并且葉子結(jié)點(diǎn)都集中在二叉樹的最下一層，這樣的二叉樹稱為滿二叉樹。下圖所示就是一棵滿二叉樹?？梢詫?duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),約定編號(hào)從樹根為1開(kāi)始,按照層數(shù)從小到大、同一層從左到右的次序進(jìn)行。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。兩種特殊形態(tài)的二叉樹

若二叉樹中最多只有最下面兩層的結(jié)點(diǎn)的度數(shù)可以小于2,并且最下面一層的葉結(jié)點(diǎn)都依次排列在該層最左邊的位置上,則這樣的二叉樹稱為完全二叉樹。如下圖所示為一棵完全二叉樹。同樣可以對(duì)完全二叉樹中每個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào),編號(hào)的方法同滿二叉樹相同。圖中每個(gè)結(jié)點(diǎn)外邊的數(shù)字為對(duì)該結(jié)點(diǎn)的編號(hào)。滿二叉樹完全二叉樹6.2.2二叉樹性質(zhì)1.具有n個(gè)結(jié)點(diǎn)的非空二叉樹共有n–1個(gè)分支。證明:

除了根結(jié)點(diǎn)以外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)雙親結(jié)點(diǎn)，即每個(gè)結(jié)點(diǎn)與其雙親結(jié)點(diǎn)之間僅有一個(gè)分支存在，因此，具有n個(gè)結(jié)點(diǎn)的非空二叉樹的分支總數(shù)為n–1。證明(采用歸納法)(1).當(dāng)i=1時(shí),結(jié)論顯然正確。非空二叉樹的第1層有且僅有一個(gè)結(jié)點(diǎn),即樹的根結(jié)點(diǎn).(2).假設(shè)對(duì)于第j層(1ji–1)結(jié)論也正確,即第j層最多有2j-1個(gè)結(jié)點(diǎn).(3).由定義可知,二叉樹中每個(gè)結(jié)點(diǎn)最多只能有兩個(gè)孩子結(jié)點(diǎn)。若第i–1層的每個(gè)結(jié)點(diǎn)都有兩棵非空子樹,則第i層的結(jié)點(diǎn)數(shù)目達(dá)到最大.而第i–1層最多有2i–2個(gè)結(jié)點(diǎn)已由假設(shè)證明,于是,

應(yīng)有

22i–2=2i–12.

非空二叉樹的第i層最多有2i–1個(gè)結(jié)點(diǎn)(i1)。證明:

由性質(zhì)1可知,若深度為h的二叉樹的每一層的結(jié)點(diǎn)數(shù)目都達(dá)到各自所在層的最大值,則二叉樹的結(jié)點(diǎn)總數(shù)一定達(dá)到最大。即有

20+21+22+…+2i-1+…+2h-1=2h-13.

深度為h的非空二叉樹最多有2h–1個(gè)結(jié)點(diǎn)。4.

若非空二叉樹有n0個(gè)葉結(jié)點(diǎn),有n2個(gè)度為2的結(jié)點(diǎn),則

n0=n2+1證明:

設(shè)該二叉樹有n1個(gè)度為1的結(jié)點(diǎn),結(jié)點(diǎn)總數(shù)為n,有

n=n0+n1+n2

--------(1)

設(shè)二叉樹的分支數(shù)目為B，根據(jù)性質(zhì)1，有

B=n-1

--------(2)

這些分支來(lái)自度于為1的結(jié)點(diǎn)與度為2結(jié)點(diǎn),即：

B=n1+2n2

---------(3)聯(lián)列關(guān)系(1),(2)與(3),可得到

n0=n2+15.具有n個(gè)結(jié)點(diǎn)的非空完全二叉樹的深度為

h=log2n+1.證明：設(shè)所求完全二叉樹的深度為k由性質(zhì)2和完全二叉樹的定義知：

2k-1-1＜n≤2k-1

由此可以推出：2k-1≤n＜2k取對(duì)數(shù)得：k-1≤log2n＜k由于k為整數(shù)，故有k-1=log2n

即：k=log2n+1

k層的最多結(jié)點(diǎn)數(shù)k-1層的最多結(jié)點(diǎn)數(shù)

性質(zhì)6:如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(其深度為log2n+1)的結(jié)點(diǎn)按層序編號(hào)(從第一層到第log2n+1層，每層從左到右)，則對(duì)任一結(jié)點(diǎn)i(1in)，有：

(1)若i＝1，則i為根，無(wú)雙親，若i>1，則雙親為i/2(2)若2i>n，則i無(wú)左孩子，否則i的左孩子為2i。

(3)若2i+1>n，則i無(wú)右孩子，否則i的右孩子為2i+1。編號(hào)i=4雙親為i/2=2左子樹為2i=8右子樹為2i+1=9i=1只有根結(jié)點(diǎn)編號(hào)i=5雙親為i/2=2左子樹為2i=10右子樹為2i+1=11i=8,2i>n無(wú)左子樹151234567891011121314通過(guò)性質(zhì)6把非線性結(jié)構(gòu)輕易轉(zhuǎn)化成了線性結(jié)構(gòu)。6.2.3二叉樹存儲(chǔ)結(jié)構(gòu)

二叉樹的順序存儲(chǔ)結(jié)構(gòu)

二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(1)二叉樹的順序存儲(chǔ)結(jié)構(gòu)

根據(jù)完全二叉樹的性質(zhì)6,對(duì)于深度為h的完全二叉樹,將樹中所有結(jié)點(diǎn)的數(shù)據(jù)信息按照編號(hào)的順序依次存儲(chǔ)到一維數(shù)組BT[1:2h-1]中,由于編號(hào)與數(shù)組下標(biāo)一一對(duì)應(yīng),該數(shù)組就是該完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)。1.完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)#defineMaxTree100typedef

TElemType

SqBiTree[MaxTree];SqBiTree

bt;ABCDEFGHIJK123456789101112131415采用一維數(shù)組，按層序順序依次存儲(chǔ)二叉樹的每一個(gè)結(jié)點(diǎn)。如下圖所示：利用性質(zhì)6實(shí)現(xiàn)線性結(jié)構(gòu)和非線性結(jié)構(gòu)的靈活轉(zhuǎn)換。ABCDEFGHJI2.一般二叉樹的順序存儲(chǔ)結(jié)構(gòu)12345678910111213BT[1:15]123456789101112131415ABCDEFGHJ

I“完全二叉樹”通過(guò)虛設(shè)部分結(jié)點(diǎn)，使其變成相應(yīng)的完全二叉樹。

對(duì)于一般二叉樹,只須在二叉樹中“添加”一些實(shí)際上二叉樹中并不存在的“虛結(jié)點(diǎn)”(可以認(rèn)為這些結(jié)點(diǎn)的數(shù)據(jù)信息為空),使其在形式上成為一棵“完全二叉樹”,然后按照完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)的構(gòu)造方法將所有結(jié)點(diǎn)的數(shù)據(jù)信息依次存放于數(shù)組BT[1:2h-1]中。結(jié)論(2)二叉鏈表存儲(chǔ)結(jié)構(gòu)結(jié)點(diǎn)的結(jié)構(gòu)如下:

typedef

structnode{

ElemTypedata;

structnode*lchild,*rchild;}BTNode,*BiTree;

其中：data表示值域，用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素,lchild和rchild分別表示左指針域和右指針域，用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)(即左、右子樹的根結(jié)點(diǎn))的存儲(chǔ)位置。二叉樹及其二叉鏈表存儲(chǔ)結(jié)構(gòu)

ABCD

EF

123456789101112131415G

兩種存儲(chǔ)結(jié)構(gòu)的轉(zhuǎn)換(c)下面根據(jù)二叉樹的順序存儲(chǔ)結(jié)構(gòu)畫出其二叉鏈表存儲(chǔ)結(jié)構(gòu)6.3二叉樹的遍歷6.3.1二叉樹遍歷的概念6.3.2二叉樹遍歷的遞歸算法6.3.3層次遍歷二叉樹遍歷算法6.3.4遞歸遍歷二叉樹的應(yīng)用6.3.5二叉樹遍歷的非遞歸算法6.3.1二叉樹遍歷的概念（1）何謂“遍歷二叉樹”？二叉樹的遍歷是指按照一定次序訪問(wèn)樹中所有結(jié)點(diǎn),并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次的過(guò)程。

“遍歷”是二叉樹其他各種算法的基礎(chǔ)。（2）如何遍歷二叉樹？二叉樹是一種非線性結(jié)構(gòu)，而遍歷的結(jié)果是一個(gè)線性的結(jié)點(diǎn)序列。

考慮二叉樹的結(jié)構(gòu)…

根據(jù)二叉樹的結(jié)構(gòu)，分為三部分：

L左子樹

D根結(jié)點(diǎn)

R右子樹DLR

A

F

G

E

D

C

B（3）遍歷二叉樹的方法先序遍歷DLR

中序遍歷LDR

后序遍歷LRD由于左右子樹也是二叉樹，屬于遞歸結(jié)構(gòu)，所以常借助遞歸算法實(shí)現(xiàn)先序、中序和后序遍歷。先序遍歷若被遍歷的二叉樹非空,則：

(1)訪問(wèn)根結(jié)點(diǎn)；

(2)先序遍歷左子樹；

(3)先序遍歷右子樹。BACDEFGHBACDEFGH先序序列：ABCDEFGH先序序列：-+a*b-cd/ef練習(xí)1：先序序列：abdefcg練習(xí)2：練習(xí)3：先序序列：abdgcefhi中序遍歷若被遍歷的二叉樹非空,則：(1)中序遍歷左子樹；(2)訪問(wèn)根結(jié)點(diǎn)；(3)中序遍歷右子樹。BACDEFGHBACDEFGH中序序列：BDCEAGHF中序序列：a+b*c-d-e/f練習(xí)1：中序序列：dfebagc練習(xí)2：練習(xí)3：中序序列：dgbaechif后序遍歷若被遍歷的二叉樹非空,則：(1)后序遍歷左子樹；(2)后序遍歷右子樹；(3)訪問(wèn)根結(jié)點(diǎn)。BACDEFGHBACDEFGH后序序列：DECBHGFA后序序列：abcd-*+ef/-練習(xí)1：后序序列：fedbgca練習(xí)2：練習(xí)3：后序序列：gdbeihfca層次遍歷從第一層開(kāi)始，同一層從左到右。一般借助隊(duì)列進(jìn)行層次遍歷。BACDEFGHBACDEFGHABFCGDEH6.3.2二叉樹遍歷的遞歸算法

由二叉樹的先序、中序和后序遍歷過(guò)程直接得到如下三種遞歸算法如下：

void

PreOrder(BiTreeb) //先序遍歷的遞歸算法

{if(b!=NULL){visit(b->data);//訪問(wèn)根結(jié)點(diǎn)

PreOrder(b->lchild);

PreOrder(b->rchild);}}

void

InOrder(BiTreeb) //中序遍歷的遞歸算法

{if(b!=NULL){InOrder(b->lchild);

visit(b->data);//訪問(wèn)根結(jié)點(diǎn)

InOrder(b->rchild); }}

void

PostOrder(BiTreeb)//后序遍歷遞歸算法

{if(b!=NULL){PostOrder(b->lchild);

PostOrder(b->rchild);

visit(b->data);//訪問(wèn)根結(jié)點(diǎn)

}}∧e∧∧

a∧

+

*

//\d/\

-T∧

b∧∧

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

A

F

E

D

C

B小結(jié)（1）三種遞歸遍歷算法的搜索路線相同：從根結(jié)點(diǎn)出發(fā)，逆時(shí)針沿著二叉樹外緣移動(dòng)，對(duì)每個(gè)結(jié)點(diǎn)均途徑三次，最后回到根結(jié)點(diǎn)。

（2）在搜索路線中，若訪問(wèn)結(jié)點(diǎn)均是第一次經(jīng)過(guò)該結(jié)點(diǎn)時(shí)進(jìn)行的，則是先序遍歷；若訪問(wèn)結(jié)點(diǎn)均是在第二次(或第三次)經(jīng)過(guò)結(jié)點(diǎn)時(shí)進(jìn)行的，則是中序遍歷(或后序遍歷)。只要將搜索路線上所有在第一次、第二次和第三次經(jīng)過(guò)的結(jié)點(diǎn)分別列表，即可分別得到該二叉樹的先序序列、中序序列和后序序列。

（3）上述三種序列都是線性序列，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其余結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。為了區(qū)別于樹形結(jié)構(gòu)中前趨(即雙親)結(jié)點(diǎn)和后繼(即孩子)結(jié)點(diǎn)的概念，對(duì)上述三種線性序列，要在某結(jié)點(diǎn)的前趨和后繼之前冠以其遍歷次序名稱。6.3.3層次遍歷二叉樹算法void

LevelOrder(

BiTree

bt

){

InitQueue(Q);//初始化隊(duì)列

EnQueue(Q,bt);//根入隊(duì)

//隊(duì)列不空則繼續(xù)遍歷

while(!QueueEmpty(Q)){

//出隊(duì)列訪問(wèn)結(jié)點(diǎn)，并將左右子樹入隊(duì)列…

}}

//出隊(duì)列訪問(wèn)結(jié)點(diǎn)，并將左右子樹入隊(duì)列

DeQueue(Q,p);if(p!=NULL){visit(p->data);

//左、右子樹入隊(duì)列

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild);}6.3.4遍歷二叉樹的應(yīng)用

回顧：二叉樹有五種基本形態(tài)空二叉樹；只有根結(jié)點(diǎn)（左右子樹都為空）；只有左子樹（右子樹為空）；只有右子樹（左子樹為空）；左右子樹均不空。（1）求二叉樹中結(jié)點(diǎn)個(gè)數(shù)分析：①0②1③L+1④1+R⑤1+L+R簡(jiǎn)化：②1+L=0+R=0③1+L+R=0④1+L=0+R合并成1+L+R一種情況。算法：int

NodeCount

(BiTreeb){

if(b==NULL)return0;L=NodeCount(b->lchild);R=NodeCount

(b->rchild);return1+L+R;}（2）求葉子結(jié)點(diǎn)個(gè)數(shù)分析：①0;②1;③L;④R;⑤L+R。簡(jiǎn)化：③④⑤可合并成⑤。

算法:int

LeafCount

(BiTreeb){ if(b==NULL)return0;

if(b->lchild==NULL&&b->rchild==NULL)

return1; L=LeafCount(b->lchild);R=LeafCount(b->rchild);return(L+R);}（3）求二叉樹的深度分析：①0;②1;③1+L;④1+R;⑤1+max(L,R)。簡(jiǎn)化：②③④⑤可合并成⑤。算法:int

Depth(BiTree

bt){if(bt==NULL)return0;L=Depth(bt->lchild);R=Depth(bt->rchild);return1+max(L,R);}

（4）假設(shè)二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，輸出一棵給定二叉樹的所有葉子結(jié)點(diǎn)。解：輸出一棵二叉樹的所有葉子結(jié)點(diǎn)的遞歸模型f()如下：

f(b)：不做任何事件 若b=NULL

f(b)：輸出b結(jié)點(diǎn)的data域若b為葉子結(jié)點(diǎn)

f(b)：f(b->lchild);f(b->rchild)其他情況

voidDispLeaf(BiTreeb){if(b!=NULL){ if(b->lchild==NULL&&b->rchild==NULL)

printf("%c",b->data); else {DispLeaf(b->lchild);

DispLeaf(b->rchild);}}}以字符串的形式“根左子樹右子樹”定義一棵二叉樹以空白字符“

”表示例如:空樹只含一個(gè)根結(jié)點(diǎn)的二叉樹A

以字符串“A”表示ABCD以下列字符串表示ABCD(5)二叉樹的創(chuàng)建利用擴(kuò)展二叉樹的先序序列構(gòu)造二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)ATBCD^^^^^ABCDvoidCreateBiTree(BiTree*T,charPCTree[]){//利用擴(kuò)展二叉樹的先序序列構(gòu)造二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)

ch=

PCTree[i++];

if(ch!=‘\0’){if(ch==‘’)T=NULL;else{T=(BiTree)malloc(sizeof(BTNode)))T->data=ch;//生成根結(jié)點(diǎn)并賦值

CreateBiTree(T->lchild);//創(chuàng)建左子樹

CreateBiTree(T->rchild);//創(chuàng)建右子樹

}

}}//CreateBiTree

6.3.5遍歷二叉樹的非遞歸算法

一般借助一個(gè)結(jié)點(diǎn)指針棧來(lái)保存需要返回的結(jié)點(diǎn)指針，從而實(shí)現(xiàn)二叉樹遍歷。

結(jié)點(diǎn)指針棧的定義：

typedef

struct

StackNode{

BiTree

St[MAXSIZE];//結(jié)點(diǎn)指針棧

intTop=-1;//棧頂指針

}SqBStack;

SqBStack

S;

BiTree

p;//遍歷過(guò)程中使用的結(jié)點(diǎn)指針變量（1）先序遍歷

先序遍歷過(guò)程為：先訪問(wèn)根結(jié)點(diǎn)，再訪問(wèn)左子樹，最后訪問(wèn)右子樹。先序遍歷的非遞歸算法思想為：根結(jié)點(diǎn)指針進(jìn)棧；當(dāng)棧不空時(shí)，循環(huán)執(zhí)行如下操作：出棧P，訪問(wèn)*P；將P的右孩子指針進(jìn)棧；將P的左孩子指針進(jìn)棧。void

Preorder(BiTreeb){

InitStack(S);//初始化二叉樹結(jié)點(diǎn)指針棧

Push(S,b);//根結(jié)點(diǎn)指針進(jìn)棧

while(!StackEmpty(S)){//棧不空

Pop(S,p);if(p){visit(p);Push(S,p->rchild);//右子樹進(jìn)棧

Push(S,p->lchild);//左子樹進(jìn)棧

}}}BACDEFGHBACDEFGH先序序列：ABCDEFGHtop二叉樹結(jié)點(diǎn)指針棧（2）中序遍歷根結(jié)點(diǎn)指針進(jìn)棧。當(dāng)棧不空時(shí)，循環(huán)執(zhí)行如下操作：當(dāng)棧頂結(jié)點(diǎn)指針?lè)强諘r(shí)，（應(yīng)遍歷其左子樹）將其左孩子指針進(jìn)棧。若棧頂結(jié)點(diǎn)指針為空時(shí)，棧頂?shù)目罩羔槼鰲?。若棧不空，棧頂?shù)慕Y(jié)點(diǎn)指針出棧，訪問(wèn)該結(jié)點(diǎn)，并將其右孩子指針進(jìn)棧。

中序遍歷過(guò)程為：先訪問(wèn)左子樹，再訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹。

中序遍歷的非遞歸算法思想為：voidInorder(BitreeT){

Initstack(S);Push(S,T);while(!StackEmpty(S)){

//左孩子進(jìn)棧，沿左孩子分支走到底直到最左邊的左孩子為空

while(Gettop(S,p))Push(S,p->lchild);

Pop(S,p);

//將棧頂空指針出棧，即最左邊的左孩子為空

if(!StackEmpty(S)){