二叉樹遍歷C語言(遞歸,非遞歸)六種算法

1、文檔文檔數(shù)據(jù)結(jié)構(gòu)（雙語）項(xiàng)目文檔報(bào)告用兩種方式實(shí)現(xiàn)表達(dá)式自動(dòng)計(jì)算專 業(yè)：班 級(jí)：指導(dǎo)教師：姓 名：實(shí)用標(biāo)準(zhǔn)文案實(shí)用標(biāo)準(zhǔn)文案文檔文檔號(hào): TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document 一、設(shè)計(jì)思想.01 HYPERLINK l bookmark6 o Current Document 二、算法流程圖2 HYPERLINK l bookmark8 o Current Document 三、源代碼.04 HYPERLINK l bookmark10 o Current Document 四、運(yùn)行結(jié)果.11 HYPERLINK l boo

2、kmark12 o Current Document 五、遇到的問題及解決. HYPERLINK l bookmark14 o Current Document 六、心得體會(huì).12一、設(shè)計(jì)思想二叉樹的遍歷分為三種方式， 分別是先序遍歷，中序遍歷和后序遍歷。 先序遍歷實(shí)現(xiàn)的 順序是：根左右，中序遍歷實(shí)現(xiàn)的是：左根右，后續(xù)遍歷實(shí)現(xiàn)的是：左右根。根據(jù)不同的算 法分，又分為遞歸遍歷和非遞歸遍歷。遞歸算法：1 先序遍歷：先序遍歷就是首先判斷根結(jié)點(diǎn)是否為空，為空則停止遍歷，不為空則將 左子作為新的根結(jié)點(diǎn)重新進(jìn)行上述判斷，左子遍歷結(jié)束后，再將右子作為根結(jié)點(diǎn)判斷，直至結(jié)束。到達(dá)每一個(gè)結(jié)點(diǎn)時(shí)，打印該結(jié)點(diǎn)數(shù)據(jù)，即

3、得先序遍歷結(jié)果。2中序遍歷：中序遍歷是首先判斷該結(jié)點(diǎn)是否為空，為空則結(jié)束，不為空則將左子作為 根結(jié)點(diǎn)再進(jìn)行判斷，打印左子，然后打印二叉樹的根結(jié)點(diǎn)，最后再將右子作為參數(shù)進(jìn)行判斷， 打印右子，直至結(jié)束。3.后續(xù)遍歷：指針到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，判斷該結(jié)點(diǎn)是否為空，為空則停止遍歷，不為空則 將左子作為新的結(jié)點(diǎn)參數(shù)進(jìn)行判斷，打印左子。左子判斷完成后，將右子作為結(jié)點(diǎn)參數(shù)傳入判斷，打印右子。左右子判斷完成后打印根結(jié)點(diǎn)。非遞歸算法：1先序遍歷：首先建立一個(gè)棧，當(dāng)指針到達(dá)根結(jié)點(diǎn)時(shí)，打印根結(jié)點(diǎn)，判斷根結(jié)點(diǎn)是否有 左子和右子。有左子和右子的話就打印左子同時(shí)將右子入棧，將左子作為新的根結(jié)點(diǎn)進(jìn)行判斷，方法同上。若當(dāng)前結(jié)點(diǎn)沒有

4、左子， 則直接將右子打印，同時(shí)將右子作為新的根結(jié)點(diǎn)判斷。 若當(dāng)前結(jié)點(diǎn)沒有右子，則打印左子，同時(shí)將左子作為新的根結(jié)點(diǎn)判斷。若當(dāng)前結(jié)點(diǎn)既沒有左子也沒有右子，則當(dāng)前結(jié)點(diǎn)為葉子結(jié)點(diǎn)，此時(shí)將從棧中出棧一個(gè)元素，作為當(dāng)前的根結(jié)點(diǎn)， 打印結(jié)點(diǎn)元素，同時(shí)將當(dāng)前結(jié)點(diǎn)同樣按上述方法判斷，依次進(jìn)行。直至當(dāng)前結(jié)點(diǎn)的左右子都為空，且棧為空時(shí)，遍歷結(jié)束。2中序遍歷：首先建立一個(gè)棧，定義一個(gè)常量flag （flag為0或者1），用flag記錄結(jié)點(diǎn)的左子是否去過，沒有去過為0，去過為1，默認(rèn)為0.首先將指針指向根結(jié)點(diǎn)，將根結(jié)點(diǎn)入棧，然后將指針指向左子，左子作為新的結(jié)點(diǎn)，將新結(jié)點(diǎn)入棧，然后再將指針指向當(dāng)前結(jié)點(diǎn)的左子，直至左子為

5、空，則指針返回，flag置1，出棧一個(gè)元素，作為當(dāng)前結(jié)點(diǎn)，打印該結(jié)點(diǎn)，然后判斷flag，flag為1則將指針指向當(dāng)前結(jié)點(diǎn)右子，將右子作為新的結(jié)點(diǎn)，結(jié)點(diǎn) 入棧，再次進(jìn)行上面的判斷，直至當(dāng)前結(jié)點(diǎn)右子也為空，則再出棧一個(gè)元素作為當(dāng)前結(jié)點(diǎn)， 一直到結(jié)束，使得當(dāng)前結(jié)點(diǎn)右子為空，且?？?，遍歷結(jié)束。3.后續(xù)遍歷：首先建立兩個(gè)棧，然后定義兩個(gè)常量。第一個(gè)為status，取值為0，1，2.0代表左右子都沒有去過，1代表去過左子，2，代表左右子都去過，默認(rèn)為0。第二個(gè)常量為flag，取值為0或者1，0代表進(jìn)左棧，1代表進(jìn)右棧。初始時(shí)指針指向根結(jié)點(diǎn)，判斷 根結(jié)點(diǎn)是否有左子，有左子則，將根結(jié)點(diǎn)入左棧，status置0

6、，flag置0 ,若沒有左子則判斷結(jié)點(diǎn)有沒有右子，有右子就把結(jié)點(diǎn)入右棧，status置0 , flag置1，若左右子都沒有，則打印該結(jié)點(diǎn)，并將指針指向空，此時(shí)判斷flag，若flag為0,則從左棧出棧一個(gè)元素作為當(dāng)前結(jié)點(diǎn)，重新判斷；若flag為1則從右棧出棧一個(gè)元素作為當(dāng)前結(jié)點(diǎn)，重新判斷左右子是否去過，若status為1，則判斷該結(jié)點(diǎn)有沒有右子，若有右子，則將該結(jié)點(diǎn)入右棧，status置1，flag置1，若沒有右子，則打印當(dāng)前結(jié)點(diǎn)，并將指針置空，然后再次判斷flag。若當(dāng)前結(jié)點(diǎn)status為2，且棧為空，則遍歷結(jié)束。若指針指向了左子，則將左子作為當(dāng)前結(jié)點(diǎn)， 判斷其左右子情況，按上述方法處理，直

7、至遍歷結(jié)束。、算法流程圖圖1二叉樹的建立用先序方法建立二叉樹，為每個(gè)結(jié)點(diǎn)定義左右子，用0代表空，得到上述二叉樹首先建立一個(gè)棧，當(dāng)指針到達(dá)根結(jié)點(diǎn)時(shí)，打印根結(jié)點(diǎn)，判斷根結(jié)點(diǎn)是否有左子和右子。有左子和右子的話就打印左子同時(shí)將右子入棧，將左子作為新的根結(jié)點(diǎn)進(jìn)行判斷，方法同上。若當(dāng)前結(jié)點(diǎn)沒有左子， 則直接將右子打印，同時(shí)將右子作為新的根結(jié)點(diǎn)判斷。 若當(dāng)前結(jié)點(diǎn)沒 有右子，則打印左子，同時(shí)將左子作為新的根結(jié)點(diǎn)判斷。若當(dāng)前結(jié)點(diǎn)既沒有左子也沒有右子， 則當(dāng)前結(jié)點(diǎn)為葉子結(jié)點(diǎn)，此時(shí)將從棧中出棧一個(gè)元素，作為當(dāng)前的根結(jié)點(diǎn)，打印結(jié)點(diǎn)元素， 同時(shí)將當(dāng)前結(jié)點(diǎn)同樣按上述方法判斷，依次進(jìn)行。直至當(dāng)前結(jié)點(diǎn)的左右子都為空，且棧為空

8、時(shí)，遍歷結(jié)束。君和話吝兔司檢濟(jì)比弱歳寺 flng 耳為rtrue補(bǔ)忖化th韻匕純點(diǎn)拒W梅吋吏*雪（fifrUS老儻陽0毎君和話吝兔司檢濟(jì)比弱歳寺 flng 耳為rtrue補(bǔ)忖化th韻匕純點(diǎn)拒W梅吋吏*雪（fifrUS老儻陽0毎到當(dāng)誇 空.豈切性yes當(dāng)F?荃點(diǎn)-入棧 當(dāng)豈結(jié)士花習(xí)苗 左于拒它蚩H建.GE吉于*藉F當(dāng)甫檔點(diǎn)fla 9為 fdse圖3非遞歸二叉樹遍歷中序中序遍歷：首先建立一個(gè)棧，定義一個(gè)常量flag （flag為0或者1），用flag記錄結(jié)點(diǎn)的左子是否去過，沒有去過為0,去過為1，默認(rèn)為0.首先將指針指向根結(jié)點(diǎn)，將根結(jié)點(diǎn)入棧，然后將指針指向左子，左子作為新的結(jié)點(diǎn)，將新結(jié)點(diǎn)入棧，然后

9、再將指針指向當(dāng)前結(jié)點(diǎn)的左子，直至左子為空，則指針返回，flag置1，出棧一個(gè)元素，作為當(dāng)前結(jié)點(diǎn)，打印該結(jié)點(diǎn)，然后判斷flag，flag為1則將指針指向當(dāng)前結(jié)點(diǎn)右子，將右子作為新的結(jié)點(diǎn)，結(jié)點(diǎn)入 棧，再次進(jìn)行上面的判斷，直至當(dāng)前結(jié)點(diǎn)右子也為空，則再出棧一個(gè)元素作為當(dāng)前結(jié)點(diǎn)，一 直到結(jié)束，使得當(dāng)前結(jié)點(diǎn)右子為空，且棧空，遍歷結(jié)束。11JncnoFiacjO?nc當(dāng)前螞點(diǎn)退右 崔，當(dāng)砒融 向其掃子” iajE斗前帶占茴 做*単出的姑 11JncnoFiacjO?nc當(dāng)前螞點(diǎn)退右 崔，當(dāng)砒融 向其掃子” iajE斗前帶占茴 做*単出的姑 占3O1U3Hn=Ii洛審朽 直啟國陽呦 站點(diǎn)，stain HX3豈

10、前烷環(huán)向 謖；七，鼻 自,和生焯出狹 負(fù) -taluuS卽怕伊杖 6t.- 宅站號(hào)（fif即 和丸3和$和導(dǎo)當(dāng)齡占圖4非遞歸二叉樹遍歷后序首先建立兩個(gè)棧，然后定義兩個(gè)常量。第一個(gè)為status，取值為0, 1 , 2.0代表左右子都沒有去過，1代表去過左子，2，代表左右子都去過，默認(rèn)為0。第二個(gè)常量為flag，取值為0或者1， 0代表進(jìn)左棧，1代表進(jìn)右棧。初始時(shí)指針指向根結(jié)點(diǎn)，判斷根結(jié)點(diǎn)是否有左 子，有左子則，將根結(jié)點(diǎn)入左棧，status置0，flag置0，若沒有左子則判斷結(jié)點(diǎn)有沒有右子，有右子就把結(jié)點(diǎn)入右棧，status置0，flag置1，若左右子都沒有，則打印該結(jié)點(diǎn)，并將指針指向空，此時(shí)判

11、斷flag，若flag為0，則從左棧出棧一個(gè)元素作為當(dāng)前結(jié)點(diǎn)，重新判斷；若flag為1則從右棧出棧一個(gè)元素作為當(dāng)前結(jié)點(diǎn)，重新判斷左右子是否去過，若status為1，則判斷該結(jié)點(diǎn)有沒有右子，若有右子，則將該結(jié)點(diǎn)入右棧，status置1，flag置1，若沒有右子，則打印當(dāng)前結(jié)點(diǎn)，并將指針置空，然后再次判斷flag。若當(dāng)前結(jié)點(diǎn)status為2，且棧為空，則遍歷結(jié)束。若指針指向了左子，則將左子作為當(dāng)前結(jié)點(diǎn)，判斷其左右子情 況，按上述方法處理，直至遍歷結(jié)束。三、源代碼F面給出的是用遞歸算法實(shí)現(xiàn)的程序的源代碼:#in clude#in clude/用遞歸的方式遍歷二叉樹typedef struct nod

12、e/用遞歸的方式遍歷二叉樹typedef struct node int data;struct n ode*IChild,*rChild;Node;int i=-1;Node *buildTree( int *b)Node *p;if(b+i=O)p=NULL;占八、else p=(Node*)malloc(sizeof(Node);p_data=bi;p-IChild=buildTree(b);/結(jié)點(diǎn)的數(shù)據(jù)/結(jié)點(diǎn)左右子/控制下面函數(shù)中循環(huán)的/產(chǎn)生二叉樹（利用先序遞歸產(chǎn)生）/創(chuàng)建一個(gè)根結(jié)點(diǎn)指針/如果傳入的當(dāng)前值為0則設(shè)其為空結(jié)/開辟內(nèi)存/設(shè)置當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)/左子結(jié)點(diǎn)p-rChild=buil

13、dTree(b);return p;void preOrder(Node *root)if(root!=0)prin tf(%d ”,root-data);preOrder(root-lChild);preOrder(root-rChild);void in Order(Node *root)if(root!=0)in Order(root-lChild); prin tf(%d ,root-data);in Order(root-rChild);/右子/把創(chuàng)建的樹的根節(jié)點(diǎn)返回/前序遍歷/如果根節(jié)點(diǎn)不為0/打印當(dāng)前結(jié)點(diǎn)/指向左子/指向右子/中序遍歷/如果根節(jié)點(diǎn)不為0/指向左子/打印當(dāng)前結(jié)點(diǎn)/指

14、向右子void postOrder(Node *root)if(root!=0)/指向左子/指向左子/指向右子/打印當(dāng)前結(jié)點(diǎn)postOrder(root-IChild); postOrder(root-rChild); prin tf(%d ”,root-data); void mai n()/按先序次序輸入樹的結(jié)點(diǎn)(非 0整數(shù))來創(chuàng)建一個(gè)樹空結(jié)點(diǎn)用0表示int a = 1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,9,0,0;int *b = a;將指向數(shù)組首地址的指針傳給bulidTree 函數(shù)來創(chuàng)建樹Node *root = buildTree(b);printf(用遞

15、歸方法nn前序遍歷：”)；/打印提示內(nèi)容preOrder(root);/調(diào)用前序遍歷函數(shù)printf(n中序遍歷：”);in Order(root);函數(shù)printf(n后序遍歷：);postOrder(root);getch();/打印提示內(nèi)容/調(diào)用中序遍歷/打印提示內(nèi)容/調(diào)用后序遍歷函數(shù)/定義二叉樹的結(jié)點(diǎn)/結(jié)點(diǎn)的數(shù)據(jù)/結(jié)點(diǎn)左右子/創(chuàng)建棧/棧底指針/棧頂指針/初始化棧下面給出的是用非遞歸算法實(shí)現(xiàn)的程序的源代碼:#in clude#in clude/用非遞歸的方式遍歷二叉樹typedef struct node int data;struct node *IChild,*rChild;Node

16、;typedef structNode *bottom;Node *top;Stack;void in it(Stack *s)s-bottom=(Node *)malloc(100*sizeof(Node);s-top=s-bottom;int isEmpty(Stack s)/為指針開辟內(nèi)存/棧頂指針指向棧底指針/判斷棧是否為空的函數(shù)if(s.top=s.bottom)return 1;else/?？辗祷?return 0;void push(Stack *s,Node node)*(s-top+)=no de;Node pop(Stack *s)Node no de;no de=*(_(

17、s_top);后 top-1retur n no de;/不為空返回 0/棧的push方法/給棧頂賦值然后top+1/出棧函數(shù)/聲明一 Node類型遍量n ode為棧頂元素然II返回pop出的結(jié)點(diǎn)Node peek(Stack *s)return *(s-top-1);typedef structNode *bottom;Node *top;MyStack;void in it1(MyStack *s)s-bottom=(Node *)malloc(10C s-top=s-bottom;void push1(MyStack *s,Node node)*(s-top+)=no de;Node p

18、op1(MyStack *s)Node no de;no de=*(_(s_top);/看棧頂元素/返回棧頂元素/創(chuàng)建棧(MyStack)結(jié)構(gòu)體/棧底指針/棧頂指針/初始化棧/開辟內(nèi)存/棧頂指針指向棧底指針/進(jìn)棧方法/給棧頂賦值然后top+1/出棧函數(shù)/聲明一 Node類型遍量n ode為棧頂元素然后top-1retur n no de;Node peek1(MyStack *s)return *(s-top-1);int isEmpty1(MyStack s)if(s.top=s.bottom)return 1;elsereturn 0;int temp=-1;Node *buildTree

19、( int *b)Node *p;針if(b+temp=0) p=NULL;elseII返回pop出的結(jié)點(diǎn)/查棧頂元素II返回棧頂元素II判斷棧是否為空II?？樟朔祷?II不為空返回 0II產(chǎn)生二叉樹II創(chuàng)建一個(gè)根結(jié)點(diǎn)指II如果傳入的當(dāng)前值為 0則設(shè)其為空結(jié)點(diǎn)/開辟內(nèi)存/設(shè)置當(dāng)前結(jié)點(diǎn)的數(shù)/左子結(jié)點(diǎn)/右子/把創(chuàng)建的樹的根結(jié)點(diǎn)返/前序遍歷/聲明一個(gè)棧/當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)/初始化找/當(dāng)前結(jié)點(diǎn)不為空且棧不為/如果當(dāng)前結(jié)點(diǎn)為空/當(dāng)前結(jié)點(diǎn)指向pop出棧的結(jié)點(diǎn)/如果右子為空 p=(Node*)malloc(sizeof(Node); p_data=btemp;據(jù)p-IChild=buildTree(b); p

20、-rChild=buildTree(b);return p;回void preOrder(Node *root)Stack po;Node curr = *root;in it(&po);while(curr.data!=0|!isEmpty(po)空if(curr.data=0)curr=pop(&po);if(curr.rChild!=NULL)push(&po,*curr.rChild);/將右子進(jìn)棧prin tf(%d ”,curr.data);/打印當(dāng)前結(jié)點(diǎn)的內(nèi)容if(currChild!=NULL)/如果左子不為空curr=*currChild;/當(dāng)前子指向左子elsecurr=p

21、op(&po);/當(dāng)前子指向pop出棧結(jié)占八、if(curr.lChild=NULL) &(curr.rChild=NULL)/如果左子右子都為空prin tf(%d ”,curr.data);/打印當(dāng)前結(jié)點(diǎn)的內(nèi)容curr.data=0;/當(dāng)前結(jié)點(diǎn)置空void inOrder(Node *root)Stack ms;Node curr = *root;占八、int flag = 0;/設(shè)置一個(gè)標(biāo)志 0:當(dāng)前結(jié)點(diǎn)指向了右結(jié)點(diǎn)/中序遍歷/聲明一個(gè)棧/當(dāng)前結(jié)點(diǎn)指向根結(jié)1:當(dāng)前結(jié)點(diǎn)指向了左結(jié)點(diǎn)in it (&ms);while(curr.data!=O|isEmpty(ms)為空if(currChil

22、d!=NULL&flag=0)左子push(&ms,curr); curr=*currChild;elseprin tf(%d ”,curr.data);容if(curr.rChild!=NULL)/初始化棧/當(dāng)前結(jié)點(diǎn)不為空且棧不/左子不為空且沒去過/當(dāng)前子進(jìn)棧當(dāng)前結(jié)點(diǎn)指向左子/打印當(dāng)前結(jié)點(diǎn)的內(nèi)/左子為空/指向左子/指向左子/flag 置 0/如果左右子都為空/打印當(dāng)前結(jié)點(diǎn)的內(nèi)/?？談t結(jié)束循環(huán)當(dāng)前子指向pop出棧的/flag 置 1/后序遍歷curr=*curr.rChild;flag=0;if(curr.rChild=NULL&currChild=NULL)printf(%d ”,curr.

23、data);容if(isEmpty(ms)=1) break;curr = pop(&ms);結(jié)點(diǎn)flag=1;void postOrder(Node *root)/聲明左右棧如果當(dāng)前結(jié)點(diǎn)有左子則進(jìn)左棧右沒左子但是有右子則進(jìn)右棧Stack msl;/聲明左棧MyStack msr;/聲明右棧Node curr = *root;/結(jié)點(diǎn)指向樹的根結(jié)占八、/初始化左棧/初始化左棧/初始化右棧/沒去過左右子樹且右子不為int flag=0;/設(shè)置一個(gè)標(biāo)志0:進(jìn)左棧 1:進(jìn)右棧/設(shè)置一個(gè)標(biāo)志0:沒去過左右子樹1:去過左子樹 2:去過右子樹(兩子樹都去過)int status=O;in it (&msl)

24、;in it (&msr);while(curr.data!=0|isEmpty(msl)!=0|isEmpty1(msr)!=0)/當(dāng)前結(jié)點(diǎn)不為空且左右棧都不為空if(status=0&currChild!=NULL)push(&msl,curr);curr = *currChild;flag=0;else if(status!=2&curr.rChild!=NULL)為空push1(&msr,curr);/當(dāng)前子進(jìn)左棧/當(dāng)前子指向左子/flag 置 0/沒去過右子樹且右子不/當(dāng)前子進(jìn)右棧/當(dāng)前子指向右子/flag 置 1/status 置 0/打印當(dāng)前結(jié)點(diǎn)內(nèi)容/當(dāng)前結(jié)點(diǎn)置空/如果當(dāng)前子為空

25、/如果flag標(biāo)志為0/如果左棧不為空/指向左棧彈出的元/status標(biāo)志置為1/指向右棧彈出的元/status標(biāo)志置為2curr=*curr.rChild;flag=1;status=O;elseprintf(%d ”,curr.data);curr.data=0;if(curr.data=0)if(flag=0)if(isEmpty(msl)=O)curr = pop(&msl);素status=1;else if(isEmpty1(msr)=0)curr = pop1(&msr);素status=2;/如果右棧為空/如果右棧為空/指向右棧彈出的元/指向左棧彈出的元素/status標(biāo)志置為

26、1/若當(dāng)前結(jié)點(diǎn)為空，結(jié)束elseif(isEmpty1(msr)=0)curr=pop1(&msr);素status=2;else if(isEmpty(msl)=0)curr=pop(&msl);status=1;if(curr.data=O) break;循環(huán)void mai n()int Tree = 1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,9,0,0;int *tree = Tree;Node *root = buildTree（tree）;II創(chuàng)建一個(gè)結(jié)點(diǎn)指向創(chuàng)建的樹的根結(jié)點(diǎn)printf（”用非遞歸方法n前序遍歷：）;/打印提示內(nèi)容preOrder(root);/調(diào)用前序遍歷函數(shù)printf（n中序遍歷：”）；/打