數(shù)據(jù)結(jié)構(gòu)二叉樹實踐報告1

1、成績：實 驗 報 告課程名稱：數(shù)據(jù)結(jié)構(gòu)實驗實驗項目：二叉樹的建立及遍歷姓 名：專 業(yè)：班 級：學(xué) 號：計算機(jī)科學(xué)與技術(shù)學(xué)院實驗教學(xué)中心2017 年 11 月 17 日實驗項目名稱： 二叉樹的建立及遍歷 一、實驗?zāi)康模?1)熟練掌握二叉樹的建立方法；(2)熟練掌握二叉樹的遍歷算法；(3)掌握二叉樹的應(yīng)用算法。二、實驗內(nèi)容：(1)編寫算法建立一棵二叉樹的二叉鏈表；(2)輸出二叉樹的三種遍歷序列，包括遞歸算法、非遞歸算法；(3)編寫算法統(tǒng)計二叉樹結(jié)點數(shù)、葉子數(shù)、深度。A三、實驗結(jié)果分析ABCBCFDEED四、實驗操作步驟按先序遍歷順序輸入建樹，空節(jié)點輸入#代替，采用遞歸建樹。輸出結(jié)果為該樹按先序遍歷

2、、中序遍歷、后序遍歷的順序序列。并計算輸出該樹的深度、葉子節(jié)點數(shù)量、總結(jié)點數(shù)量之后按層序遍歷順序輸入建立完全二叉樹，采用非遞歸建樹。輸出結(jié)果為該樹按先序遍歷、中序遍歷、后序遍歷的順序序列。并計算輸出該樹的深度、葉子節(jié)點數(shù)量、總結(jié)點數(shù)量五、源代碼#include<stdio.h>#include <cstdlib>#include <iostream>#include <stack>using namespace std;/二叉樹定義typedef char ElementType;typedef struct BiTreeNode Element

3、Type data; struct BiTreeNode* lchild; struct BiTreeNode* rchild; BiTreeNode, *BiTree;/遞歸的建立一棵二叉樹/輸入為二叉樹的先序序列void createBiTree(BiTree &T) char data; data = getchar(); if(data = '#') T = NULL; else T = new BiTreeNode; T->data = data; createBiTree(T->lchild); createBiTree(T->rchild

4、); void creatBiTree_2(BiTree &rt,int n) char root2; scanf("%s",root); rt=new BiTreeNode; rt->data=root0; for(int i=2; i<=n; i+) BiTreeNode* T=rt; char tmp2; int num=0,a16; scanf("%s",tmp); int ii=i; while(ii) anum+=ii%2; ii/=2; BiTreeNode *node=new BiTreeNode; node->

5、data=tmp0; node->rchild=NULL; node->lchild=NULL; for(int j=num-2; j>0; j-) if(aj)T=T->rchild; else T=T->lchild; if(a0)T->rchild=node; else T->lchild=node; int Nodenum(BiTreeNode* root)/二叉樹節(jié)點數(shù)目 if(root = NULL) return 0; else return 1+Nodenum(root->lchild)+Nodenum(root->rchi

6、ld);/遞歸銷毀一棵二叉樹void destroyBiTree(BiTree &T) if(T) destroyBiTree(T->lchild); destroyBiTree(T->rchild); delete T; T = NULL; /遞歸先序遍歷二叉樹void preOrderTraverse(const BiTree &T) if(T) cout<<T->data<<" "/輸出根節(jié)點值 preOrderTraverse(T->lchild);/遍歷左子樹 preOrderTraverse(T-&

7、gt;rchild);/遍歷右子樹 /遞歸中序遍歷二叉樹void inOrderTraverse(const BiTree &T) if(T) inOrderTraverse(T->lchild);/遍歷左子樹 cout<<T->data<<" "/輸出根節(jié)點值 inOrderTraverse(T->rchild);/遍歷右子樹 /遞歸后序遍歷二叉樹void postOrderTraverse(const BiTree &T) if(T) postOrderTraverse(T->lchild);/遍歷左子樹

8、postOrderTraverse(T->rchild);/遍歷右子樹 cout<<T->data<<" "/輸出根節(jié)點值 /遞歸求樹的深度int depthOfBiTree(const BiTree &T) int ldepth; int rdepth; if(T=NULL)/空樹 return 0; ldepth = depthOfBiTree(T->lchild); rdepth = depthOfBiTree(T->rchild); return (ldepth>rdepth)?(ldepth+1):(r

9、depth+1);/遞歸求二叉樹的葉子結(jié)點個數(shù)int leafCountOfBiTree(const BiTree &T) if(T=NULL) return 0; if(T->lchild=NULL && T->rchild=NULL) return 1; return leafCountOfBiTree(T->lchild) + leafCountOfBiTree(T->rchild);int main(int argc, char *argv) BiTree T = NULL; createBiTree(T);/建立二叉樹 AB#D#CE#

10、 cout<<"先序遍歷: " /先序遍歷 preOrderTraverse(T); cout<<endl; cout<<"中序遍歷: "/中序遍歷 inOrderTraverse(T); cout<<endl; cout<<"后序遍歷: "/后序遍歷 postOrderTraverse(T); cout<<endl; cout<<"深度: "<<depthOfBiTree(T)<<endl;/樹的高度 co

11、ut<<"葉子結(jié)點數(shù): "<<leafCountOfBiTree(T)<<endl;/葉子結(jié)點數(shù) cout<<"總結(jié)點數(shù)量: "<<Nodenum(T)<<endl; destroyBiTree(T);/銷毀二叉樹，釋放空間 int n; scanf("%d",&n); BiTree TT=NULL; creatBiTree_2(TT,n); cout<<"先序遍歷: " /先序遍歷 preOrderTraverse(TT); cout<<endl; cout<<"中序遍歷: "/中序遍歷 inOrderTraverse(TT); cout<<endl; cout<<"后序遍歷: "/后序遍歷 postOrderTraverse(TT); cout<<endl; cout<<"深度: "<<depthOfBiTree(TT)<<endl;/樹的高度 cout<<"葉子結(jié)點數(shù): "&l