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

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

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

3、孩子為空的時(shí)候，應(yīng)當(dāng)輸入一個(gè)特殊的字符（本算法為“#”），表示左孩子或者右孩子為空。（3） 下一步，創(chuàng)建利用遞歸方法先序遍歷二叉樹(shù)的函數(shù)，函數(shù)為PreOrderTree()，創(chuàng)建非遞歸方法中序遍歷二叉樹(shù)的函數(shù)，函數(shù)為InOrderTree()，中序遍歷過(guò)程是：從二叉樹(shù)的根節(jié)點(diǎn)開(kāi)始，沿左子樹(shù)向下搜索，在搜索過(guò)程將所遇到的節(jié)點(diǎn)進(jìn)棧；左子樹(shù)遍歷完畢后，從棧頂退出棧中的節(jié)點(diǎn)并訪問(wèn)；然后再用上述過(guò)程遍歷右子樹(shù)，依次類(lèi)推，指導(dǎo)整棵二叉樹(shù)全部訪問(wèn)完畢。創(chuàng)建遞歸方法后序遍歷二叉樹(shù)的函數(shù)，函數(shù)為L(zhǎng)aOrderTree()。（提示：該部分主要是利用C、C+等完成數(shù)據(jù)結(jié)構(gòu)定義、設(shè)計(jì)算法實(shí)現(xiàn)各種操作，可以用列表分步形

4、式的自然語(yǔ)言描述，也可以利用流程圖等描述）4) 編碼#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedef char DataType;#define MaxSize 100typedef struct NodeDataType data;struct Node *lchild;struct Node *rchild;*BiTree,BitNode;void InitBitTree(BiTree *T); /*樹(shù)的初始化*/void CreateBitTree(BiTree *T); /*按照

5、先序輸入字符序列遞歸創(chuàng)建二叉樹(shù)*/void PreOrderTraverse(BiTree T);/*二叉樹(shù)的先序遍歷的遞歸函數(shù)聲明*/void InOrderTraverse(BiTree T);/*二叉樹(shù)的中序遍歷的遞歸函數(shù)聲明*/void PostOrderTraverse(BiTree T);/*二叉樹(shù)的后序遍歷的遞歸函數(shù)聲明*/void PreOrderTraverse2(BiTree T);/*二叉樹(shù)的先序遍歷的非遞歸函數(shù)聲明*/void InOrderTraverse2(BiTree T);/*二叉樹(shù)的中序遍歷的非遞歸函數(shù)聲明*/void PostOrderTraverse2(B

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

7、ntf("n");printf("二叉樹(shù)的中序序列：n");printf("遞歸：t");InOrderTraverse(T);printf("n");printf("非遞歸：");InOrderTraverse2(T);printf("n");printf("二叉樹(shù)的后序序列：n");printf("遞歸：t");PostOrderTraverse(T);printf("n");printf("非遞歸：&

8、quot;);PostOrderTraverse2(T);printf("n");void InitBitTree(BiTree *T)*T=NULL;void CreateBitTree(BiTree *T)/*遞歸創(chuàng)建二叉樹(shù)*/ DataType ch; scanf("%c",&ch); if(ch='#') *T=NULL; else *T=(BiTree)malloc(sizeof(BitNode); /*生成根結(jié)點(diǎn)*/ if(!(*T) exit(-1); (*T)->data=ch; CreateBitTree(

9、&(*T)->lchild); /*構(gòu)造左子樹(shù)*/ CreateBitTree(&(*T)->rchild); /*構(gòu)造右子樹(shù)*/ void PreOrderTraverse(BiTree T)/*先序遍歷二叉樹(shù)的遞歸實(shí)現(xiàn)*/ if(T)/*如果二叉樹(shù)不為空*/ printf("%2c",T->data); /*訪問(wèn)根結(jié)點(diǎn)*/ PreOrderTraverse(T->lchild);/*先序遍歷左子樹(shù)*/ PreOrderTraverse(T->rchild); /*先序遍歷右子樹(shù)*/ void InOrderTraverse(

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

11、e(T->rchild); /*后序遍歷右子樹(shù)*/printf("%2c",T->data); /*訪問(wèn)根結(jié)點(diǎn)*/ void PreOrderTraverse2(BiTree T)/*先序遍歷二叉樹(shù)的非遞歸實(shí)現(xiàn)*/BiTree stackMaxSize; /*定義一個(gè)棧，用于存放結(jié)點(diǎn)的指針*/int top; /*定義棧頂指針*/BitNode *p; /*定義一個(gè)結(jié)點(diǎn)的指針*/top=0;/*初始化棧*/p=T;while(p!=NULL|top>0)while(p!=NULL) /*如果p不空，訪問(wèn)根結(jié)點(diǎn)，遍歷左子樹(shù)*/printf("%2c

12、",p->data); /*訪問(wèn)根結(jié)點(diǎn)*/stacktop+=p; /*將p入棧*/p=p->lchild; /*遍歷左子樹(shù)*/if(top>0) /*如果棧不空*/p=stack-top; /*棧頂元素出棧*/p=p->rchild;/*遍歷右子樹(shù)*/void InOrderTraverse2(BiTree T)/*中序遍歷二叉樹(shù)的非遞歸實(shí)現(xiàn)*/BiTree stackMaxSize; /*定義一個(gè)棧，用于存放結(jié)點(diǎn)的指針*/int top; /*定義棧頂指針*/BitNode *p; /*定義一個(gè)結(jié)點(diǎn)的指針*/top=0;/*初始化棧*/p=T;while(

13、p!=NULL|top>0)while(p!=NULL) /*如果p不空，訪問(wèn)根結(jié)點(diǎn)，遍歷左子樹(shù)*/stacktop+=p; /*將p入棧*/p=p->lchild; /*遍歷左子樹(shù)*/if(top>0) /*如果棧不空*/p=stack-top; /*棧頂元素出棧*/printf("%2c",p->data); /*訪問(wèn)根結(jié)點(diǎn)*/p=p->rchild;/*遍歷右子樹(shù)*/void PostOrderTraverse2(BiTree T)/*后序遍歷二叉樹(shù)的非遞歸實(shí)現(xiàn)*/BiTree stackMaxSize; /*定義一個(gè)棧，用于存放結(jié)點(diǎn)的指

14、針*/int top; /*定義棧頂指針*/BitNode *p,*q; /*定義結(jié)點(diǎn)的指針*/top=0;/*初始化棧*/p=T,q=NULL; /*初始化結(jié)點(diǎn)的指針*/while(p!=NULL|top>0)while(p!=NULL) /*如果p不空，訪問(wèn)根結(jié)點(diǎn)，遍歷左子樹(shù)*/stacktop+=p; /*將p入棧*/p=p->lchild; /*遍歷左子樹(shù)*/if(top>0) /*如果棧不空*/p=stacktop-1; /*取棧頂元素*/if(p->rchild=NULL|p->rchild=q) /*如果p沒(méi)有右孩子結(jié)點(diǎn)，或右孩子結(jié)點(diǎn)已經(jīng)訪問(wèn)過(guò)*/printf("%2c",p->data); /*訪問(wèn)根結(jié)點(diǎn)*/q=p; p=NULL;top-;elsep=p->rchild;（提示：該部分主要是將算法轉(zhuǎn)化為C、C+程序，設(shè)計(jì)主函數(shù)完成對(duì)各成員函數(shù)的調(diào)用；設(shè)計(jì)人機(jī)界面，每一步需要用戶操作的提示以及每一次用戶操作產(chǎn)生的預(yù)期結(jié)果）四、 運(yùn)行與測(cè)試1) 在調(diào)試程序的過(guò)程中遇到什么問(wèn)題，是如何解決的？在調(diào)試程序的過(guò)