數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)4-3.doc

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