第六章

二叉樹(shù)的遍歷及應(yīng)用本講內(nèi)容6.3遍歷二叉樹(shù)1.遍歷二叉樹(shù)的概念2.遍歷算法實(shí)現(xiàn)（遞歸算法和非遞歸算法）先序、中序、后序和層次遍歷3.遍歷算法的應(yīng)用舉例遍歷二叉樹(shù)遍歷二叉樹(shù)的概念遍歷二叉樹(shù)就是如何按某條搜索路徑巡訪(fǎng)二叉樹(shù)中的每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪(fǎng)問(wèn)一次，而且僅被訪(fǎng)問(wèn)一次。

如何確定搜索路徑？先上后下搜索先左后右搜索先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法先左后右的遍歷算法先序遍歷二叉樹(shù)遍歷策略若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）訪(fǎng)問(wèn)根結(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。ABCDEGHFABDEGCFH

遞歸算法先序遍歷二叉樹(shù)的遞歸算法實(shí)現(xiàn)void

PreOrder(BiTreeT){if(T){ //如果樹(shù)不為空 visit(T->data

);//輸出根結(jié)點(diǎn)

PreOrder(T->lchild);//先序遍歷左子樹(shù)

PreOrder

(T->rchild);//先序遍歷右子樹(shù)}}中序遍歷二叉樹(shù)遍歷策略若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）中序遍歷左子樹(shù)；（2）訪(fǎng)問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。ABCDEGHFDBGEAFHC遞歸算法中序遍歷二叉樹(shù)的遞歸算法實(shí)現(xiàn)void

InOrder(BiTreeT){if(T){ //如果樹(shù)不為空

InOrder(T->lchild);//中序遍歷左子樹(shù) visit(T->data

);//輸出根結(jié)點(diǎn)

InOrder

(T->rchild);//中序遍歷右子樹(shù)}}后序遍歷二叉樹(shù)遍歷策略若二叉樹(shù)為空樹(shù)，則空操作；否則，（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪(fǎng)問(wèn)根結(jié)點(diǎn)。ABCDEGHFDGEBHFCA遞歸算法后序遍歷二叉樹(shù)的遞歸算法實(shí)現(xiàn)void

PastOrder(BiTreeT){if(T){ //如果樹(shù)不為空

PastOrder(T->lchild);//后序遍歷左子樹(shù)

PastOrder

(T->rchild);//后序遍歷右子樹(shù) visit(T->data

);//輸出根結(jié)點(diǎn)}}層次遍歷二叉樹(shù)遍歷策略采用“自上而下，自左而右”的方法訪(fǎng)問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，即從第一層開(kāi)始，依次訪(fǎng)問(wèn)二叉樹(shù)中每一層的結(jié)點(diǎn)，同一層中按照先訪(fǎng)問(wèn)左孩子再訪(fǎng)問(wèn)右孩子的順序訪(fǎng)問(wèn)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)均被訪(fǎng)問(wèn)，此種遍歷需要借助于隊(duì)列來(lái)完。ABCDEGHFABCDEFGH層次遍歷二叉樹(shù)的非遞歸算法實(shí)現(xiàn)voidLevelOrder(BinTreeT){ InitQueue(Q); //隊(duì)列初始化為空

EnQueue

(Q,T); //根入隊(duì)列

while(!QueueEmpty(Q)){

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

DeQueue(Q,p);

if(p!=NULL){

visit(p->data);

EnQueue(Q,p->lchild);//左孩子入隊(duì)列

EnQueue(Q,p->rchild);//右孩子入隊(duì)列

}

}}首先將根入隊(duì)列，以后若隊(duì)列不空則出隊(duì)頭元素p，如果p不空，則訪(fǎng)問(wèn)之。然后將其左右孩子入隊(duì)列，如此循環(huán)直到隊(duì)列為空。

遍歷算法的應(yīng)用舉例1.統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)2.統(tǒng)計(jì)二叉樹(shù)中總結(jié)點(diǎn)的個(gè)數(shù)3.求二叉樹(shù)的深度4.建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)5.交換二叉樹(shù)的左右子樹(shù)6.根據(jù)遍歷序列畫(huà)對(duì)應(yīng)二叉樹(shù)統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)算法思想分別求出左子樹(shù)、右子樹(shù)的葉子數(shù)，然后相加。根據(jù)二叉樹(shù)的五種基本形態(tài)知：空二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為0；

只有根的二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為1；

只有左子樹(shù)的二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為左子樹(shù)中葉子結(jié)點(diǎn)數(shù)；只有右子樹(shù)的二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)為右子樹(shù)中葉子結(jié)點(diǎn)數(shù)；具有左右子樹(shù)的二叉樹(shù)，葉子結(jié)點(diǎn)數(shù)等于左子樹(shù)中葉子結(jié)點(diǎn)數(shù)、右子樹(shù)中的葉子結(jié)點(diǎn)數(shù)之和。遞歸算法實(shí)現(xiàn)int

CountLeaf(BiTreeT){

if(!T) return0;

elseif((!T->lchild)&&(!T->rchild))

return

1;

else{

nl=CountLeaf(T->lchild); nr=CountLeaf(T->rchild);

returnnl+nr;

}//if}//CountLeaf空樹(shù)只有根左子樹(shù)右子樹(shù)統(tǒng)計(jì)二叉樹(shù)中總結(jié)點(diǎn)的個(gè)數(shù)算法思想分別求出左子樹(shù)、右子樹(shù)的總結(jié)點(diǎn)數(shù)，然后與根求和。根據(jù)二叉樹(shù)的五種基本形態(tài)知：空二叉樹(shù)，結(jié)點(diǎn)數(shù)為0；

只有根的二叉樹(shù)，結(jié)點(diǎn)數(shù)為1；

只有左子樹(shù)的二叉樹(shù)，結(jié)點(diǎn)數(shù)為左子樹(shù)中結(jié)點(diǎn)數(shù)加上根；只有右子樹(shù)的二叉樹(shù)，結(jié)點(diǎn)數(shù)為右子樹(shù)中結(jié)點(diǎn)數(shù)加上根；具有左右子樹(shù)的二叉樹(shù)，結(jié)點(diǎn)數(shù)等于左子樹(shù)中結(jié)點(diǎn)數(shù)、右子樹(shù)中的結(jié)點(diǎn)數(shù)加上根之和。遞歸算法實(shí)現(xiàn)int

NodeCount(BinTreeT){

if(!T) return

0;

else{

nl=

NodeCount(T->lchild); nr=NodeCount(T->rchild); return

1+nl+nr;

}//if}空樹(shù)左子樹(shù)右子樹(shù)求二叉樹(shù)的深度算法思想二叉樹(shù)的深度應(yīng)為其左、右子樹(shù)深度的最大值加1。根據(jù)二叉樹(shù)的五種基本形態(tài)知：空二叉樹(shù)，深度為0；

只有根的二叉樹(shù)，深度為1；

只有左子樹(shù)的二叉樹(shù)，深度為左子樹(shù)的深度加1；只有右子樹(shù)的二叉樹(shù)，深度為右子樹(shù)的深度加1；具有左右子樹(shù)的二叉樹(shù)，深度等于左子樹(shù)的深度與右子樹(shù)的深度的最大值加1。遞歸算法實(shí)現(xiàn)int

Depth(BinTreeT){

if(!T) return

0;

else{

dl=

Depth(T->lchild); dr=Depth(T->rchild);

depth=1+(dl>dr?dl:dr);

}

return

depth;}空樹(shù)左子樹(shù)右子樹(shù)建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉樹(shù)針對(duì)不同的定義形式對(duì)應(yīng)不同的建立存儲(chǔ)結(jié)構(gòu)的方法。以字符串的形式，按照先序遍歷思想，建立一棵二叉樹(shù)的二叉鏈表。以空白字符“”表示1.空樹(shù)2.只含一個(gè)根結(jié)點(diǎn)的二叉樹(shù)A以字符串“A”表示ABCDA(B(

,C(

,

)),D(

,

))以下列字符串表示遞歸算法實(shí)現(xiàn)voidCreateBiTree(BiTree&T){ scanf(“%c”,&ch);

if(ch==‘’)T=NULL;

else{

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

exit(overflow);

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

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

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

}}//CreateBiTreeAB

C

D

ABCD算法執(zhí)行過(guò)程舉例如下：ATBCD^^^^^交換二叉樹(shù)的左右子樹(shù)空樹(shù)不需要進(jìn)行任何交換操作；只有根的二叉樹(shù)交換后仍然只有根；只有左子樹(shù)的二叉樹(shù)，交換后變成只有右子樹(shù)的二叉樹(shù)；只有右子樹(shù)的二叉樹(shù)，交換后變成只有左子樹(shù)的二叉樹(shù)；具有左右子樹(shù)的二叉樹(shù)交換后，原左子樹(shù)變成右子樹(shù)，原右子樹(shù)變成左子樹(shù)。分別對(duì)于交換后的左子樹(shù)或右子樹(shù)重復(fù)進(jìn)行上述操作直到操作完成。算法思想遞歸算法實(shí)現(xiàn)voidchange(BinTree&T){

if(!T)returnT;

else{ t=T->lchild; T->lchild=T->rchild; T->rchild=t;

change(T->lchild); change(T->rchild);

}}

僅知二叉樹(shù)的先序序列“abcdefg”不能唯一確定一棵二叉樹(shù)，1.由先序和中序遍歷序列建立二叉樹(shù)

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

二叉樹(shù)的先序序列二叉樹(shù)的中序序列左子樹(shù)左子樹(shù)右子樹(shù)右子樹(shù)根根主要思想：先序序列中第一個(gè)為“根”，標(biāo)出之；在中序序列中標(biāo)出“根”，并分出左、右子樹(shù)；在先序序列中標(biāo)出左、右子樹(shù)；分別對(duì)左、右子樹(shù)重復(fù)以上步驟。abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列2.由后序和中序遍歷序列建立二叉樹(shù)二叉樹(shù)的后序序列二叉樹(shù)的中序序列左子樹(shù)右子樹(shù)根左子樹(shù)右子樹(shù)根主要思想：后序序列中第一個(gè)為“根”，標(biāo)出之；在中序序列中標(biāo)出“根”，并分出左、右子樹(shù)；在后序序列中標(biāo)出左、右子樹(shù)；分別對(duì)左、右子樹(shù)重復(fù)以上步驟。3.由后序和先序序列能否建立二叉樹(shù)？二叉樹(shù)的后序序列二叉樹(shù)的先序序列左子樹(shù)右子樹(shù)根左子樹(shù)右子樹(shù)根結(jié)論：不能唯一確定二叉樹(shù)！ABAB或例如：先序：AB后序：BA二叉樹(shù)遍歷的非遞歸算法遍歷二叉樹(shù)的非遞歸算法，一般借助于棧實(shí)現(xiàn)。仿照遞歸算法執(zhí)行過(guò)程中遞歸工作棧的狀態(tài)變化狀況可直接寫(xiě)出相應(yīng)的非遞歸算法。先序遍歷非遞歸算法中序遍歷非遞歸算法后序遍歷非遞歸算法先序遍歷的非遞歸算法實(shí)現(xiàn)思想首先，根結(jié)點(diǎn)先入棧。在棧不空的情況下出棧，若結(jié)點(diǎn)存在則訪(fǎng)問(wèn)結(jié)點(diǎn)，對(duì)于訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)便可以棄之不用，只要先將其右孩子入棧保存，再將其左孩子入棧保存即可。先序遍歷非遞歸算法舉例

ABCDEGHF

A

AC

BBE

D

D^^E^G

G^^C^FFH^H^^遍歷結(jié)果非遞歸算法實(shí)現(xiàn)——先序遍歷void

Preorder(BinTreebt,VisitFuncvisit){ InitStack(S);

Push(S,bt);

while(!StackEmpty(S)){

Pop(S,p);

if(p){

visit(p);

Push(S,p->rchild);

Push(S,p->lchild);

} }}中序遍歷的非遞歸算法實(shí)現(xiàn)思想實(shí)現(xiàn)中序遍歷二叉樹(shù)的非遞歸算法時(shí)，需要設(shè)一指針沿二叉樹(shù)中序順序移動(dòng)，每當(dāng)向上層移動(dòng)時(shí)就要出棧。指針p從根開(kāi)始，首先沿著左子樹(shù)向下移動(dòng)，同時(shí)入棧保存；當(dāng)?shù)竭_(dá)空子樹(shù)后需要退棧訪(fǎng)問(wèn)結(jié)點(diǎn)，然后移動(dòng)到右子樹(shù)上去。非遞歸算法實(shí)現(xiàn)——中序遍歷voidInOrder(BinTreebt,VisitFuncvisit){

InitStack(S); p=bt;

while(p||!StackEmpty(S)){

if(p){

Push(S,p);

p=p->lchild;

}else{

Pop(S,p);

visit(p);

p=p->rchild; } }}非空進(jìn)棧保存沿左子樹(shù)向下移動(dòng)為空向上移動(dòng)，出棧，訪(fǎng)問(wèn)結(jié)點(diǎn)移動(dòng)到右子樹(shù)上先序遍歷的非遞歸算法方法二實(shí)現(xiàn)思想修改前面介紹的中序遍歷二叉樹(shù)的非遞歸算法也可得到先序遍歷二叉樹(shù)的另一種非遞歸算法實(shí)現(xiàn)，即將訪(fǎng)問(wèn)結(jié)點(diǎn)的位置放在第一次指向該結(jié)點(diǎn)時(shí)。非遞歸算法——先序遍歷實(shí)現(xiàn)二voidPreOrder(BinTreebt,VisitFuncvisit){

InitStack(S); p=bt;

while(p||!StackEmpty(S)){

if(p){

visit(p);

Push(S,p);

p=p->lchild;

}else{

Pop(S,p);

p=p->rchild; } }}非空進(jìn)棧保存前，先訪(fǎng)問(wèn)沿左子樹(shù)向下移動(dòng)為空向上移動(dòng)，出棧移動(dòng)到右子樹(shù)上后序遍歷的非遞歸算法實(shí)現(xiàn)思想后序遍歷時(shí)，分別從左子樹(shù)和右子樹(shù)共兩次返回根結(jié)點(diǎn)，只有從右子樹(shù)返回時(shí)才訪(fǎng)