DS06樹和二叉樹02二叉樹的遍歷

1、DS06樹和二叉樹02二叉樹的遍歷本節(jié)內(nèi)容前序、中序、后序遍歷的過程前序、中序、后序遍歷的遞歸算法前序、中序、后序遍歷的非遞歸算法層序遍歷算法6.3.1 遍歷二叉樹 二叉樹的遍歷：是指從根結(jié)點(diǎn)出發(fā)，按照某種次序訪問二叉樹中的所有結(jié)點(diǎn)，使得每個結(jié)點(diǎn)被訪問一次且僅被訪問一次?？梢允菍Y(jié)點(diǎn)進(jìn)行的各種處理，一般簡化為輸出結(jié)點(diǎn)的值。前序遍歷中序遍歷后序遍歷層序遍歷 假設(shè)二叉樹的六種遍歷方式：DLR、LDR、LRD、DRL、RDL、RLD 假設(shè)限定先左后右，那么遍歷方式有三種：DLR = 前序(或先序)LDR = 中序LRD = 后序根結(jié)點(diǎn)D左子樹L右子樹R二叉樹二叉樹的遍歷方式 假設(shè)二叉樹為空，那么返回

2、；否那么：訪問根結(jié)點(diǎn)；前序遍歷根結(jié)點(diǎn)的左子樹；前序遍歷根結(jié)點(diǎn)的右子樹。前序遍歷序列：ABCDEFG二叉樹的前序遍歷ABDGCEF假設(shè)二叉樹為空，那么返回；否那么：中序遍歷根結(jié)點(diǎn)的左子樹；訪問根結(jié)點(diǎn)；中序遍歷根結(jié)點(diǎn)的右子樹。 中序遍歷序列：DGBAECF二叉樹的中序遍歷ABCDEFG假設(shè)二叉樹為空，那么返回；否那么：后序遍歷根結(jié)點(diǎn)的左子樹；后序遍歷根結(jié)點(diǎn)的右子樹。訪問根結(jié)點(diǎn)；后序遍歷序列：GDBEFCA二叉樹的后序遍歷ABCDEFG從二叉樹的第一層即根結(jié)點(diǎn)開場，從上至下逐層遍歷，在同一層中，那么按從左到右的順序?qū)Y(jié)點(diǎn)逐個訪問。 A B C D E F G二叉樹的層序遍歷ABCDEFG層序遍歷序列

3、：例 : 先序遍歷序列波蘭式為： 中序遍歷序列為： 后序遍歷序列逆波蘭式為：- + a * b c d / e fa + b * c d e / fa b c d - * + e f / -a+/-*efcdb-Q: 假設(shè)一棵二叉樹的前序序列和中序序列，能否唯一確定這棵二叉樹呢？怎樣確定？ 例如：一棵二叉樹的前序遍歷序列和中序遍歷序列分別為ABCDEFGHI 和BCAEDGHFI，如何構(gòu)造該二叉樹呢? 前序：A B C D E F G H I中序：B C A E D G H F I前序：B C中序：B C B C D EF GH IA前序： D E F G H I中序： E D G H F I

4、ABCDEFGHI前序：F G H I中序：G H F I前序： D E F G H I中序： E D G H F IABCDEFGHIABCDEFIGH1. 根據(jù)前序序列的第一個元素建立根結(jié)點(diǎn)；2. 在中序序列中找到該元素，確定根結(jié)點(diǎn)的左右子樹的中序序列；3. 在前序序列中確定左右子樹的前序序列；4. 由左子樹的前序序列和中序序列建立左子樹；5. 由右子樹的前序序列和中序序列建立右子樹。 一棵二叉樹的前序序列和中序序列，構(gòu)造該二叉樹的過程如下： 例：前序遍歷序列為ABC，后序遍歷序列為CBA，畫出滿足條件的二叉樹。那么以下二叉樹都滿足條件。ABCABC結(jié)論給定一棵二叉樹的前序和中序序列可以唯

5、一確定此二叉樹給定一棵二叉樹的中序和后序序列可以唯一確定此二叉樹給定一棵二叉樹的前序和后序序列不能唯一確定此二叉樹先序遍歷二叉樹的遞歸算法Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)/二叉鏈表存儲構(gòu)造，visit是對數(shù)據(jù)元素操作的函數(shù)/先序遍歷二叉樹T的遞歸算法，對每個數(shù)據(jù)元素調(diào)用visit if(T) if (Visit(T-data) /訪問當(dāng)前結(jié)點(diǎn) if ( PreOrderTraverse(T-lchild,Visit ) /先序左子 if (PreOrderTraverser(T-rchild,Visit)

6、 return OK; /先序右子 return ERROR; else return OK;/最簡單的Visit函數(shù)是： 輸出元素e的值Status PrintElement (TElemType e) printf ( e );/實(shí)現(xiàn)時，加上格式串 return OK;/調(diào)用實(shí)例：PreOrderTraverse (T, PrintElement);中序遍歷二叉樹的遞歸算法：Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if(T) if ( InOrderTraverse(T-lchild,Visit) ) if

7、 (Visit(T-data) if ( InOrderTraverse(T-rchild,Visit) ) return OK; return ERROR; else return OK;后序遍歷二叉樹的遞歸算法：Status PostOrderTraverse(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 ER

8、ROR; else return OK; 中序遍歷的執(zhí)行過程void PreOrder(BiTree T) if(T) printf(T-data); /訪問結(jié)點(diǎn) PreOrder(T-lchild); /先序左子 PreOrder(T-rchild); /先序右子 void InOrder(BiTree T) if(T) InOrder(T-lchild); /中序左子 printf(T-data); /訪問結(jié)點(diǎn) InOrder(T-rchild); /中序右子 void PostOrder(BiTree T) if(T) PostOrder(T-lchild); /后序左子 PostOrd

9、er(T-rchild); /后序右子 printf(T-data); /訪問結(jié)點(diǎn) 三種遍歷的簡單寫法 “遍歷是二叉樹各種操作的根底，可以在遍歷過程中對結(jié)點(diǎn)進(jìn)展各種操作，如：對于一棵樹求結(jié)點(diǎn)的雙親，求結(jié)點(diǎn)的孩子結(jié)點(diǎn)個數(shù)，斷定結(jié)點(diǎn)所在的層次等，也可在遍歷過程中生成結(jié)點(diǎn)，建立二叉樹的存儲構(gòu)造。例1：求二叉樹的深度int getDepth(BiTree T) int depth,dLeft,dRight; if (!T) depth = 0; else dLeft = getDepth(T-lchild); dRight = getDepth(T-rchild); depth = (dLeft=dR

10、ight) ? (dLeft+1) : (dRight+1); return depth;例2：統(tǒng)計二叉樹中葉子結(jié)點(diǎn)的個數(shù)void CountLeaf(BiTree T, int &count) if (T) if (T-lchild=NULL) & (T-rchild=NULL) +count; return; CountLeaf(T-lchild, count); / 統(tǒng)計左子樹葉子結(jié)點(diǎn)個數(shù) CountLeaf(T-rchild, count); / 統(tǒng)計右子樹葉子結(jié)點(diǎn)個數(shù) count在調(diào)用此函數(shù)前已初始化為0例3：按先序序列建立二叉樹的二叉鏈表先序序列：A B C # # D E # G

11、 # # F # # #其中#表示空格字符建立相應(yīng)的二叉鏈表。ABCEDGF例3：按先序序列建立二叉樹的二叉鏈表/按先序序列輸入二叉樹中結(jié)點(diǎn)的值，空格字符表示空樹int CreateBiTree(BiTree &T) char ch; scanf(%c,&ch); if (ch = ) T = NULL; else if (!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(-1); T-data = ch; /構(gòu)造根結(jié)點(diǎn) CreateBiTree(T-lchild); /構(gòu)造左子 CreateBiTree(T-rchild); /構(gòu)造右子 return 0;從

12、上述二叉樹遍歷的定義可知，三種遍歷算法不同之處僅在于訪問根結(jié)點(diǎn)和遍歷左、右子樹的先后關(guān)系。假設(shè)在算法中暫且抹去和遞歸無關(guān)的visit語句，那么三個遍歷算法完全一樣。由此，從遞歸執(zhí)行過程的角度來看先序、中序和后序遍歷也是完全一樣的。 三種遍歷過程示意圖 向下的箭頭表示更深一層的遞歸調(diào)用，向上的箭頭表示從遞歸調(diào)用退出返回。 虛線旁的三角形、圓形和方形內(nèi)的字符分別表示在先序、中序和后序遍歷過程中訪問結(jié)點(diǎn)時輸出的信息。 只要沿虛線從1出發(fā)到2完畢，將沿途所見的三角形或圓形、方形內(nèi)的字符記下，便得遍歷二叉樹的先序或中序、后序序列。中序遍歷二叉樹的非遞歸算法遞歸算法雖然簡潔，但是有時程序設(shè)計不允許用遞歸，

13、且遞歸效率不高，這時就存在如何把遞歸程序轉(zhuǎn)化成等價的非遞歸算法的問題。解決這個問題的關(guān)鍵是設(shè)置一個棧。仿照遞歸算法執(zhí)行過程中編譯棧的工作原理，可以寫出相應(yīng)的非遞歸算法。訪問結(jié)點(diǎn)序列:B棧S內(nèi)容:D A B ADBC NULL D NULL NULL訪問結(jié)點(diǎn)序列:棧S內(nèi)容:BD A ADBCA C NULL NULLC1. 棧s初始化，根指針進(jìn)棧；2. 循環(huán)直到棧s為空 2.1 當(dāng)指向棧頂元素的指針p不空時循環(huán) 2.1.1 p-lchild壓棧； 2.2 空指針退棧 2.3 假設(shè)棧s不空，那么 2.3.1 將棧頂元素彈出至p； 2.3.2 訪問p-data; 2.3.3 p的右子樹壓棧； 中序遍

14、歷非遞歸算法6.2偽代碼中序遍歷二叉樹的/中序遍歷的非遞歸算法Status InOrderTrav(BiTree T) InitStack(S); Push(S,T); /根指針入棧 while(!StackEmpty(S) while(GetTop(S,p)&p) Push(S,p-lchild);/向左走到盡頭 Pop(S,p); /空指針退棧 if(!StackEmpty(S) /棧非空，那么出棧訪問結(jié)點(diǎn)，右子入棧 Pop(S,p); printf(p-data); Push(S,p-rchild); return OK;1. 棧s初始化，p指向根結(jié)點(diǎn)；2. p非空或棧s非空時循環(huán) 2.

15、1 假設(shè)p不空 2.1.1 p壓棧； 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偽代碼訪問結(jié)點(diǎn)序列:B棧S內(nèi)容:D A B ADBC D訪問結(jié)點(diǎn)序列:棧S內(nèi)容:BD A ADBCA CC中序遍歷的Status InOrderTrv(BiTree T) InitStack(S); p=T; while(p | !StackEmpty(S) if (p) Push(S,p); p=p-lchild; else Pop(S,p

16、); printf(p-data)； p=p-rchild; return OK;/根指針進(jìn)棧，遍歷左子/根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子 1. 棧s初始化，p指向根結(jié)點(diǎn)；2. p非空或棧s非空時循環(huán) 2.1 當(dāng)p不空時循環(huán)2.1.1 輸出p-data; 2.1.2 p壓棧； 2.1.3 繼續(xù)遍歷p的左子樹2.2 假設(shè)棧s不空，那么2.2.1 將棧頂元素彈出至p；2.2.2 準(zhǔn)備遍歷p的右子樹； 前序遍歷非遞歸算法偽代碼中序訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD A B前序遍歷的非遞歸實(shí)現(xiàn) ADBC訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD A前序遍歷的非遞歸實(shí)現(xiàn) ADBC D訪問結(jié)點(diǎn)序列:A棧S內(nèi)容:BD C前

17、序遍歷的非遞歸實(shí)現(xiàn) ADBCCvoid PreOrderTrv( BiTree T) InitStack(S); BiTree p = 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; 層序遍歷隊列Q初始化；2. 假設(shè)二叉樹非空，將根指針入隊；3. 循環(huán)直到隊列為空 3.1 隊頭元素出隊，q指向它； 3.2 訪問結(jié)點(diǎn)q； 3.3 假設(shè)結(jié)點(diǎn)q有左子，那么將左子

18、指針入隊； 3.4 假設(shè)結(jié)點(diǎn)q有右子，那么將右子指針入隊；/ 層序遍歷(利用隊列)void LevelOrderTraverse(BiTree T) LinkQueue q; BiTNode* p; if(T) InitQueue(q); / 初始化隊列q EnQueue(q,T); / 根指針入隊 while (!QueueEmpty(q) / 隊列非空，循環(huán) DeQueue(q,p); / 隊頭元素出隊, 賦給p printf(p-data); / 訪問p所指結(jié)點(diǎn) if (p-lchild!=NULL) / p有左子 EnQueue(q, p-lchild); / p的左子入隊 if (p

19、-rchild!=NULL) / p有右子 EnQueue(q, p-rchild); / p的右子入隊 printf(n); 遍歷的復(fù)雜度分析遍歷算法的根本操作是訪問結(jié)點(diǎn)，那么不管哪種遍歷算法，對于有n個結(jié)點(diǎn)的二叉樹，時間復(fù)雜度均為O(n)只要對每個結(jié)點(diǎn)的處理函數(shù)Visit的執(zhí)行時間是一個常數(shù)，那么遍歷二叉樹就可以在線性時間內(nèi)完成所需要的輔助空間為遍歷過程中棧的最大容量，即樹的深度最壞情況下具有n個結(jié)點(diǎn)的二叉樹高度為n，那么所需要的空間復(fù)雜度為O(n)習(xí)題6.27： 假設(shè)一棵二叉樹的先序序列為 E B A D C F H G I K J，中序序列為 A B C D E F G H I J K。畫出該二叉樹?！痉治觥坑上刃蛐蛄械玫礁Y(jié)點(diǎn)，然后由中序序列得到左右子樹的先序和中序序列。依次類推。JEBFAHDCGIK作業(yè)本周五 下午實(shí)驗(yàn) 二叉樹的實(shí)現(xiàn)習(xí)題按先序次序建立二叉樹的算法，原型說明：void CreateBiTree(BiTree &T);2. 二叉樹的打印，有縮進(jìn)，并旋轉(zhuǎn)了90度，本算法可以用于調(diào)試二叉樹處理程序。h為T所在層數(shù)。原型：void printBiTree(BiTree T, int h);main函數(shù)里的調(diào)用語句為：BiTree root; printBiTree(root, 0);二叉樹的打印void printNode(TEle