二叉樹(shù)的基本操作實(shí)現(xiàn)及其應(yīng)用

1、中原工學(xué)院軟件學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目名稱 二叉樹(shù)的基本操作實(shí)現(xiàn)及其應(yīng)用課程名稱數(shù)據(jù)結(jié)構(gòu)學(xué)生學(xué)生學(xué)號(hào)所在班級(jí)學(xué)科專業(yè)任課教師完成日期一、實(shí)驗(yàn)?zāi)康?熟悉二叉樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)和對(duì)二叉樹(shù)的基本操作。 2掌握對(duì)二叉樹(shù)每一種操作的具體實(shí)現(xiàn)。3學(xué)會(huì)利用遞歸方法編寫對(duì)二叉樹(shù)這種遞歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。4.會(huì)用二叉樹(shù)解決簡(jiǎn)單的實(shí)際問(wèn)題。二、實(shí)驗(yàn)容題目一設(shè)計(jì)程序?qū)崿F(xiàn)二叉樹(shù)結(jié)點(diǎn)的類型定義和對(duì)二叉樹(shù)的基本操作 該程序包括二叉樹(shù)結(jié)構(gòu)類型以及每一種操作的具體的函數(shù)定義和主函數(shù) 1 按先序次序建立一個(gè)二叉樹(shù)，2按 (A:先序B:中序C:后序)遍歷輸岀二叉樹(shù)的所有結(jié)點(diǎn)以上比做，以下選做求二叉樹(shù)中所有結(jié)點(diǎn)數(shù)求二叉樹(shù)的深度三、實(shí)驗(yàn)

2、步驟、數(shù)據(jù)結(jié)構(gòu)與核心算法的設(shè)計(jì)描述typedef struct nodechar data;struct node *lchild,*rchild;BinTNode, *BinTree; /定義二叉樹(shù)的指針BinTree CreatBinTree(void)/先序遍歷算法創(chuàng)建二叉樹(shù)void Preorder(BinTree T)先序遍歷void Inorder(BinTree T)中序遍歷void Postorder(BinTree T)后序遍歷int TreeDepth(BinTree T)求 深度(二)、函數(shù)調(diào)用及主函數(shù)設(shè)計(jì)程序調(diào)試及運(yùn)行結(jié)果分析勒序遍歷：de ba*后序謹(jǐn)歷， 二賈樹(shù)深度

3、科嚴(yán)J程一尺勒序遍歷：de ba*后序謹(jǐn)歷， 二賈樹(shù)深度科嚴(yán)J程一尺PJI刑八P點(diǎn)序列用三格鋰代；表王卩點(diǎn)xabed二冥樹(shù)創(chuàng)建成功T數(shù) 點(diǎn) 一 度 歷歷無(wú) 逅黑的 先中后t結(jié)九序遍歷；二叉樹(shù)節(jié)點(diǎn)數(shù)N如結(jié)果所示，該程序?qū)崿F(xiàn)了先序創(chuàng)建二叉樹(shù)，先序遍歷，中序遍 歷，后序遍歷及求深度，求節(jié)點(diǎn)數(shù)等功能。（四）實(shí)驗(yàn)總結(jié) 該實(shí)驗(yàn)主要是對(duì)二叉樹(shù)的基本操作進(jìn)行了訓(xùn)練。在實(shí)驗(yàn)的過(guò)程中，我 熟悉了二叉樹(shù)的構(gòu)造方法，以及二叉樹(shù)的一些操作，通過(guò)此次實(shí)驗(yàn)， 我對(duì)二叉樹(shù)的基本構(gòu)造方法以及怎么使用遞歸的方法有了更深的理 解。四、主要算法流程圖及程序清單1、主要算法流程圖+*先序遍歷 PreOrd&rQ中序遍歷 InOrder

4、Q后序遍歷 PostOrderQ12、程序清單#include#include#include typedef struct nodechar data;struct node *lchild,*rchild;BinTNode, *BinTree; /定義二叉樹(shù)的指針BinTree CreatBinTree(void)/先序遍歷算法創(chuàng)建二叉樹(shù) BinTree T; char ch;if(ch=getchar()= ) return(NULL);elseT=(BinTNode *)malloc(sizeof(BinTNode);T-data=ch;T-lchild=CreatBinTree();

5、/構(gòu)造左子樹(shù)T-rchild=CreatBinTree();/構(gòu)造右子樹(shù)return(T);/先序遍歷void Preorder(BinTree T)if(T)printf(%c,T-data);Preorder(T-lchild);Preorder(T-rchild);/中序遍歷void Inorder(BinTree T)if(T)Inorder(T-lchild);printf(%c,T-data);Inorder(T-rchild);/后序遍歷void Postorder(BinTree T)if(T)Postorder(T-lchild);Postorder(T-rchild);pr

6、intf(%c,T-data);int TreeDepth(BinTree T) int hl,hr,max;if(T)hl=TreeDepth(T-lchild); hr=TreeDepth(T-rchild); max=hlhr? hl:hr;NodeNum=NodeNum+1; return(max+1);else return(0);Int TreeNode(BinTree T)int NodeNum=0;if(T)TreeDepth(T-lchild);TreeDepth(T-rchild);NodeNum=NodeNum+1; return(NodeNum);elsereturn

7、0;/主函數(shù) void main()BinTree root;int i,depth，NodeNum;printf(創(chuàng)建二叉樹(shù)；輸入節(jié)點(diǎn)序列(用空格鍵代表空節(jié)點(diǎn)):n); root=CreatBinTree();printf（二叉樹(shù)創(chuàng)建成功!nn）;創(chuàng)建二叉樹(shù)，返回根結(jié)點(diǎn)printf（tt*選擇操作*n）;printf（tt*選擇操作*n）;printf（tt1:先序遍歷n）;printf（tt2:中序遍歷n）;printf（tt3:后序遍歷n）;printf（tt4:求樹(shù)的深度，節(jié)點(diǎn)數(shù)n）; printf（ttO:結(jié)束n）;printf（tt*汝printf（tt*汝*n）;while（scanf（%d，&i）輸入菜單序號(hào)（0-4）switch （i）case 1: printf（先序遍歷:n）;Preorder（root）; break;case 2: printf（中序遍歷:n）;Inorder（root）; break;case 3: printf（后序遍歷:n ）;Postorder（root）; break