數(shù)據(jù)結(jié)構(gòu)第13講-遍歷二叉樹

1、第6章 樹和二叉樹6.1 樹的定義和基本術(shù)語6.2 二叉樹6.3 遍歷二叉樹和線索二叉樹 6.3.1 遍歷二叉樹 6.3.2 線索二叉樹6.4 樹和森林6.6 赫夫曼樹及其應(yīng)用6.3.1 遍歷二叉樹 在二叉樹的一些應(yīng)用中，常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。這就提出了遍歷二叉樹的問題。提出問題：“遍歷”是任何類型均有的操作 對線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)； 而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷，即按什么樣的搜索路徑遍歷的問題。 對二叉樹而言，是由三個(gè)基本單元組成：根結(jié)點(diǎn)(D)、左子樹(L)和右子樹(R)。

2、因此，若能遍歷這三部分，便是遍歷了整個(gè)二叉樹?？紤]：一共有多少種遍歷 二叉樹的方案？則有 D L R 、L D R 、L R D 、 D R L 、R D L 、R L D 先序 中序 后序六種遍歷方案選擇假如以 L、D、R 分別表示遍歷二叉樹的左子樹(Left)、訪問根結(jié)點(diǎn)(Data)、遍歷右子樹(Right)，1.先左后右的遍歷算法 先（根）序遍歷算法：DLR 若二叉樹為空樹，則空操作；否則，訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。 中（根）序遍歷算法：LDR 若二叉樹為空樹，則空操作；否則，中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。 后（根）序遍歷算法：LRD 若二叉樹為空樹，則空

3、操作；否則，后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。例 :先（根）序的遍歷序列為：中（根）序的遍歷序列為：后（根）序的遍歷序列為：a+/-*efcdb- + a * b c d / e fa + b * c d e / fa b c d - * + e f / -20151105結(jié)束二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)二叉鏈表層序遍歷 層序遍歷就是按二叉樹的層序號(hào)順序遍歷。具體地講，就是先訪問根，接著是根的左孩子，再是根的右孩子，再。ABECDHG1234567 先訪問結(jié)點(diǎn)的子孩子一定先訪問，符合隊(duì)的特點(diǎn)（先進(jìn)先出）。 下面我們來看一下如何利用隊(duì)來進(jìn)行層序遍歷。例： 假設(shè)一棵二叉樹的先序序列為 E B

4、A D C F H G I K J，中序序列為 A B C D E F G H I J K。畫出該二叉樹。先序序列為 E B A D C F H G I K J中序序列為 A B C D E F G H I J K由先序序列知E為根又由中序知 左子樹：ABCD右子樹：FGHIJK由先序序列知B為根又由中序知 左子樹：A右子樹：CD由先序序列知F為根又由中序知 左子樹：右子樹：GHIJK由先序序列知D為根又由中序知 左子樹：C右子樹：由先序序列知H為根又由中序知 左子樹：G右子樹：IJK由先序序列知I為根又由中序知 左子樹：右子樹：JK由先序序列知K為根又由中序知 左子樹：J右子樹：ABCDFG

5、HIJKE ABFECDGHIJKABFEDIJKHCGABFEDIHJKCGABFEDIHJKCG先序序列為 E B A D C F H G I K J中序序列為 A B C D E F G H I J K由先序序列可知E為根又由中序知 左子樹：ABCD右子樹：FGHIJK由先序序列知B為根又由中序知 左子樹：A右子樹：CD由先序序列知F為根又由中序知 左子樹：右子樹：GHIJK由先序序列知D為根又由中序知 左子樹：C右子樹：由先序序列知H為根又由中序知 左子樹：G右子樹：IJK由先序序列知I為根又由中序知 左子樹：右子樹：JK由先序序列知K為根又由中序知 左子樹：J右子樹：ABFEDIHJ

6、KCG 先序遍歷二叉樹的遞歸算法Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)/二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)/先序遍歷二叉樹T的遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用visit1 if(T)2 if (Visit(T-data)3 if ( PreOrderTraverse(T-lchild,Visit )4 if (PreOrderTraverser(T-rchild,Visit)5 return OK;6 return ERROR; 7 else return OK;/先序遍歷【DLR】訪問根節(jié)點(diǎn)訪

7、問左子樹訪問右子樹主程序Pre( T )Pre(T R);Pre(T R);TAVisit(A);Pre(T L);TDVisit(D);Pre(T L);TCVisit(C);Pre(T L);TBVisit(B);Pre(T L);返回TPre(T R);返回T返回T返回T返回TPre(T R);得到的遍歷次序?yàn)椋篈 B D C先序遍歷【DLR】Status PreOrderTraverse(BiTree T,Status(* Visit) (TElemType e) if(T) if (Visit(T-data) if ( PreOrderTraverse(T-lchild,Visit

8、) if (PreOrderTraverser(T-rchild,Visit)ACBD中序遍歷二叉樹的遞歸算法： Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if(T) if ( InOrderTraverse(T-lchild,Visit) ) if (Visit(T-data) if ( InOrderTraverse(T-rchild,Visit) ) return OK; return ERROR; else return OK; 訪問左子樹訪問根節(jié)點(diǎn)訪問右子樹后序遍歷二叉樹的遞歸算法： Status Po

9、stOrderTraverse(BiTree T ,Status(* Visit)(TElemType e) if(T) if ( PostOrderTraverse(T-lchild ,Visit) ) if ( PostOrderTraverse(T-rchild ,Visit) ) if (Visit(T-data) return OK; return ERROR; else return OK; 訪問左子樹訪問右子樹訪問根節(jié)點(diǎn)void LevelOrderTraverse(BiTree T ) LinkQueue Q; InitQueue(Q); EnQueue(Q,T); while

10、(!QueueEmpty(Q) /判斷隊(duì)列是否為空 DeQueue(Q,T); /去隊(duì)頭元素 printf(%c,T-data); if(T-lchild) EnQueue(Q,T-lchild); if(T-rchild) EnQueue(Q,T-rchild); 后序遍歷二叉樹的遞歸算法：/層次遍歷的主要思想其實(shí)就是每次將一個(gè)根結(jié)點(diǎn)從隊(duì)列里刪除的時(shí)候同時(shí)將他的孩子放進(jìn)去/從根開始逐層訪問，用FIFO隊(duì)列實(shí)現(xiàn)/讓每一層從左到右依次進(jìn)隊(duì)再出隊(duì)void LevelOrderTraverse(BiTree T ) BiTree p; SqQueue Q; InitQueue(Q); if(T) Q

11、.baseQ.rear=T; Q.rear=(Q.rear+1)%MAXQSIZE; while(Q.front!=Q.rear) /判斷隊(duì)列是否為空 p=Q.baseQ.front; /去隊(duì)頭元素 printf(“%c”,p-data); Q.front=(Q.front+1)% MAXQSIZE; if(T-lchild) EnQueue(Q,T-lchild); if(T-rchild) EnQueue(Q,T-rchild); 遞歸算法執(zhí)行過程中遞歸工作棧的狀態(tài)變化如圖，根據(jù)其狀態(tài)變化可以直接寫出相應(yīng)的非遞歸算法。a*c-b前序-*abc 中序a*b-c 后序ab*c-例：從中序遍歷遞

12、歸算法執(zhí)行過程中遞歸工作棧狀態(tài)可見：(1) 工作記錄中包含兩項(xiàng)，其一是遞歸調(diào)用的語句編號(hào)，其二是指向根結(jié)點(diǎn)的指針，則當(dāng)棧頂記錄中的指針非空時(shí)，應(yīng)遍歷左子樹，即指向左子樹根的指針進(jìn)棧；(2) 若棧頂記錄中的指針值為空，則應(yīng)退至上一層，若是從左子樹返回，則應(yīng)訪問當(dāng)前層即棧頂記錄中指針?biāo)傅母Y(jié)點(diǎn)；(3) 若是從右子樹返回，則表明當(dāng)前層的遍歷結(jié)束，應(yīng)繼續(xù)退棧。從另一角度看，這意味著遍歷右子樹時(shí)不再需要保存當(dāng)前層的根指針，可直接修改棧頂記錄中的指針即可。r非空？訪問根結(jié)點(diǎn)先序遍歷左子樹先序遍歷右子樹r非空？訪問根結(jié)點(diǎn)先序遍歷左子樹先序遍歷右子樹中序遍歷二叉樹的非遞歸算法一：Staus InOrderT

13、rav(BiTree T,Status(* Visit)(TElemType e)/中序遍歷二叉樹T的非遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit.InitStack(S); Push(S,T); /根指針進(jìn)棧while(!StackEmpty(S) /S不為空的情況下，執(zhí)行下列語句 while(GetTop(S,p)&p) Push(S,p-lchild);/向左走到盡頭 Pop(S,p); /空指針退棧 if(!StackEmpty(S) /訪問結(jié)點(diǎn)，向右一步 Pop(S,p); if(!Visit(p-data) return error; Push(S,p-rchild); /if /

14、whileReturn ok; /InOrderTraverse中序遍歷二叉樹的非遞歸算法二：Status InOrderTrv( BiTree T,Status (*Visit)(TElemType e)/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)/中序遍歷二叉樹T的非遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。 InitStack(S); p=T; while(p | !StackEmpty(S) if (p) Push(S,p); p=p-lchild; else Pop(S,p); if (!Visit(p-data) return ERROR； p=p-rchild;

15、 /else /while return OK; /InOrderTrv/根指針進(jìn)棧，遍歷左子樹/根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹 2.遍歷算法的應(yīng)用舉例 “遍歷”是二叉樹各種操作的基礎(chǔ)，可以在遍歷過程中對結(jié)點(diǎn)進(jìn)行各種操作，如：對于一棵已知樹求結(jié)點(diǎn)的雙親，求結(jié)點(diǎn)的孩子結(jié)點(diǎn)，判定結(jié)點(diǎn)所在的層次等。例1：統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)Status CountLeaf (BiTree T, int & count) if ( T ) if ( (T-lchild =NULL) & (T-rchild =NULL) count + +; return OK; CountLeaf( T - lchild,

16、 count); / 統(tǒng)計(jì)左子樹中葉子結(jié)點(diǎn)個(gè)數(shù) CountLeaf( T - rchild, count); / 統(tǒng)計(jì)右子樹中葉子結(jié)點(diǎn)個(gè)數(shù) else return ERROR; 例2：求二叉樹的深度int Depth (BiTree T ) if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + max(depthLeft,depthRight); return depthval;例3：按先序序列建立二叉樹的二叉鏈表已知先序序列：A B C

17、 0 0 D E 0 G 0 0 F 0 0 0（其中0表示空格字符）建立相應(yīng)的二叉鏈表。ABCDEFGStatus CreateBiTree (BiTree &T) /按先序序列輸入二叉樹中結(jié)點(diǎn)的值，空格字符表示空樹 Scanf(&ch) if (ch = =0) T=NULL; else if( !( T=(BiTNode*)malloc(sizeof(BiTNode) ) ) exit(OVERFLOW); T-data = ch; /構(gòu)造根結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子樹 CreateBiTree(T-rchild); /構(gòu)造右子樹 Return OK例3：按先序序列建立二叉樹