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

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

2、點數(shù) 4求二叉樹的深度 三、實驗步驟、數(shù)據(jù)結(jié)構與核心算法的設計描述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ù)設計 程序調(diào)試及運行結(jié)果分析如結(jié)果所示，該

3、程序?qū)崿F(xiàn)了先序創(chuàng)建二叉樹，先序遍歷，中序遍歷，后序遍歷及求深度，求節(jié)點數(shù)等功能。（4） 實驗總結(jié) 該實驗主要是對二叉樹的基本操作進行了訓練。在實驗的過程中，我熟悉了二叉樹的構造方法，以及二叉樹的一些操作，通過此次實驗，我對二叉樹的基本構造方法以及怎么使用遞歸的方法有了更深的理解。四、主要算法流程圖及程序清單 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(); /構造左子樹T-rchild=CreatBinTree(); /構造右子樹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