數(shù)據(jù)結(jié)構(gòu)二叉樹的遍歷及其他操作

第六章

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

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

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

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

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

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

PreOrder

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

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

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

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

InOrder

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

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

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

PastOrder

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

);//輸出根結(jié)點(diǎn)}}層次遍歷二叉樹遍歷策略采用“自上而下，自左而右”的方法訪問二叉樹中的所有結(jié)點(diǎn)，即從第一層開始，依次訪問二叉樹中每一層的結(jié)點(diǎn)，同一層中按照先訪問左孩子再訪問右孩子的順序訪問結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)均被訪問，此種遍歷需要借助于隊(duì)列來完。ABCDEGHFABCDEFGH層次遍歷二叉樹的非遞歸算法實(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不空，則訪問之。然后將其左右孩子入隊(duì)列，如此循環(huán)直到隊(duì)列為空。

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

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

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

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

只有左子樹的二叉樹，結(jié)點(diǎn)數(shù)為左子樹中結(jié)點(diǎn)數(shù)加上根；只有右子樹的二叉樹，結(jié)點(diǎn)數(shù)為右子樹中結(jié)點(diǎn)數(shù)加上根；具有左右子樹的二叉樹，結(jié)點(diǎn)數(shù)等于左子樹中結(jié)點(diǎn)數(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}空樹左子樹右子樹求二叉樹的深度算法思想二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。根據(jù)二叉樹的五種基本形態(tài)知：空二叉樹，深度為0；

只有根的二叉樹，深度為1；

只有左子樹的二叉樹，深度為左子樹的深度加1；只有右子樹的二叉樹，深度為右子樹的深度加1；具有左右子樹的二叉樹，深度等于左子樹的深度與右子樹的深度的最大值加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;}空樹左子樹右子樹建立二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹針對(duì)不同的定義形式對(duì)應(yīng)不同的建立存儲(chǔ)結(jié)構(gòu)的方法。以字符串的形式，按照先序遍歷思想，建立一棵二叉樹的二叉鏈表。以空白字符“”表示1.空樹2.只含一個(gè)根結(jié)點(diǎn)的二叉樹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)造左子樹

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

}}//CreateBiTreeAB

C

D

ABCD算法執(zhí)行過程舉例如下：ATBCD^^^^^交換二叉樹的左右子樹空樹不需要進(jìn)行任何交換操作；只有根的二叉樹交換后仍然只有根；只有左子樹的二叉樹，交換后變成只有右子樹的二叉樹；只有右子樹的二叉樹，交換后變成只有左子樹的二叉樹；具有左右子樹的二叉樹交換后，原左子樹變成右子樹，原右子樹變成左子樹。分別對(duì)于交換后的左子樹或右子樹重復(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);

}}

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

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

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根主要思想：先序序列中第一個(gè)為“根”，標(biāo)出之；在中序序列中標(biāo)出“根”，并分出左、右子樹；在先序序列中標(biāo)出左、右子樹；分別對(duì)左、右子樹重復(fù)以上步驟。abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列2.由后序和中序遍歷序列建立二叉樹二叉樹的后序序列二叉樹的中序序列左子樹右子樹根左子樹右子樹根主要思想：后序序列中第一個(gè)為“根”，標(biāo)出之；在中序序列中標(biāo)出“根”，并分出左、右子樹；在后序序列中標(biāo)出左、右子樹；分別對(duì)左、右子樹重復(fù)以上步驟。3.由后序和先序序列能否建立二叉樹？二叉樹的后序序列二叉樹的先序序列左子樹右子樹根左子樹右子樹根結(jié)論：不能唯一確定二叉樹！ABAB或例如：先序：AB后序：BA二叉樹遍歷的非遞歸算法遍歷二叉樹的非遞歸算法，一般借助于棧實(shí)現(xiàn)。仿照遞歸算法執(zhí)行過程中遞歸工作棧的狀態(tài)變化狀況可直接寫出相應(yīng)的非遞歸算法。先序遍歷非遞歸算法中序遍歷非遞歸算法后序遍歷非遞歸算法先序遍歷的非遞歸算法實(shí)現(xiàn)思想首先，根結(jié)點(diǎn)先入棧。在棧不空的情況下出棧，若結(jié)點(diǎn)存在則訪問結(jié)點(diǎn)，對(duì)于訪問過的結(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è)一指針沿二叉樹中序順序移動(dòng)，每當(dāng)向上層移動(dòng)時(shí)就要出棧。指針p從根開始，首先沿著左子樹向下移動(dòng)，同時(shí)入棧保存；當(dāng)?shù)竭_(dá)空子樹后需要退棧訪問結(jié)點(diǎn)，然后移動(dòng)到右子樹上去。非遞歸算法實(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)棧保存沿左子樹向下移動(dòng)為空向上移動(dòng)，出棧，訪問結(jié)點(diǎn)移動(dòng)到右子樹上先序遍歷的非遞歸算法方法二實(shí)現(xiàn)思想修改前面介紹的中序遍歷二叉樹的非遞歸算法也可得到先序遍歷二叉樹的另一種非遞歸算法實(shí)現(xià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)棧保存前，先訪問沿左子樹向下移動(dòng)為空向上移動(dòng)，出棧移動(dòng)到右子樹上后序遍歷的非遞歸算法實(shí)現(xiàn)思想后序遍歷時(shí)，分別從左子樹和右子樹共兩次返回根結(jié)點(diǎn)，只有從右子樹返回時(shí)才訪