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

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

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

3、算法特點(diǎn)它能將查找進(jìn)行 2 分，體現(xiàn)出了更高效快捷的特點(diǎ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) 中序遍歷模塊：將樹進(jìn)行從左孩子開始再頭結(jié)點(diǎn)再右孩子 代碼： 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、四、調(diào)試與運(yùn)行1. 程序調(diào)試本程序開發(fā)過程中，采用的調(diào)試方法或手段如下：方法1：在程序執(zhí)行的終止的函數(shù)中加一條輸出語句coutvv”*”vvendl；進(jìn)行 錯(cuò)誤的定位，調(diào)試了指針沒有正確使用的錯(cuò)誤。方法 2：輸出一些樹中的數(shù)據(jù)，看能不能正確的輸出，調(diào)試了其左右孩子是不是正 確。2. 運(yùn)行結(jié)果本次實(shí)驗(yàn)多個(gè)功能需分別截圖，逐個(gè)說明。MHXMHXMHXMHXMHXMH JCH X運(yùn)行結(jié)果圖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í)驗(yàn)總結(jié)結(jié)果分析：本程序完成了樹的前序遍歷、中序遍歷、后序遍歷功能；但是還是存在不 完善的地方，沒有對結(jié)點(diǎn)進(jìn)行刪除增加等操作，沒有將樹的結(jié)構(gòu)給輸出。心得體會：通過這個(gè)實(shí)驗(yàn)我更熟練的掌握了二叉樹的結(jié)構(gòu)同時(shí)也更了解了遞歸算法， 覺得數(shù)據(jù)結(jié)構(gòu)是一個(gè)很不錯(cuò)的一門課程。代碼：#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