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

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

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

3、程序?qū)崿F(xiàn)了先序創(chuàng)建二叉樹，先序遍歷，中序遍歷，后序遍歷及求深度，求節(jié)點數(shù)等功能。（4） 實驗總結(jié) 該實驗主要是對二叉樹的基本操作進行了訓(xùn)練。在實驗的過程中，我熟悉了二叉樹的構(gòu)造方法，以及二叉樹的一些操作，通過此次實驗，我對二叉樹的基本構(gòu)造方法以及怎么使用遞歸的方法有了更深的理解。四、主要算法流程圖及程序清單 1、主要算法流程圖 2、程序清單 #include#include#includetypedef struct node char data; struct node *lchild,*rchild;BinTNode, *BinTree; /定義二叉樹的指針BinTree CreatBin

4、Tree(void)/先序遍歷算法創(chuàng)建二叉樹 BinTree T; char ch; if(ch=getchar()= ) return(NULL); elseT=(BinTNode *)malloc(sizeof(BinTNode); T-data=ch;T-lchild=CreatBinTree(); /構(gòu)造左子樹T-rchild=CreatBinTree(); /構(gòu)造右子樹return(T);/先序遍歷void Preorder(BinTree T) if(T) printf(%c,T-data); Preorder(T-lchild); Preorder(T-rchild); /中序遍

5、歷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); printf(%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; NodeNu

6、m=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);else return 0;/主函數(shù)void main() BinTree root; int i,depth，NodeNum; printf(創(chuàng)建二叉樹； 輸入節(jié)點序列(用空格鍵代表空節(jié)點):n); root=CreatBinTree(); printf(二叉樹創(chuàng)建成功!

7、nn); /創(chuàng)建二叉樹，返回根結(jié)點 printf(tt* 選擇操作 *n); printf(tt1: 先序遍歷n); printf(tt2: 中序遍歷n); printf(tt3: 后序遍歷n); printf(tt4: 求樹的深度，節(jié)點數(shù)n); printf(tt0: 結(jié)束n); printf(tt*n);while(scanf(%d,&i)/輸入菜單序號（0-4） switch (i) case 1: printf(先序遍歷: n); Preorder(root); break; case 2: printf(中序遍歷: n); Inorder(root); break; case 3: printf(后序遍歷:n ); Postorder(root); brea