1、實用文檔數據結構（雙語）項目文檔報告用遞歸、非遞歸兩種方法遍歷二叉樹專 業：計算機科學與技術班 級：指導教師：姓 名：號:一、設計思想 .03二、算法流程圖 .04三、源代碼 .06四、運行結果 .12五、遇到的問題及解決 .14六、心得體會 .15標準文案一、設計思想1 .遞歸：(1)主函數main ()主程序要包括：定義的二叉樹 T、建樹函數、先序遍 歷函數、中序遍歷函數、后序遍歷函數。(2)建樹函數定義一個輸入的數是字符型的，當 ch為空時，T就為空值， 否則的話就分配空間給T, T就指向它的結點，然后左指針域指向左孩子，右指 針指向右孩子，若還有，繼續調用，依次循環下去，直到ch遇到空

2、時，結束。最 后要返回建立的二叉樹To(3)先序遍歷函數根據先序遍歷規則，當 T為非空時，先輸出結點處的數 據，指針指向左、右孩子，依次進行下去。(4)中序遍歷函數根據中序遍歷規則，當T為非空時，先左指針指向左孩子 數據，然后輸出結點處的數據，再右指針指向右孩子，依次進行下去。(5)后序遍歷函數根據后序遍歷規則，當T為非空時，先右指針指向右孩子， 然后左指針指向左孩子，最后輸出結點處的數據，依次進行下去。2 .非遞歸：(1)跟遞歸遍歷二叉樹的前提一樣， 首先應該創建一個二叉樹，同樣使用 先序遞歸的方式創建二叉樹。(2)然后是中序，先序，后序非遞歸遍歷二叉樹。(3)中序非遞歸遍歷二叉樹的思想是：

3、 首先是根節點壓棧，當根節點的左 子樹不是空的時候，左子樹壓棧。直到左子樹為空的時候，不再壓棧。將棧頂元 素出棧，訪問棧頂元素，并將棧頂的右子樹進棧。當右子樹的左子樹不是空的時 候，左子樹一直進棧，直到左子樹為空，則不再進棧。重復上面的操作，直到棧 空的時候。(4)先序非遞歸遍歷二叉樹的思想是：首先是根節點進棧，然后當棧不為空 的時候，將棧頂元素出棧，然后訪問。同時將出棧元素的右子樹進棧，左子樹進 棧。重復上面的操作，直到棧為空。(5)后序非遞歸遍歷二叉樹的思想：首先是根節點進棧，當根節點的左子 樹不為空的時候，左子樹進棧，直到左為空的時候，左子樹不再進棧。指針指向 的是右子樹，當右子樹為空的

4、時候，直接訪問根節點。當右子樹不為空的時候， 則右子樹的指針進棧，當右子樹的左子樹不為空的時候， 則左也進棧，直到左為 空。重復上面的操作，直到棧為空的時候，則遍歷樹完成。二、算法流程圖i.遞歸I咕布在、4旃人校孫上 11M中憫歷程2.非遞歸建。網TT.T收布 白當宜的懶用舟根丐息人山-|k利p盤口”的人 授元篇.并聘id中 的巾行點也掛，也 人君I技心中£ tt-' HTXTFhIL< U伍槽3的元典依次山林三、源代碼1 .遞歸#include "stdio.h"#include "conio.h"#include <st

5、dlib.h>#include<stack>typedef struct nodechar data;struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; 定義二叉樹類型的指針/*先序創建二叉樹*/int CreateBinTree(BinTree *T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");doch=getchar();if(ch='') *T=NULL;re

6、turn 0;else(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;while(ch!='0');/*中序遞歸遍歷*/void InorderTransverse(BinTree s)ifInorderTransverse(s->lchild); printf("%c", s->data); InorderTransverse(s->rchild);/先序遞歸遍歷二叉樹void PreOrde

7、rTranverseTree(BinTree s)ifprintf("%c", s->data);PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); /后序遞歸遍歷二叉樹 void PostOrderTranverseTree(BinTree s) if PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); printf("%c", s->data);/*

8、主方法*/void main()BinTree T;printf("請按照先序的順序輸入要創建的樹：n");CreateBinTree(&T); /*中序序列創建二叉樹*/printf("中序遞歸遍歷的序列是：")；InorderTransverse(T);printf("n");/先序遞歸遍歷printf("先序遞歸遍歷的序列是：")；PreOrderTranverseTree(T); printf("n");/后序遞歸遍歷printf("后序遞歸遍歷的序列是：")

9、；PostOrderTranverseTree(T); printf("n");2 .非遞歸#include "stdio.h"#include "conio.h"#include <stack>#include <stdlib.h>typedef struct nodechar data;struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; 定義二叉樹類型的指針typedef structBinTree data100;int to

10、p;SeqStack;void initStack(SeqStack *S)S->top =-1;void Push(SeqStack *S,BinTree x)if(S->top=100-1)printf("the stack is overflow");else S->top=S->top+1;S->dataS->top=x;int Pop(SeqStack *S,BinTree *p)if(S->top=-1)printf("the stack is underflow");return 0;else *p

11、=S->dataS->top;-S->top;return 1;int EmptyStack(SeqStack S)if(S.top=-1) return 1;else return 0; /*棧不空的情況*/int GetTop(SeqStack S,BinTree *p)if(S.top=-1)printf("the stack is empty");return 0;else *p=S.dataS.top;return 1;char visit(BinTree p) return (*p).data;/*創建二叉樹*/int CreateBinTre

12、e(BinTree *T)char ch;叮=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");else doch=getchar();if(ch!='')q=NULL;return 0; else(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild); return 1;while(ch!='0');/*中序非遞歸遍歷*/void InorderTra

13、nsverse(BinTree T)SeqStack S;BinTree p;initStack(&S);/ 初始化棧printf("中序非遞歸序列是：")；Push(&S,T); / 根指針進棧T為指向二叉樹的指針while(!EmptyStack(S) /棧不是空的情況while(GetTop(S,&p) && p)Push(&S,p->lchild); /gettop得到的結果也必須是一棵子樹才行,進棧應該進的是樹根的指針Pop(&S,&p);if(!EmptyStack(S)printf(&quo

14、t;%c",visit(p);Pop(&S,&p);printf("%c",visit(p);Push(&S,p->rchild); /*先序非遞歸遍歷*/ void PreorderTransverse(BinTree T)SeqStack S;BinTree p;initStack(&S);/ 初始化棧Push(&S,T); /根指針進棧Tprintf("先序非遞歸序列是：")；while(!EmptyStack(S)Pop(&S,&p);/if(p!=NULL) printf(

15、"%c",visit(p); Push(&S,p->rchild); Push(&S,p->lchild); /*后序非遞歸遍歷*/ void PostorderTransverse(BinTree T)SeqStack S;BinTree p,q;initStack(&S);/ 初始化棧p=T;printf("后序非遞歸序列是：")；while(p |!EmptyStack(S) /為空了if(p!=q)while(p!=NULL)為指向二叉樹的指針根節點出棧跳出while循環的原因是因為左子樹或者右子樹Push(&

16、amp;S,p);if(p->lchild!=NULL) p=p->lchild;elsep=p->rchild; if(EmptyStack(S) break;進棧的是右子樹GetTop(S,&q); if(q->rchild=p)/Pop(&S,&p); printf("%c",visit(p); p=q; else p=q->rchild; /*主方法*/ void main()BinTree T;printf("請按照先序的順序輸入創建的樹：n");/*創建樹*/CreateBinTree(&

17、amp;T);/中序非遞歸遍歷InorderTransverse(T); printf("n"); /先序非遞歸遍歷 PreorderTransverse(T); printf("n"); /后序非遞歸遍歷 PostorderTransverse(T); 四、運行結果1.遞歸 輸入結果配"E:jST3Debug4exe 回 甌2.非遞歸輸入請按.照先序的順 錦仄要劉郡嗣12 3 4 5 6 7中文-Q。拼音輸入法全二結果。拼音輸法gl：12345fc?I 5：1234567Hj|：2345671 continue五、遇到的問題及解決經過一個星期的寫代碼，我遇到了很多問題，并一一解決了，比如：1 .創建二叉樹時：void createBiTree(BiTNode *T)和 void createBiTree(BiTNode *&T) 沒分清楚區別。后來查找資料找到 void createBiTree(BiTNode *T)是將結點的指針(地址)傳遞到函數中進行處理void createBiTree(BiTNode *