二叉樹前序或中序或后序遍歷

1、數(shù)學與計算機學院計算機系實驗報告課程名稱： 數(shù)據(jù)結構指導教師課程名稱： 數(shù)據(jù)結構指導教師： 黃襄念實驗名稱：二叉樹前序或中序或后序遍歷實驗序號：實驗3年級：2010實驗成績姓名：實驗教室學號：實驗日期實驗時間：8:0011:40實驗學時6A-4132012/6/104一、實驗目的熟悉的掌握樹的創(chuàng)建，和樹的前序、中序、后序遍歷。二、實驗環(huán)境操作系統(tǒng)：Windows7開發(fā)軟件： Microsoft Visual C+ 6.0三、實驗內容程序功能本程序完成了以下功能前序遍歷中序遍歷后序遍歷 數(shù)據(jù)結構本程序中使用的數(shù)據(jù)結構(若有多個，逐個說明)：1. 它的優(yōu)缺點1 ) 可以快速的查找數(shù)據(jù)。2) 讓數(shù)據(jù)

2、層次更加清晰。2. 邏輯結構圖3. 存儲結構圖2. 邏輯結構圖3. 存儲結構圖4. 存儲結構的 C/C+ 語言描述 typedef struct node DataType data; struct node *lchild; struct node *rchild; BiTNode, *BiTree; typedef BiTree type;算法描述本程序中采用的算法算法名稱：遞歸算法原理或思想 是通過訪問結點的左右孩子來進行循環(huán)查找的方法，拿中序遍歷來說明：先從頭結 點開始，再去訪問頭結點的右孩子如果為空就訪問頭結點的左孩子，依次進行訪問 當結點的左右孩子都為空時，就訪問上一級，到了最后。

3、算法特點它能將查找進行 2 分，體現(xiàn)出了更高效快捷的特點，并且層次很清晰。 程序說明代碼：void InOrder(BiTree root) Stack S(100);initStack(S);BiTNode *p = root; do while(p != NULL) Push(S, p);p = p-lchild; if(!isEmpty(S)Pop(S, p);cout data rchild; while(p != NULL | !isEmpty(S); cout rchild; if(!isEmpty(S)Pop(S, p);p = p-lchild; while(p != NULL

4、 | !isEmpty(S); while(!isEmpty(SS) Pop(SS, p); cout data ; cout endl;3) 中序遍歷模塊：將樹進行從左孩子開始再頭結點再右孩子 代碼： void PreOrder(BiTree root)Stack S(100); initStack(S);BiTNode *p = root;do while(p != NULL) Push(S, p);cout data lchild;if(!isEmpty(S)Pop(S, p);p = p-rchild; while(p != NULL | !isEmpty(S); cout endl;

5、四、調試與運行1. 程序調試本程序開發(fā)過程中，采用的調試方法或手段如下：方法1：在程序執(zhí)行的終止的函數(shù)中加一條輸出語句coutvv”*”vvendl；進行 錯誤的定位，調試了指針沒有正確使用的錯誤。方法 2：輸出一些樹中的數(shù)據(jù)，看能不能正確的輸出，調試了其左右孩子是不是正 確。2. 運行結果本次實驗多個功能需分別截圖，逐個說明。MHXMHXMHXMHXMHXMH JCH X運行結果圖1歷歷歷序 H 12 3 0B C D E G F輸入你的選屋B C D E G F輸入你的選毘B E G D F A輸入你的選擇:G E F D B A輸入爾的選擇:ress any key to continu

6、e五、實驗總結結果分析：本程序完成了樹的前序遍歷、中序遍歷、后序遍歷功能；但是還是存在不 完善的地方，沒有對結點進行刪除增加等操作，沒有將樹的結構給輸出。心得體會：通過這個實驗我更熟練的掌握了二叉樹的結構同時也更了解了遞歸算法， 覺得數(shù)據(jù)結構是一個很不錯的一門課程。代碼：#include #include using namespace std;using std:cout;using std:endl;typedef char DataType;typedef struct node DataType data;struct node *lchild;struct node *rchild;

7、 BiTNode, *BiTree;typedef BiTree type;class Stackfriend void initStack(Stack &S);friend bool isEmpty(Stack &S);friend bool Push(Stack &S, type x);friend bool Pop(Stack &S, type &x);friend bool getTop(Stack &S, type &x);public:Stack(int maxSize)if(maxSize maxSize = maxSize; this-s = NULL;virtual Stac

8、k()if(this-s != NULL)delete this-s; this-s = NULL;protected:int maxSize; std:stack *s;void initStack(Stack &S)if(S.s != NULL)delete S.s;S.s = NULL; S.s = new std:stack(); bool isEmpty(Stack &S) return S.s-empty();bool Push(Stack &S, type x)if(S.s-size() = S.maxSize) return false;S.s-push(x); return

9、true;bool Pop(Stack &S, type &x)if(S.s-empty()return false;x = S.s-top();S.s-pop();return true;bool getTop(Stack &S, type &x)if(S.s-empty()return false;x = S.s-top(); return true;void PreOrder(BiTree root)Stack S(100); initStack(S); BiTNode *p = root; do while(p != NULL)Push(S, p); cout data lchild;

10、 if(!isEmpty(S) Pop(S, p);p = p-rchild; while(p != NULL | !isEmpty(S); cout lchild; if(!isEmpty(S) Pop(S, p);cout data rchild; while(p != NULL | !isEmpty(S); cout rchild; if(!isEmpty(S)Pop(S, p);p = p-lchild; while(p != NULL | !isEmpty(S); while(!isEmpty(SS)Pop(SS, p);cout data cout endl;void menu()coutvv*1.中序遍歷*vvendl;coutvv*2.前序遍歷*vvendl;coutvv*3.后序遍歷*vvendl;coutvv*0.退出程序*vvendl;!cout!c