數(shù)據(jù)結構實驗4-3.doc

數(shù)據(jù)結構實驗報告 實驗4 二叉樹遍歷算法的設計與實現(xiàn)實驗人： 學號: 時間：一、 實驗目的1. 掌握二叉樹的建立與存儲2. 掌握二叉樹的遍歷方法二、 實驗內(nèi)容編寫程序實現(xiàn)根據(jù)用戶輸入二叉樹的先序序列建立一棵二叉樹，并實現(xiàn)對此二叉樹的先序、中序、和后序遍歷。（算法6.4）三、 實驗步驟：1. 接收用戶輸入的先序序列建立以二叉鏈表為存儲結構的二叉樹（算法6.4）。2. 對建立好的二叉樹實現(xiàn)先序、中序、和后序遍歷，將遍歷后的序列輸出（參考算法6.1，6.3）。其中中序遍歷包括遞歸和非遞歸算法實現(xiàn)，先序、后序遍歷只要求遞歸算法實現(xiàn)即可。四、 算法說明 1.二叉樹的二叉鏈表存儲表示（結構體）2.按先序次序輸入二叉樹中結點的值，#表示空樹3.訪問二叉樹中元素4.遞歸先序遍歷5.遞歸中序遍歷6.遞歸后序遍歷7.主函數(shù)依次調用上述函數(shù)五、 測試結果對以下二叉樹進行驗證 A / B C / / D E F G 六、 分析與探討1.用按先序遍歷輸入的方法輸入的字符畫出二叉樹，看圖依次按先序、中序、后序的方法寫出遍歷后的序列與測試結果對比可知正確。2.我在本實驗中都是按遞歸的方法實現(xiàn)遍歷，用棧操作也實現(xiàn)了非遞歸的遍歷。七、 附錄：源代碼 #include#include/ 函數(shù)結果狀態(tài)代碼#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2 /因為在math.h中已定義OVERFLOW的值為3,故去掉此行#define STACK_INIT_SIZE 100 /存儲空間初始分配量#define STACKINCREMENT 10 / 存儲空間分配增量typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結果狀態(tài)代碼，如OK等typedef int Boolean; / Boolean是布爾類型,其值是TRUE或FALSE/二叉樹結點typedef struct BiTNode/數(shù)據(jù)char data;/左右孩子指針struct BiTNode *lchild,*rchild;BiTNode,*BiTree;typedef struct SqStackBiTree *base; / 在棧構造之前和銷毀之后，base的值為NULLBiTree *top; / 棧頂指針 */int stacksize; / 當前已分配的存儲空間，以元素為單位SqStack; / 順序棧/按先序序列創(chuàng)建二叉樹int CreateBiTree(BiTree &T)char data;/按先序次序輸入二叉樹中結點的值（一個字符），#表示空樹scanf(%c,&data);if(data = #)T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode);/生成根結點T-data = data;/構造左子樹CreateBiTree(T-lchild);/構造右子樹CreateBiTree(T-rchild);return 0;/輸出void Visit(BiTree T)if(T-data != #)printf(%c ,T-data);/先序遍歷void PreOrder(BiTree T)if(T != NULL)/訪問根節(jié)點Visit(T);/訪問左子結點PreOrder(T-lchild);/訪問右子結點PreOrder(T-rchild);/中序遍歷 void InOrder(BiTree T) if(T != NULL) /訪問左子結點 InOrder(T-lchild); /訪問根節(jié)點 Visit(T); /訪問右子結點 InOrder(T-rchild); /后序遍歷void PostOrder(BiTree T)if(T != NULL)/訪問左子結點PostOrder(T-lchild);/訪問右子結點PostOrder(T-rchild);/訪問根節(jié)點Visit(T);/棧的基本操作Status InitStack(SqStack &S) / 構造一個空棧SS.base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!S.base)exit(-2); /* 存儲分配失敗 */S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S) /* 若棧S為空棧，則返回TRUE，否則返回FALSE */if(S.top=S.base)return TRUE;elsereturn FALSE;Status GetTop(SqStack S,BiTree &e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR */if(S.topS.base)e=*(S.top-1);return OK;elsereturn ERROR;Status Push(SqStack &S,BiTree e) /* 插入元素e為新的棧頂元素 */if(S.top-S.base=S.stacksize) /* 棧滿，追加存儲空間 */S.base=(BiTree *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(!S.base)exit(-2); /* 存儲分配失敗 */S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,BiTree &e) /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */if(S.top=S.base)return ERROR;e=*-S.top;return OK; /* 先序遍歷(非遞歸) 思路：訪問T-data后，將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，再先序遍歷T的右子樹。*/void PreOrder2(BiTree T)/p是遍歷指針BiTree p = T;SqStack S;InitStack(S);/棧不空或者p不空時循環(huán)while(p | !StackEmpty(S)if(p != NULL)/存入棧中Push(S,p);/訪問根節(jié)點printf(%c ,p-data);/遍歷左子樹p = p-lchild;else/退棧Pop(S,p);/訪問右子樹p = p-rchild;/while/* 中序遍歷(非遞歸) 思路：T是要遍歷樹的根指針，中序遍歷要求在遍歷完左子樹后，訪問根，再遍歷右子樹。 先將T入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為T，出棧，訪問T-data，再中序遍歷T的右子樹。*/void InOrder2(BiTree T) SqStack S;/p是遍歷指針BiTree p = T;InitStack(S);/棧不空或者p不空時循環(huán)while(p | !StackEmpty(S)if(p != NULL)/存入棧中Push(S,p);/遍歷左子樹p = p-lchild;else/退棧，訪問根節(jié)點Pop(S,p);printf(%c ,p-data);/訪問右子樹p = p-rchild;/while/*/后序遍歷(非遞歸)typedef struct BiTNodePostBiTree biTree;char tag;BiTNodePost,*BiTreePost;void PostOrder2(BiTree T)stack stack;/p是遍歷指針BiTree p = T;BiTreePost BT;/棧不空或者p不空時循環(huán)while(p != NULL | !stack.empty()/遍歷左子樹while(p != NULL)BT = (BiTreePost)malloc(sizeof(BiTNodePost);BT-biTree = p;/訪問過左子樹BT-tag = L;stack.push(BT);p = p-lchild;/左右子樹訪問完畢訪問根節(jié)點while(!stack.empty() & (stack.top()-tag = R)BT = stack.top();/退棧stack.pop();printf(%c ,BT-biTree-data);/遍歷右子樹if(!stack.empty()BT = stack.top();/訪問過右子樹BT-tag = R;p = BT-biTree;p = p-rchild;/while/層次遍歷void LevelOrder(BiTree T)BiTree p = T;/隊列queue queue;/根節(jié)點入隊queue.push(p);/隊列不空循環(huán)while(!queue.empty()/對頭元素出隊p = queue.front();/訪問p指向的結點printf(%c ,p-data);/退出隊列queue.pop();/左子樹不空，將左子樹入隊if(p-lchild != NULL)queue.push(p-lchild);/右子樹不空，將右子樹入隊if(p-rchild != NULL)queue.push(p-rchild);*/int main()BiTree T;CreateBiTree(T);printf(先序遍歷：n);PreOrder(T);printf(n);printf(先序遍歷(非遞歸)：n);PreOrder2(T);printf(n);printf(中序遍歷：n);InOrder(T);printf(n);print