DS樹和二叉樹二叉樹的遍歷

會計學(xué)1DS樹和二叉樹二叉樹的遍歷本節(jié)內(nèi)容前序、中序、后序遍歷的過程前序、中序、后序遍歷的遞歸算法前序、中序、后序遍歷的非遞歸算法層序遍歷算法第1頁/共52頁6.3.1遍歷二叉樹

二叉樹的遍歷：是指從根結(jié)點出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次?？梢允菍Y(jié)點進(jìn)行的各種處理，一般簡化為輸出結(jié)點的值。前序遍歷中序遍歷后序遍歷層序遍歷第2頁/共52頁假設(shè)二叉樹的六種遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD如果限定先左后右，則遍歷方式有三種：DLR=>前序(或先序)LDR=>中序LRD

=>后序根結(jié)點D左子樹L右子樹R二叉樹二叉樹的遍歷方式第3頁/共52頁若二叉樹為空，則返回；否則：①訪問根結(jié)點；②前序遍歷根結(jié)點的左子樹；③前序遍歷根結(jié)點的右子樹。前序遍歷序列：ABCDEFG二叉樹的前序遍歷ABDGCEF第4頁/共52頁若二叉樹為空，則返回；否則：①中序遍歷根結(jié)點的左子樹；②訪問根結(jié)點；③中序遍歷根結(jié)點的右子樹。中序遍歷序列：DGBAECF二叉樹的中序遍歷ABCDEFG第5頁/共52頁若二叉樹為空，則返回；否則：①后序遍歷根結(jié)點的左子樹；②后序遍歷根結(jié)點的右子樹。③訪問根結(jié)點；后序遍歷序列：GDBEFCA二叉樹的后序遍歷ABCDEFG第6頁/共52頁從二叉樹的第一層（即根結(jié)點）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。ABCDEFG二叉樹的層序遍歷ABCDEFG層序遍歷序列：第7頁/共52頁例:先序遍歷序列（波蘭式）為：中序遍歷序列為：后序遍歷序列（逆波蘭式）為：-+a*b–cd/efa+b*c–d–e/fabcd-*+ef/-a+/-*efcdb-第8頁/共52頁Q:若已知一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？例如：已知一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI和BCAEDGHFI，如何構(gòu)造該二叉樹呢?第9頁/共52頁前序：ABCDEFG

HI中序：BCAEDGHFI前序：BC中序：BC

BCDEFGHIA前序：DEFGHI中序：EDGHFIABCDEFGHI第10頁/共52頁前序：FG

HI中序：GHFI前序：DEFGHI中序：EDGHFIABCDEFGHIABCDEFIGH第11頁/共52頁1.根據(jù)前序序列的第一個元素建立根結(jié)點；2.在中序序列中找到該元素，確定根結(jié)點的左右子樹的中序序列；3.在前序序列中確定左右子樹的前序序列；4.由左子樹的前序序列和中序序列建立左子樹；5.由右子樹的前序序列和中序序列建立右子樹。已知一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹的過程如下：第12頁/共52頁例：已知前序遍歷序列為ABC，后序遍歷序列為CBA，畫出滿足條件的二叉樹。則下列二叉樹都滿足條件。ABCABC第13頁/共52頁結(jié)論給定一棵二叉樹的前序和中序序列可以唯一確定此二叉樹給定一棵二叉樹的中序和后序序列可以唯一確定此二叉樹給定一棵二叉樹的前序和后序序列不能唯一確定此二叉樹第14頁/共52頁先序遍歷二叉樹的遞歸算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee))//二叉鏈表存儲結(jié)構(gòu)，visit是對數(shù)據(jù)元素操作的函數(shù)//先序遍歷二叉樹T的遞歸算法，對每個數(shù)據(jù)元素調(diào)用visit{

if(T)

{

if(Visit(T->data))//訪問當(dāng)前結(jié)點

if(PreOrderTraverse(T->lchild,Visit)//先序左子

if(PreOrderTraverser(T->rchild,Visit))

returnOK;//先序右子

returnERROR;}elsereturnOK;}第15頁/共52頁//最簡單的Visit函數(shù)是：輸出元素e的值StatusPrintElement(TElemTypee){ printf(e); //實現(xiàn)時，加上格式串returnOK;}//調(diào)用實例：PreOrderTraverse(T,PrintElement);第16頁/共52頁中序遍歷二叉樹的遞歸算法：StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T)

{

if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit))returnOK;returnERROR;

}elsereturnOK;}第17頁/共52頁后序遍歷二叉樹的遞歸算法：StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

if(T)

{if(PostOrderTraverse(T->lchild,Visit))

if(PostOrderTraverse(T->rchild,Visit))if(Visit(T->data))returnOK;returnERROR;

}elsereturnOK;}第18頁/共52頁中序遍歷的執(zhí)行過程第19頁/共52頁void

PreOrder(BiTreeT){if(T){

printf(T->data);

//訪問結(jié)點

PreOrder(T->lchild);

//先序左子PreOrder(T->rchild);

//先序右子}}void

InOrder(BiTreeT){if(T){InOrder(T->lchild);

//中序左子

printf(T->data);

//訪問結(jié)點InOrder(T->rchild);

//中序右子}}void

PostOrder(BiTreeT){if(T){PostOrder(T->lchild);

//后序左子PostOrder(T->rchild);

//后序右子

printf(T->data);

//訪問結(jié)點

}}三種遍歷的簡單寫法第20頁/共52頁2.遍歷算法的應(yīng)用舉例“遍歷”是二叉樹各種操作的基礎(chǔ)，可以在遍歷過程中對結(jié)點進(jìn)行各種操作，如：對于一棵已知樹求結(jié)點的雙親，求結(jié)點的孩子結(jié)點個數(shù)，判定結(jié)點所在的層次等，也可在遍歷過程中生成結(jié)點，建立二叉樹的存儲結(jié)構(gòu)。第21頁/共52頁例1：求二叉樹的深度intgetDepth(BiTreeT){intdepth,dLeft,dRight;if(!T)depth=0;else{dLeft=getDepth(T->lchild);dRight=getDepth(T->rchild);depth=(dLeft>=dRight)?(dLeft+1):(dRight+1);}returndepth;}第22頁/共52頁例2：統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)voidCountLeaf(BiTreeT,int&count){if(T)

{

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

{ ++count;

return; } CountLeaf(T->lchild,count);//統(tǒng)計左子樹葉子結(jié)點個數(shù) CountLeaf(T->rchild,count);//統(tǒng)計右子樹葉子結(jié)點個數(shù)}}count在調(diào)用此函數(shù)前已初始化為0第23頁/共52頁例3：按先序序列建立二叉樹的二叉鏈表已知先序序列：ABC#

#DE#G#

#F#

#

#（其中#表示空格字符）建立相應(yīng)的二叉鏈表。ABCEDGF第24頁/共52頁例3：按先序序列建立二叉樹的二叉鏈表//按先序序列輸入二叉樹中結(jié)點的值，空格字符表示空樹intCreateBiTree(BiTree&T){charch;scanf("%c",&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(-1);T->data=ch;//構(gòu)造根結(jié)點CreateBiTree(T->lchild);//構(gòu)造左子CreateBiTree(T->rchild);//構(gòu)造右子

}return0;}第25頁/共52頁從上述二叉樹遍歷的定義可知，三種遍歷算法不同之處僅在于訪問根結(jié)點和遍歷左、右子樹的先后關(guān)系。如果在算法中暫且抹去和遞歸無關(guān)的visit語句，則三個遍歷算法完全相同。由此，從遞歸執(zhí)行過程的角度來看先序、中序和后序遍歷也是完全相同的。第26頁/共52頁三種遍歷

過程示意圖向下的箭頭表示更深一層的遞歸調(diào)用，向上的箭頭表示從遞歸調(diào)用退出返回。虛線旁的三角形、圓形和方形內(nèi)的字符分別表示在先序、中序和后序遍歷過程中訪問結(jié)點時輸出的信息。只要沿虛線從1出發(fā)到2結(jié)束，將沿途所見的三角形（或圓形、方形）內(nèi)的字符記下，便得遍歷二叉樹的先序（或中序、后序）序列。第27頁/共52頁中序遍歷二叉樹的非遞歸算法遞歸算法雖然簡潔，但是有時程序設(shè)計不允許用遞歸，且遞歸效率不高，這時就存在如何把遞歸程序轉(zhuǎn)化成等價的非遞歸算法的問題。解決這個問題的關(guān)鍵是設(shè)置一個棧。仿照遞歸算法執(zhí)行過程中編譯棧的工作原理，可以寫出相應(yīng)的非遞歸算法。第28頁/共52頁訪問結(jié)點序列:B棧S內(nèi)容:D

A

B中序遍歷的非遞歸實現(xiàn),算法6.2

ADBC

NULL

D

NULL

NULL第29頁/共52頁訪問結(jié)點序列:棧S內(nèi)容:BD

A中序遍歷的非遞歸實現(xiàn),算法6.2

ADBCA

C

NULL

NULLC第30頁/共52頁1.棧s初始化，根指針進(jìn)棧；2.循環(huán)直到棧s為空2.1當(dāng)指向棧頂元素的指針p不空時循環(huán)2.1.1p->lchild壓棧；2.2空指針退棧2.3如果棧s不空，則2.3.1將棧頂元素彈出至p；

2.3.2訪問p->data;2.3.3p的右子樹壓棧；中序遍歷——非遞歸算法6.2（偽代碼）第31頁/共52頁中序遍歷二叉樹的非遞歸算法6.2//中序遍歷的非遞歸算法StatusInOrderTrav(BiTreeT){

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

while(!StackEmpty(S)){while((GetTop(S,p)&&p)

Push(S,p->lchild);//向左走到盡頭Pop(S,p);//空指針退棧if(!StackEmpty(S)){//棧非空，則出棧訪問結(jié)點，右子入棧Pop(S,p);printf(p->data);Push(S,p->rchild);}

}

returnOK;}第32頁/共52頁1.棧s初始化，p指向根結(jié)點；2.p非空或棧s非空時循環(huán)2.1如果p不空2.1.1p壓棧；2.1.2繼續(xù)遍歷p的左子樹（即p=p->lchild）;2.2否則2.2.1將棧頂元素彈出至p；

2.2.2輸出p->data;2.2.3準(zhǔn)備遍歷p的右子樹（即p=p->rchild）；中序遍歷——非遞歸算法6.3（偽代碼）第33頁/共52頁訪問結(jié)點序列:B棧S內(nèi)容:D

A

B中序遍歷的非遞歸實現(xiàn),算法6.3

ADBC

D第34頁/共52頁訪問結(jié)點序列:棧S內(nèi)容:BD

A中序遍歷的非遞歸實現(xiàn),算法6.3

ADBCA

CC第35頁/共52頁中序遍歷的非遞歸算法6.3StatusInOrderTrv(BiTreeT){

InitStack(S);p=T;while(p||!StackEmpty(S))

{

if(p){Push(S,p);p=p->lchild;

}

else{Pop(S,p);

printf(p->data)；p=p->rchild;

}}returnOK;}//根指針進(jìn)棧，遍歷左子//根指針退棧，訪問根結(jié)點，遍歷右子第36頁/共52頁1.棧s初始化，p指向根結(jié)點；2.p非空或棧s非空時循環(huán)2.1當(dāng)p不空時循環(huán)

2.1.1輸出p->data;2.1.2p壓棧；2.1.3繼續(xù)遍歷p的左子樹2.2如果棧s不空，則2.2.1將棧頂元素彈出至p；2.2.2準(zhǔn)備遍歷p的右子樹；前序遍歷——非遞歸算法（偽代碼）中序第37頁/共52頁訪問結(jié)點序列:A棧S內(nèi)容:BD

A

B前序遍歷的非遞歸實現(xiàn)

ADBC第38頁/共52頁訪問結(jié)點序列:A棧S內(nèi)容:BD

A前序遍歷的非遞歸實現(xiàn)

ADBC

D第39頁/共52頁訪問結(jié)點序列:A棧S內(nèi)容:BD

C前序遍歷的非遞歸實現(xiàn)

ADBCC第40頁/共52頁voidPreOrderTrv(BiTreeT){

InitStack(S);

BiTreep=T;

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

printf(p->data); Push(S,p);p=p->lchild;}if(!StackEmpty(S)){

Pop(S,p);

p=p->rchild;}}}第41頁/共52頁層序遍歷隊列Q初始化；2.如果二叉樹非空，將根指針入隊；3.循環(huán)直到隊列為空3.1隊頭元素出隊，q指向它；3.2訪問結(jié)點q；3.3若結(jié)點q有左子，則將左子指針入隊；3.4若結(jié)點q有右子，則將右子指針入隊；第42頁/共52頁//層序遍歷(利用隊列)voidLevelOrderTraverse(BiTreeT){

LinkQueueq;

BiTNode*p;if(T){InitQueue(q);//初始化隊列qEnQueue(q,T);//根指針入隊while(!QueueEmpty(q))//隊列非空，循環(huán){DeQueue(q,p);//隊頭元素出隊,賦給p

printf(p->data);//訪問p所指結(jié)點if(p->lchild!=NULL)//p有左子 EnQueue(q,p->lchild);//p的左子入隊if(p->rchild!=NULL)//p有右子 EnQueue(q,p->rchild);//p的右子入隊}printf("\n");}}第43頁/共52頁遍歷的復(fù)雜度分析遍歷算法的基本操作是訪問結(jié)點，則不論哪種遍歷算法，對于有n個結(jié)點的二叉樹，時間復(fù)雜度均為O(n)只要對每個結(jié)點的處理（函數(shù)Visit的執(zhí)行）時間是一個常數(shù)，那么遍歷二叉樹就可以在線性時間內(nèi)完成所需要的輔助空間為遍歷過程中棧的最大容量，即樹的深度最壞情況下具有n個結(jié)點的二叉樹高度為n，則所需要的空間復(fù)雜度為O(n)第44頁/共52頁習(xí)題6.27：假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK。畫出該二叉樹?！痉治觥坑上刃蛐蛄械玫礁Y(jié)點，然后由中序序列得到左右子樹的先序和中序序列。依次類推。JEBFAHDCGIK第45頁/共52頁作業(yè)6.146.276.286.296.42~6.446.47本周五下午實驗二叉樹的實現(xiàn)第46頁/共52頁習(xí)題按先序次序建立二叉樹的算法，原型說明：voidCreateBiTree(BiTree&T);2.二叉樹的打印，有縮進(jìn)，并旋轉(zhuǎn)了90度，本算法可以用于調(diào)試二叉樹處理程序。h為T所在層數(shù)。原型：voidprintBiTree(BiTreeT,inth);main函數(shù)里的調(diào)用語句為：BiTreeroot;printBiTree(root,0);第47頁/共52頁二叉樹的打印voidprintNode(TElemTypee,inth)

//打印結(jié)點的值e，結(jié)點的高度為h{ for(inti=0;i<h;++i)

printf("");

printf("