1、WORD格式實用文檔數據構造雙語工程文檔報告用遞歸、非遞歸兩種方法遍歷二叉樹專業：計算機科學與技術班級：指導教師：XX：專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔學號：目錄一、設計思想.03二、算法流程圖.04三、源代碼.06四、運行結果.12五、遇到的問題及解決.14六、心得體會.15專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔一、設計思想1遞歸：1主函數 main主程序要包括：定義的二叉樹T、建樹函數、先序遍歷函數、中序遍歷函數、后序遍歷函數。2建樹函數定義一個輸入的數是字符型的，當ch 為空時， T 就為空值，否那么的話就分配空間給 T， T 就

2、指向它的結點，然后左指針域指向左孩子，右指針指向右孩子，假設還有，繼續調用 , 依次循環下去，直到 ch 遇到空時，完畢。最后要返回建立的二叉樹 T。3先序遍歷函數根據先序遍歷規那么，當 T 為非空時，先輸出結點處的數據，指針指向左、右孩子，依次進展下去。(4) 中序遍歷函數根據中序遍歷規那么，當 T 為非空時，先左指針指向左孩子數據，然后輸出結點處的數據，再右指針指向右孩子，依次進展下去。(5 后序遍歷函數根據后序遍歷規那么，當 T 為非空時，先右指針指向右孩子，然后左指針指向左孩子，最后輸出結點處的數據，依次進展下去。2. 非遞歸：1跟遞歸遍歷二叉樹的前提一樣，首先應該創立一個二叉樹，同樣

3、使用先序遞歸的方式創立二叉樹。2然后是中序，先序，后序非遞歸遍歷二叉樹。3中序非遞歸遍歷二叉樹的思想是：首先是根節點壓棧，當根節點的左子樹不是空的時候，左子樹壓棧。直到左子樹為空的時候，不再壓棧。將棧頂元素出棧，訪問棧頂元素，并將棧頂的右子樹進棧。當右子樹的左子樹不是空的時候，左子樹一直進棧，直到左子樹為空，那么不再進棧。重復上面的操作，直到?？盏臅r候。(4) 先序非遞歸遍歷二叉樹的思想是：首先是根節點進棧，然后當棧不為空的時候，將棧頂元素出棧，然后訪問。同時將出棧元素的右子樹進棧，左子樹進棧。重復上面的操作，直到棧為空。(5 后序非遞歸遍歷二叉樹的思想：首先是根節點進棧，當根節點的左子樹不為

4、空的時候，左子樹進棧，直到左為空的時候，左子樹不再進棧。指針指向的是右子樹，當右子樹為空的時候，直接訪問根節點。當右子樹不為空的時候，那么右子樹的指針進棧，當右子樹的左子樹不為空的時候，那么左也進棧，直到左為空。重復上面的操作，直到棧為空的時候，那么遍歷樹完成。專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔二、算法流程圖1. 遞歸專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔2. 非遞歸專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔三、源代碼1. 遞歸#include "stdio.h"#include "co

5、nio.h"#include <stdlib.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();

6、if(ch=' ') *T=NULL; return 0;else(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;while(ch!='0');/* 中序遞歸遍歷*/void InorderTransverse(BinTree s)if (s)專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔InorderTransverse(s->lchild);printf("%c", s

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

8、derTranverseTree(s->rchild);printf("%c", s->data);/* 主方法 */void main()BinTreeT;printf("請按照先序的順序輸入要創立的樹:n");CreateBinTree(&T); /*中序序列創立二叉樹*/printf("中序遞歸遍歷的序列是:");InorderTransverse(T);printf("n");/ 先序遞歸遍歷printf("先序遞歸遍歷的序列是:");PreOrderTranvers

9、eTree(T);printf("n");/ 后序遞歸遍歷printf("后序遞歸遍歷的序列是:");PostOrderTranverseTree(T);printf("n");專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔2. 非遞歸#include "stdio.h"#include "conio.h"#include <stack>#include <stdlib.h>typedef struct nodechar data;struct node

10、 *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; / 定義二叉樹類型的指針 typedef structBinTree data100;int top;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;in

11、t Pop(SeqStack *S,BinTree *p)if(S->top=-1)printf("the stack is underflow");return 0;else *p=S->dataS->top;-S->top;return 1;專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔int EmptyStack(SeqStack S)if(S.top=-1) return 1;else return 0; /*棧不空的情況*/int GetTop(SeqStack S,BinTree *p)if(S.top=-1)print

12、f("the stack is empty");return 0;else *p=S.dataS.top;return 1;char visit(BinTree p)return (*p).data;/* 創立二叉樹 */int CreateBinTree(BinTree *T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");elsedoch=getchar();if(ch!=' ')*T=NULL;return 0;else(*T)->d

13、ata=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;while(ch!='0');/* 中序非遞歸遍歷*/void InorderTransverse(BinTree T)SeqStack S;BinTreep;initStack(&S);/初始化棧printf("中序非遞歸序列是:");專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔Push(&S,T); /根指針進棧T為指向二叉樹的指針while(!

14、EmptyStack(S)/棧不是空的情況while(GetTop(S,&p) && p)Push(&S,p->lchild);/gettop得到的結果也必須是一棵子樹才行, 進棧應該進的是樹根的指針Pop(&S,&p);if(!EmptyStack(S)/printf("%c",visit(p);Pop(&S,&p);printf("%c",visit(p);Push(&S,p->rchild);/* 先序非遞歸遍歷*/void PreorderTransverse(B

15、inTree T)SeqStack S;BinTreep;initStack(&S);/初始化棧Push(&S,T); /根指針進棧T為指向二叉樹的指針printf("先序非遞歸序列是:");while(!EmptyStack(S)Pop(&S,&p);/根節點出棧if(p!=NULL)printf("%c",visit(p);Push(&S,p->rchild);Push(&S,p->lchild);/* 后序非遞歸遍歷*/void PostorderTransverse(BinTree T)

16、SeqStack S;BinTreep,q;initStack(&S);/初始化棧p=T;printf("后序非遞歸序列是:");while(p |!EmptyStack(S)/跳出while循環的原因是因為左子樹或者右子樹為空了if(p!=q)while(p!=NULL)Push(&S,p);if(p->lchild!=NULL)p=p->lchild;elsep=p->rchild;專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔if(EmptyStack(S) break;GetTop(S,&q);if(q-&

17、gt;rchild=p)/進棧的是右子樹Pop(&S,&p);printf("%c",visit(p);p=q;elsep=q->rchild;/* 主方法 */void main()BinTreeT;printf("請按照先序的順序輸入創立的樹:n");/* 創立樹 */CreateBinTree(&T);/ 中序非遞歸遍歷InorderTransverse(T);printf("n");/ 先序非遞歸遍歷PreorderTransverse(T);printf("n");/ 后序非

18、遞歸遍歷PostorderTransverse(T);四、運行結果1. 遞歸輸入專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔結果2. 非遞歸輸入專業資料整理WORD格式標準文案專業資料整理WORD格式實用文檔結果五、遇到的問題及解決經過一個星期的寫代碼，我遇到了很多問題，并一一解決了，比方：1.創立二叉樹時： void createBiTree(BiTNode*T) 和 void createBiTree(BiTNode*&T)沒分清楚區別。后來查找資料找到void createBiTree(BiTNode *T)是將結點的指針地址傳遞到函數中進展處理void createBiTree(BiTNode *&T是將結點指針的引用傳遞到函數處理。才理解清楚。專業資料整理WORD格式標