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

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

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

3、一步，創(chuàng)建利用遞歸方法先序遍歷二義樹的函數(shù)，函數(shù)為PreOrderTree(),創(chuàng)建非遞歸方法中序遍歷二義樹的函數(shù),函數(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)各種操2) 作，可以用列表分步形式的自然語言描述，也可以利用流程圖等描述)編碼#include<stdio.h&g

4、t;#include<malloc.h>#include<stdlib.h>typedefcharDataType;#defineMaxSize100typedefstructNodeDataTypedata;structNode*lchild;structNode*rchild;*BiTree,BitNode;/*樹的初始化*/*按照先序輸入字符序列遞歸創(chuàng)建二叉樹*/*二叉樹的先序遍歷的遞歸函數(shù)聲明*/*二叉樹的中序遍歷的遞歸函數(shù)聲明*/二叉樹的后序遍歷的遞歸函數(shù)聲明*/二叉樹的先序遍歷的非遞歸函數(shù)聲明*/*二叉樹的中序遍歷的非遞歸函數(shù)聲明*/*二叉樹的后序遍歷的非遞

5、歸函數(shù)聲明voidInitBitTree(BiTree*T);voidCreateBitTree(BiTree*T);voidPreOrderTraverse(BiTreeT);voidInOrderTraverse(BiTreeT);voidPostOrderTraverse(BiTreeT);/*voidPreOrderTraverse2(BiTreeT);/*voidInOrderTraverse2(BiTreeT);voidPostOrderTraverse2(BiTreeT);*/voidmain()BiTreeT,root;InitBitTree(&T);printf(&q

6、uot;根據(jù)輸入二叉樹的先序序列創(chuàng)建二叉樹('#'表示結(jié)束):n");CreateBitTree(&T);printf("二叉樹的先序序列：n");printf("遞歸:t");PreOrderTraverse(T);printf("n");printf(-非遞歸：")；PreOrderTraverse2(T);printf("n");printf("二叉樹的中序序列：n");printf("遞歸:t");InOrderTraver

7、se(T);printf("n");printf(-非遞歸：")；InOrderTraverse2(T);printf("n");printf(-二叉樹的后序序列：n");printf("遞歸:t");PostOrderTraverse(T);printf("n");printf(-非遞歸：")；PostOrderTraverse2(T);printf("n");voidInitBitTree(BiTree*T)*T=NULL;voidCreateBitTree(B

8、iTree*T)/*遞歸創(chuàng)建二叉樹*/DataTypech;scanf("%c”,&ch);if(ch='#')*T=NULL;else*T=(BiTree)malloc(sizeof(BitNode);if(!(*T)exit(-1);(*T)->data=ch;CreateBitTree(&(*T)->lchild);CreateBitTree(&(*T)->rchild);/*生成根結(jié)點(diǎn)*/*構(gòu)造左子樹*/*構(gòu)造右子樹*/voidPreOrderTraverse(BiTreeT)/*先序遍歷二叉樹的遞歸實(shí)現(xiàn)*/if(T)

9、printf("%2c”,T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);voidInOrderTraverse(BiTreeT)/*中序遍歷二叉樹的遞歸實(shí)現(xiàn)*/if(T)InOrderTraverse(T->lchild);printf("%2c”,T->data);InOrderTraverse(T->rchild);voidPostOrderTraverse(BiTreeT)/*后序遍歷二叉樹的遞歸實(shí)現(xiàn)*/if(T)PostOrderTraverse(

10、T->lchild);PostOrderTraverse(T->rchild);printf("%2c”,T->data);/*如果二叉樹不為空*/*訪問根結(jié)點(diǎn)*/*先序遍歷左子樹*/*先序遍歷右子樹*/*如果二叉樹不為空*/*中序遍歷左子樹*/*訪問根結(jié)點(diǎn)*/*中序遍歷右子樹*/*如果二叉樹不為空*/*后序遍歷左子樹*/*后序遍歷右子樹*/*訪問根結(jié)點(diǎn)*/*定義一個棧，用于存放結(jié)點(diǎn)的指針*/*定義棧頂指針*/*定義一個結(jié)點(diǎn)的指針*/*初始化棧*/*如果p不空，訪問根結(jié)點(diǎn)，遍歷左子/*訪問根結(jié)點(diǎn)*/*將p入棧*/*遍歷左子樹*/*如果棧不空*/*棧頂元素出棧*/*遍

11、歷右子樹*/*定義一個棧，用于存放結(jié)點(diǎn)的指針*/*定義棧頂指針*/*定義一個結(jié)點(diǎn)的指針*/*初始化棧*/*如果p不空，訪問根結(jié)點(diǎn)，遍歷左子voidPreOrderTraverse2(BiTreeT)/*先序遍歷二叉樹的非遞歸實(shí)現(xiàn)*/(BiTreestackMaxSize;inttop;BitNode*p;top=0;P=T;while(p!=NULL|top>0)(while(p!=NULL)樹*/(printf("%2c”,p->data);stacktop+=p;p=p->lchild;if(top>0)(p=stack-top;p=p->rchil

12、d;voidInOrderTraverse2(BiTreeT)/*中序遍歷二叉樹的非遞歸實(shí)現(xiàn)*/(BiTreestackMaxSize;inttop;BitNode*p;top=0;p=T;while(p!=NULL|top>0)(while(p!=NULL)樹*/stacktop+=p;p=p->lchild;if(top>0)(p=stack-top;printf("%2c”,p->data);p=p->rchild;voidPostOrderTraverse2(BiTreeT)/*后序遍歷二叉樹的非遞歸實(shí)現(xiàn)*/(BiTreestackMaxSize

13、;inttop;BitNode*p,*q;top=0;p=T,q=NULL;while(p!=NULL|top>0)(while(p!=NULL)左子樹*/(stacktop+=p;p=p->lchild;if(top>0)(p=stacktop-1;if(p->rchild=NULL|p->rchild=q)右孩子結(jié)點(diǎn)已經(jīng)訪問過*/(printf("%2c",p->data);q=p;/*將p入棧*/*遍歷左子樹*/*如果棧不空*/*棧頂元素出棧*/*訪問根結(jié)點(diǎn)*/*遍歷右子樹*/*定義一個棧，用于存放結(jié)點(diǎn)的指針*/*定義棧頂指針*/*

14、定義結(jié)點(diǎn)的指針*/*初始化棧*/*初始化結(jié)點(diǎn)的指針*/*如果p不空，訪問根結(jié)點(diǎn)，遍歷/*將p入棧*/*遍歷左子樹*/*如果棧不空*/*取棧頂元素*/*如果p沒有右孩子結(jié)點(diǎn)，或/*訪問根結(jié)點(diǎn)*/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)行與測試1)在調(diào)試程序的過程中遇到什么問題，是如何解決的？在調(diào)試程序的過程中，遇到最大的問題就是中序和后序不能正確表示答案是因?yàn)閮蓚€函數(shù)的錯誤導(dǎo)致2)設(shè)計(jì)了哪些測試數(shù)據(jù)？測試結(jié)果是什么？abd#e#c#測試結(jié)果：前序：abdec中序：dbeac后序：debca3)程序運(yùn)行結(jié)果如何？g*C:Docu>entsandSettingsAdAin±stratorDebugCpp1.exe*ff艮據(jù)輸入二叉樹的先序序列創(chuàng)建二叉樹b