二叉樹的遍歷

1、目 錄一、設(shè)計思想.01二、算法流程圖.01三、源代碼.04四、運行結(jié)果.08五、遇到的問題及解決.09六、心得體會.10一、 設(shè)計思想遍歷二叉樹首先有三種方法，即先序遍歷，中序遍歷和后序遍歷。遞歸方法比較簡單，首先獲得結(jié)點指針如果指針不為空，且有左子，從左子遞歸到下一層，如果沒有左子，從右子遞歸到下一層，如果指針為空，則結(jié)束一層遞歸調(diào)用。直到遞歸全部結(jié)束。 下面重點來講述非遞歸方法：首先介紹先序遍歷：先序遍歷的順序是根 左 右，也就是說先訪問根結(jié)點然后訪問其左子再然后訪問其右子。具體算法實現(xiàn)如下：如果結(jié)點的指針不為空，結(jié)點指針入棧，輸出相應(yīng)結(jié)點的數(shù)據(jù)，同時指針指向其左子，如果結(jié)點的指針為空，

2、表示左子樹訪問結(jié)束，棧頂結(jié)點指針出棧，指針指向其右子，對其右子樹進(jìn)行訪問， 如此循環(huán)，直至結(jié)點指針和棧均為空時，遍歷結(jié)束。 再次介紹中序遍歷：中序遍歷的順序是左 根 右，中序遍歷和先序遍歷思想差不多，只是打印順序稍有變化。具體實現(xiàn)算法如下：如果結(jié)點指針不為空，結(jié)點入棧，指針指向其左子，如果指針為空，表示左子樹訪問完成，則棧頂結(jié)點指針出棧，并輸出相應(yīng)結(jié)點的數(shù)據(jù)，同時指針指向其右子，對其右子樹進(jìn)行訪問。如此循環(huán)直至結(jié)點指針和棧均為空，遍歷結(jié)束。最后介紹后序遍歷：后序遍歷的順序是左 右 根，后序遍歷是比較難的一種，首先需要建立兩個棧，一個用來存放結(jié)點的指針，另一個存放標(biāo)志位，也是首先訪問根結(jié)點，如果

3、結(jié)點的指針不為空，根結(jié)點入棧，與之對應(yīng)的標(biāo)志位也隨之入標(biāo)志位棧，并賦值0，表示該結(jié)點的右子還沒有訪問，指針指向該結(jié)點的左子，如果結(jié)點指針為空，表示左子訪問完成，父結(jié)點出棧，與之對應(yīng)的標(biāo)志位也隨之出棧，如果相應(yīng)的標(biāo)志位值為0，表示右子樹還沒有訪問，指針指向其右子，父結(jié)點再次入棧，與之對應(yīng)的標(biāo)志位也入棧，但要給標(biāo)志位賦值為1，表示右子訪問過。如果相應(yīng)的標(biāo)志位值為1，表示右子樹已經(jīng)訪問完成，此時要輸出相應(yīng)結(jié)點的數(shù)據(jù)，同時將結(jié)點指針賦值為空，如此循環(huán)直至結(jié)點指針和棧均為空，遍歷結(jié)束。二、 算法流程圖下圖是定義的二叉樹的結(jié)構(gòu)圖ABCDEGF圖1 二叉樹結(jié)構(gòu)圖下圖是遞歸算法的流程圖，首先的到當(dāng)前根結(jié)點，判

4、斷結(jié)點指針是否空，如果非空，判斷左子指針是否為空，非空則指向左子，左子作為當(dāng)前根結(jié)點，空則判斷右子指針是否為空，非空則指向右子，右子作為當(dāng)前根結(jié)點，如果空，輸出相應(yīng)的數(shù)據(jù)，結(jié)束遞歸。圖2 遞歸算法流程圖下圖是非遞歸算法先序遍歷的算法流程圖，首先對結(jié)點指針進(jìn)行判斷，如果指針不為空，結(jié)點指針入棧，輸出數(shù)據(jù)，指針指向左子，訪問左子樹，如果結(jié)點指針為空，棧頂結(jié)點指針出棧，指針指向右子，訪問右子樹，直至遍歷整個二叉樹。圖3 非遞歸先序遍歷算法流程圖下圖是非遞歸中序遍歷算法流程圖，首先對結(jié)點指針進(jìn)行判斷，如果指針不為空，則指針入棧，指針指向其左子，對左子樹進(jìn)行訪問，如果結(jié)點指針為空，棧頂結(jié)點指針出棧，輸出

5、相應(yīng)的數(shù)據(jù)，指針指向右子，對右子樹進(jìn)行訪問，直至遍歷整個二叉樹。圖4 非遞歸中序遍歷算法流程圖、下圖是非遞歸后序遍歷二叉樹算法流程圖，首先對結(jié)點指針進(jìn)行判斷，如果指針不為空，結(jié)點指針和相應(yīng)的標(biāo)志位同時入棧，指針指向左子，對左子樹進(jìn)行遍歷，如果指針為空，棧頂指針和相應(yīng)的標(biāo)志位同時出棧，如果標(biāo)志位的值為0，則結(jié)點再次入棧，標(biāo)志位置1，隨之入棧，指針指向右子，訪問右子樹，如果標(biāo)志位的值為1，輸出相應(yīng)結(jié)點的數(shù)據(jù)，并將結(jié)點指針置為NULL，直至遍歷結(jié)束。圖5 非遞歸后序遍歷算法流程圖三、 源代碼#include<stdio.h>#define MAX 100 /表示棧的最大容量#define

6、 FULL 99/表示棧滿#define EMPTY -1/表示?？誸ypedef struct Tnode /定義結(jié)點char data;/存儲結(jié)點數(shù)據(jù) struct Tnode *left;/定義結(jié)點左子指針struct Tnode *right;/定義右子指針Tnode,*Pnode;/聲明Tnode類型的變量和指針typedef struct Stack/定義棧Pnode pnodeMAX;/存放數(shù)據(jù)int p;/棧頂指針Stack,*Pstack;/定義Stack類型的變量和指針void Push (Pstack pstack,Pnode pnode)/入棧pstack->p

7、+;pstack->pnodepstack->p = pnode;/賦值Pnode Pop(Pstack pstack)/出棧return pstack->pnodepstack->p-;Pnode Top (Pstack pstack)/看棧頂元素return pstack->pnodepstack->p;int Isempty (Pstack pstack)/棧判空if(pstack->p=EMPTY)return 1;else return 0;int Isfull (Pstack pstack )/棧滿if (pstack ->p=FUL

8、L)return 1;else return 0;void Initstack (Pstack pstack)/初始化棧pstack->p=EMPTY;void Inittnode(Pnode root,Pnode left,Pnode right,char data)/初始化結(jié)點root->left=left;root->right = right;root->data = data;void PreorderR(Pnode proot)/遞歸先序遍歷算法if(proot)printf("%2c",proot->data);PreorderR

9、(proot->left);PreorderR(proot->right);void InorderR(Pnode proot)/遞歸中序遍歷算法if(proot)InorderR(proot->left);printf("%2c",proot->data);InorderR(proot->right);void PostorderR(Pnode proot)/遞歸后序遍歷算法if(proot)PostorderR(proot->left);PostorderR(proot->right);printf("%2c"

10、;,proot->data);void PreorderI(Pnode proot,Pstack pstack)/非遞歸先序遍歷算法Initstack(pstack);/初始化棧while(proot|!Isempty(pstack)/如果?？詹⑶医Y(jié)點指針空，則結(jié)束循環(huán)if(proot)printf("%2c",proot->data);if(Isfull(pstack)/如果棧滿不能執(zhí)行入棧操作printf("棧滿，不能執(zhí)行入棧操作！");return;Push(pstack,proot);/入棧proot=proot->left;/

11、指針指向左子else if(Isempty(pstack)/?？諘r不能出棧printf("棧空，不能執(zhí)行出棧操作！");return;proot = Pop(pstack);/執(zhí)行出棧操作proot=proot->right;/指針指向右子void InorderI(Pnode proot,Pstack pstack)/非遞歸中序遍歷算法Initstack(pstack);/初始化棧while(proot|!Isempty(pstack)/循環(huán)結(jié)束條件if(proot)if(Isfull(pstack)printf("棧滿，不能執(zhí)行入棧操作！");

12、return;Push(pstack,proot);/執(zhí)行入棧操作proot = proot->left;/指針指向左子else if(Isempty(pstack)printf("棧空，不能執(zhí)行出棧操作！");return ;proot = Pop(pstack);/出棧printf("%2c",proot->data);/打印數(shù)據(jù)proot=proot->right;/指針指向右子void PostorderI(Pnode proot,Pstack pstack)/非遞歸后續(xù)遍歷算法int flagsMAX;/定義標(biāo)志位棧int p

13、 =-1;/初始化標(biāo)志位棧int flag;/存放標(biāo)志位Initstack(pstack);/初始化棧while(proot|!Isempty(pstack)/循環(huán)結(jié)束條件if(proot)if(Isfull(pstack)printf("棧滿，不能執(zhí)行入棧操作！");return ;flags+p = 0;/標(biāo)志位置0，并入棧Push(pstack,proot);/結(jié)點入棧proot=proot->left;/指針指向左子elseproot = Pop(pstack);/指針出棧flag = flagsp-;/相應(yīng)標(biāo)志位出棧if(flag=0)/如果標(biāo)志位為0表示右

14、子還未訪問過flag =1;/將標(biāo)志位置1，右子已訪問flags+p = flag;/標(biāo)志位入棧Push(pstack,proot);/結(jié)點入棧 proot = proot->right;/指針指向右子else printf("%2c",proot->data);/打印數(shù)據(jù)proot = NULL;/將結(jié)點指針置空void main ()Tnode A,B,C,D,E,F,G;/聲明結(jié)點變量Stack stack;/聲明棧Inittnode(&A,&B,&C,'A');/初始化結(jié)點Inittnode(&B,NULL

15、,&D,'B');Inittnode(&C,&E,&F,'C');Inittnode(&D,NULL,NULL,'D');Inittnode(&E,NULL,NULL,'E');Inittnode(&F,&G,NULL,'F');Inittnode(&G,NULL,NULL,'G');printf("你定義的樹的結(jié)構(gòu)是：n"); /*一下是調(diào)用相應(yīng)的函數(shù)輸出遍歷結(jié)果*/printf("A(B(D)C

16、(E F(G)n");printf("=下面是遍歷結(jié)果=n");printf("=遞歸先序遍歷：=n");PreorderR(&A);printf("n");printf("=非遞歸先序遍歷：=n");PreorderI(&A,&stack);printf("n");printf("=遞歸中序遍歷：=n");InorderR(&A);printf("n");printf("=非遞歸中序遍歷：=n"

17、;);InorderI(&A,&stack);printf("n");printf("=遞歸后序遍歷：=n");PostorderR(&A);printf("n");printf("=非遞歸后序遍歷：=n");PostorderI(&A,&stack);printf("n");四、 運行結(jié)果定義的樹的結(jié)構(gòu)為A(B(D)C(EF(G),遍歷的結(jié)果：圖6 程序運行結(jié)果五、 遇到的問題及解決這部分我主要遇到如下兩個問題，其內(nèi)容和解決方法如下所列： 執(zhí)行程序時程序

18、停止運行，其效果如圖：圖7 問題一截圖 解決方法：看到程序停止運行，推測可能的原因：遇到死循環(huán)、參數(shù)設(shè)置不合理或者結(jié)構(gòu)體沒有造好。首先對結(jié)構(gòu)體進(jìn)行了檢查，各個成員聲明正常無誤，在對程序進(jìn)行調(diào)試，程序正常跳出循環(huán)，因此最可能是自定義函數(shù)的參數(shù)設(shè)置的不合理，因此對調(diào)用的自定義函數(shù)進(jìn)行相應(yīng)的改動，將參數(shù)由具體類型改為指針類型后，程序正常運行。 程序不停的輸出同一個結(jié)點的數(shù)據(jù)，其效果入圖：圖8 問題二截圖解決方法：分析運行結(jié)果可知，第一不停的輸出證明遇到了死循環(huán)，第二輸出的是同一個結(jié)點的數(shù)據(jù)，表示指針沒有按預(yù)期進(jìn)行指向，首先對程序進(jìn)行調(diào)試，發(fā)現(xiàn)程序沒有添加循環(huán)結(jié)束條件，添加循環(huán)結(jié)束條件后，只能輸出樹的部分結(jié)點的數(shù)據(jù)，對標(biāo)志位進(jìn)行修改后，程序運行正常，也能正確輸出遍歷結(jié)果。六、心得體會通過這次作業(yè)真的受益匪淺，感觸良多：首先，要提高編程能力，必須多動手，多實踐，而不是