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

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

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

3、Type data; struct BiTreeNode* lchild; struct BiTreeNode* rchild; BiTreeNode, *BiTree;/遞歸的建立一棵二叉樹(shù)/輸入為二叉樹(shù)的先序序列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)/二叉樹(shù)節(jié)點(diǎn)數(shù)目 if(root = NULL) return 0; else return 1+Nodenum(root->lchild)+Nodenum(root->rchi

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

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

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

9、depth+1);/遞歸求二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(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);/建立二叉樹(shù) AB#D#CE#

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

11、ut<<"葉子結(jié)點(diǎn)數(shù): "<<leafCountOfBiTree(T)<<endl;/葉子結(jié)點(diǎn)數(shù) cout<<"總結(jié)點(diǎn)數(shù)量: "<<Nodenum(T)<<endl; destroyBiTree(T);/銷(xiāo)毀二叉樹(shù)，釋放空間 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;/樹(shù)的高度 cout<<"葉子結(jié)點(diǎn)數(shù): "&l