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

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

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

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

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

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

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

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

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

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

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

11、斷flag，若flag為0，則從左棧出棧一個元素作為當前結點，重新判斷；若flag為1則從右棧出棧一個元素作為當前結點，重新判斷左右子是否去過，若status為1，則判斷該結點有沒有右子，若有右子，則將該結點入右棧，status置1，flag置1，若沒有右子，則打印當前結點，并將指針置空，然后再次判斷flag。若當前結點status為2，且棧為空，則遍歷結束。若指針指向了左子，則將左子作為當前結點，判斷其左右子情 況，按上述方法處理，直至遍歷結束。三、源代碼F面給出的是用遞歸算法實現(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);/結點的數(shù)據(jù)/結點左右子/控制下面函數(shù)中循環(huán)的/產生二叉樹（利用先序遞歸產生）/創(chuàng)建一個根結點指針/如果傳入的當前值為0則設其為空結/開辟內存/設置當前結點的數(shù)據(jù)/左子結點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é)點返回/前序遍歷/如果根節(jié)點不為0/打印當前結點/指向左子/指向右子/中序遍歷/如果根節(jié)點不為0/指向左子/打印當前結點/指

14、向右子void postOrder(Node *root)if(root!=0)/指向左子/指向左子/指向右子/打印當前結點postOrder(root-IChild); postOrder(root-rChild); prin tf(%d ”,root-data); void mai n()/按先序次序輸入樹的結點(非 0整數(shù))來創(chuàng)建一個樹空結點用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前序遍歷：”)；/打印提示內容preOrder(root);/調用前序遍歷函數(shù)printf(n中序遍歷：”);in Order(root);函數(shù)printf(n后序遍歷：);postOrder(root);getch();/打印提示內容/調用中序遍歷/打印提示內容/調用后序遍歷函數(shù)/定義二叉樹的結點/結點的數(shù)據(jù)/結點左右子/創(chuàng)建棧/棧底指針/棧頂指針/初始化棧下面給出的是用非遞歸算法實現(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)/為指針開辟內存/棧頂指針指向棧底指針/判斷棧是否為空的函數(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出的結點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)結構體/棧底指針/棧頂指針/初始化棧/開辟內存/棧頂指針指向棧底指針/進棧方法/給棧頂賦值然后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出的結點/查棧頂元素II返回棧頂元素II判斷棧是否為空II棧空了返回1II不為空返回 0II產生二叉樹II創(chuàng)建一個根結點指II如果傳入的當前值為 0則設其為空結點/開辟內存/設置當前結點的數(shù)/左子結點/右子/把創(chuàng)建的樹的根結點返/前序遍歷/聲明一個棧/當前結點為根結點/初始化找/當前結點不為空且棧不為/如果當前結點為空/當前結點指向pop出棧的結點/如果右子為空 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);/將右子進棧prin tf(%d ”,curr.data);/打印當前結點的內容if(currChild!=NULL)/如果左子不為空curr=*currChild;/當前子指向左子elsecurr=p

21、op(&po);/當前子指向pop出棧結占八、if(curr.lChild=NULL) &(curr.rChild=NULL)/如果左子右子都為空prin tf(%d ”,curr.data);/打印當前結點的內容curr.data=0;/當前結點置空void inOrder(Node *root)Stack ms;Node curr = *root;占八、int flag = 0;/設置一個標志 0:當前結點指向了右結點/中序遍歷/聲明一個棧/當前結點指向根結1:當前結點指向了左結點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)/初始化棧/當前結點不為空且棧不/左子不為空且沒去過/當前子進棧當前結點指向左子/打印當前結點的內/左子為空/指向左子/指向左子/flag 置 0/如果左右子都為空/打印當前結點的內/?？談t結束循環(huán)當前子指向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);結點flag=1;void postOrder(Node *root)/聲明左右棧如果當前結點有左子則進左棧右沒左子但是有右子則進右棧Stack msl;/聲明左棧MyStack msr;/聲明右棧Node curr = *root;/結點指向樹的根結占八、/初始化左棧/初始化左棧/初始化右棧/沒去過左右子樹且右子不為int flag=0;/設置一個標志0:進左棧 1:進右棧/設置一個標志0:沒去過左右子樹1:去過左子樹 2:去過右子樹(兩子樹都去過)int status=O;in it (&msl)

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

25、/如果flag標志為0/如果左棧不為空/指向左棧彈出的元/status標志置為1/指向右棧彈出的元/status標志置為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標志置為

26、1/若當前結點為空，結束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)建一個結點指向創(chuàng)建的樹的根結點printf（”用非遞歸方法n前序遍歷：）;/打印提示內容preOrder(root);/調用前序遍歷函數(shù)printf（n中序遍歷：”）；/打