創(chuàng)建一個(gè)二叉樹并輸出三種遍歷結(jié)果

1、實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)三一創(chuàng)建一個(gè)二叉樹并輸出三種遍歷結(jié)果系 別=一計(jì)算機(jī)學(xué)院_ _專 _班級/學(xué)號_學(xué)生姓名實(shí)驗(yàn)日期_成績指導(dǎo)教師實(shí)驗(yàn)題目：實(shí)驗(yàn)三創(chuàng)建一個(gè)二叉樹并輸出三種遍歷結(jié)果一、實(shí)驗(yàn)?zāi)康恼莆斩鏄浯鎯Y(jié)構(gòu)；掌握并實(shí)現(xiàn)二叉樹遍歷的遞歸算法和非遞歸算法理解樹及森林對二叉樹的轉(zhuǎn)換；理解二叉樹的應(yīng)用哈夫曼編碼及 WPL 計(jì)算。二、實(shí)驗(yàn)內(nèi)容以廣義表或遍歷序列形式創(chuàng)建一個(gè)二叉樹，存儲結(jié)構(gòu)自選；輸出先序、中序、后序遍歷序列；二選一應(yīng)用題：1)樹和森林向二叉樹轉(zhuǎn)換；2)哈夫曼編碼的應(yīng)用問題。(應(yīng)用型題目可替換上述前兩項(xiàng)實(shí)驗(yàn)內(nèi)容)三、設(shè)計(jì)與編碼程序結(jié)構(gòu)基本設(shè)計(jì)框架本實(shí)驗(yàn)用到的理論知識 遍歷二

2、叉樹，遞歸和非遞歸的方法(提示：總結(jié)本實(shí)驗(yàn)用到的理論知識，實(shí)現(xiàn)理論與實(shí)踐相結(jié)合?？偨Y(jié)盡量簡明扼要，并與本次實(shí)驗(yàn)密切相關(guān)，要求結(jié)合自己的題目并 闡述自己的理解和想法)具體算法設(shè)計(jì)首先，定義二叉樹的存儲結(jié)構(gòu)為二叉鏈表存儲，每個(gè)元素的數(shù)據(jù)類型Elemtype，定義一棵二叉樹，只需定義其根指針。然后以遞歸的先序遍歷方法創(chuàng)建二叉樹，函數(shù)為CreateTree(),在輸入字符時(shí)要注意，當(dāng)節(jié)點(diǎn)的左孩子或者右孩子為空的時(shí)候，應(yīng)當(dāng)輸入一個(gè)特殊的字符(本算法為“#”)，表示左孩子或者右孩子為空。下一步，創(chuàng)建利用遞歸方法先序遍歷二叉樹的函數(shù)，函數(shù)為PreOrderTree()，創(chuàng)建非遞歸方法中序遍歷二叉樹的函數(shù)，函

3、數(shù)為InOrderTree()，中序遍歷過程是：從二叉樹的根節(jié)點(diǎn)開始，沿左子樹向下搜索，在搜索過程將所遇到的節(jié)點(diǎn)進(jìn)棧；左子樹遍歷完畢后，從棧頂退出棧中的節(jié)點(diǎn)并訪問；然后再用上述過程遍歷右子樹，依次類推，指導(dǎo)整棵二叉樹全部訪問完畢。創(chuàng)建遞歸方法后序遍歷二叉樹的函數(shù)，函數(shù)為LaOrderTree()。(提示：該部分主要是利用C、C+等完成數(shù)據(jù)結(jié)構(gòu)定義、設(shè)計(jì)算法實(shí)現(xiàn)各種操作，可以用列表分步形式的自然語言描述，也可以利用 流程圖等描述)4) 編碼#include#include#includetypedef char DataType;#define MaxSize 100typedef struct

4、 NodeDataType data; struct Node *lchild; struct Node *rchild; *BiTree,BitNode;void InitBitTree(BiTree *T);/*樹的初始化*/void CreateBitTree(BiTree *T);/*按照先序輸入字符序列遞歸創(chuàng)建二叉樹*/void PreOrderTraverse(BiTree T); /*二叉樹的先序遍歷的 遞歸函數(shù)聲明*/void InOrderTraverse(BiTree T); /*二叉樹的中序遍歷的 遞歸函數(shù)聲明*/void PostOrderTraverse(BiTree

5、 T); /*二叉樹的后序遍歷的 遞歸函數(shù)聲明*/void PreOrderTraverse2(BiTree T); /*二叉樹的先序遍歷的 非遞歸函數(shù)聲明*/void InOrderTraverse2(BiTree T); /*二叉樹的中序遍歷的 非遞歸函數(shù)聲明*/void PostOrderTraverse2(BiTree T); /*二叉樹的后序遍歷的 非遞歸函數(shù)聲明*/void main()BiTree T,root; InitBitTree(&T);printf (根據(jù)輸入二叉樹的先序序列創(chuàng)建二叉樹(#表示結(jié) 束)：n);CreateBitTree(&T);printf(二叉樹的先序

6、序列：n); printf(遞歸：t);PreOrderTraverse(T);printf(n); printf(非遞歸：)；PreOrderTraverse2(T);printf(n);printf(二叉樹的中序序列：n);printf(遞歸：t);InOrderTraverse(T); printf(n);printf(非遞歸：”);InOrderTraverse2(T); printf(n);printf(二叉樹的后序序列：n); printf(遞歸：t);PostOrderTraverse(T); printf(n);printf(非遞歸：”)；PostOrderTraverse2(

7、T); printf(n);void InitBitTree(BiTree *T)*T=NULL;void CreateBitTree(BiTree *T) /*遞歸創(chuàng)建二叉樹*/DataType ch; scanf(%c,&ch); if(ch=#) *T=NULL;else /*生成根/*構(gòu)造左/*構(gòu)造右*T=(BiTree)malloc(sizeof(BitNode); 結(jié)點(diǎn)*/*生成根/*構(gòu)造左/*構(gòu)造右if(!(*T) exit(-1);(*T)-data=ch; CreateBitTree(&(*T)-lchild); 子樹*/CreateBitTree(&(*T)-rchild)

8、;子樹*/void PreOrderTraverse(BiTree T)/*先序遍歷二叉樹的遞歸實(shí)現(xiàn)*/樹*/樹*/if(T)/*如果二叉樹不為空*/ 樹*/樹*/if(T)/*如果二叉樹不為空*/ printf(%2c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);/*訪問根結(jié)點(diǎn)*/*先序遍歷左子/*先序遍歷右子void InOrderTraverse(BiTree T)/*中序遍歷二叉樹的遞歸實(shí)現(xiàn)*/if(T)/*如果二叉樹不為空*/if(T)樹*/樹*/*中序遍歷左子樹*/樹*/*中序遍歷左子/*訪問根結(jié)點(diǎn)*/

9、*中序遍歷右子printf(%2c,T-data);InOrderTraverse(T-rchild);void PostOrderTraverse(BiTree T)/*后序遍歷二叉樹的遞歸實(shí)現(xiàn)*/if(T) /*如果二叉樹不為空*/PostOrderTraverse(T-lchild);/*后序遍歷左子樹*/PostOrderTraverse(T-rchild);/*后序遍歷右子樹*/printf(%2c,T-data);/*訪問根結(jié)點(diǎn)*/*定義一個(gè)棧，用于/*定義棧頂指針*/ /*定義一個(gè)結(jié)點(diǎn)的指針*/*初始化棧*/void PreOrderTraverse2(BiTree T) /*定

10、義一個(gè)棧，用于/*定義棧頂指針*/ /*定義一個(gè)結(jié)點(diǎn)的指針*/*初始化棧*/BiTree stackMaxSize; 存放結(jié)點(diǎn)的指針*/ int top;BitNode *p; top=0; p=T;while(p!=NULL|top0) /*如果p不空，訪問根結(jié)/*如果p不空，訪問根結(jié)/*訪問根結(jié)點(diǎn)*/*將 p入棧*/*遍歷左子樹*/*如果棧不空*/*棧頂元素出棧*/*遍歷右子樹*/ printf(%2c,p-data); stacktop+=p; p=p-lchild; if(top0) p=stack-top; p=p-rchild;/*定義一個(gè)棧，用于/*定義棧頂指針*/ /*定義一個(gè)

11、結(jié)點(diǎn)的指針*/*初始化棧*/void InOrderTraverse2(BiTree T) /*定義一個(gè)棧，用于/*定義棧頂指針*/ /*定義一個(gè)結(jié)點(diǎn)的指針*/*初始化棧*/BiTree stackMaxSize; 存放結(jié)點(diǎn)的指針*/ int top;BitNode *p; top=0; p=T;while(p!=NULL|top0)/*如果p不空，訪問根結(jié)/*將/*如果p不空，訪問根結(jié)/*將p入棧*/*遍歷左子樹*/*如果棧不空*/*棧頂元素出棧*/*訪問根結(jié)點(diǎn)*/*遍歷右子樹*/BiTree stackMaxSize;存放結(jié)點(diǎn)的指針*/int top;BitNode *p,*q;top=0

12、;p=T,q=NULL;while(p!=NULL|top0) while(p!=NULL) 根結(jié)點(diǎn)，遍歷左子樹*/stacktop+=p; p=p-lchild;if(top0)p=stacktop-1;/*定義一個(gè)棧，用于/*定義棧頂指針*/ /*定義結(jié)點(diǎn)的指針*/*初始化棧*/*初始化結(jié)點(diǎn)的指針*/*如果p不空，訪問/*將p入棧*/*遍歷左子樹*/*如果棧不空*/*取棧頂元素*/while(p!=NULL)點(diǎn)，遍歷左子樹*/stacktop+=p; p=p-lchild;if(top0)p=stack-top;printf(%2c,p-data); p=p-rchild;void Pos

13、tOrderTraverse2(BiTree T) /*后序遍歷二叉樹的非遞歸實(shí)現(xiàn)*/ if(p-rchild=NULL|p-rchild=q)/*如果 p 沒有右孩子結(jié)點(diǎn)，或右孩子結(jié)點(diǎn)已經(jīng)訪問過*/printf(%2c,p-data);/*訪問根結(jié)點(diǎn)printf(%2c,p-data);/*訪問根結(jié)點(diǎn)*/q=p;p=NULL;top-;elsep=p-rchild;(提示：該部分主要是將算法轉(zhuǎn)化為C、C+程序，設(shè)計(jì)主函數(shù)完成 對各成員函數(shù)的調(diào)用；設(shè)計(jì)人機(jī)界面，每一步需要用戶操作的提示 以及每一次用戶操作產(chǎn)生的預(yù)期結(jié)果)四、運(yùn)行與測試在調(diào)試程序的過程中遇到什么問題，是如何解決的 在調(diào)試程序的過程中，遇到最大的問題就是中序和后序不能正確表示 答案，最后發(fā)現(xiàn)是因?yàn)閮蓚€(gè)函數(shù)的錯(cuò)誤導(dǎo)致。設(shè)計(jì)了哪些測試數(shù)據(jù)測試結(jié)果是什么abd#e#c#測試結(jié)果：前序：abdec中序：dbeac后序：debca3) 測試結(jié)果：前序：abdec中序：dbeac后序：debca3) 程序運(yùn)行結(jié)果如何Habdec abdec帥 *C: YDDcuient s and Sett ings&dAinist ratorDebugXCpp 1. exe醍據(jù)輸卜二處的先序斥列創(chuàng)逹二翼檳葉舂六結(jié)車； Exw的尢序療