《数据结构二叉树实践报告1》由会员分享，可在线阅读，更多相关《数据结构二叉树实践报告1（7页珍藏版）》请在金锄头文库上搜索。
1、成绩：实 验 报 告课程名称：数据结构实验实验项目：二叉树的建立及遍历姓 名：专 业：班 级：学 号：计算机科学与技术学院实验教学中心2017 年 11 月 17 日哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告实验项目名称： 二叉树的建立及遍历 一、实验目的：(1)熟练掌握二叉树的建立方法；(2)熟练掌握二叉树的遍历算法；(3)掌握二叉树的应用算法。二、实验内容：(1)编写算法建立一棵二叉树的二叉链表；(2)输出二叉树的三种遍历序列，包括递归算法、非递归算法；(3)编写算法统计二叉树结点数、叶子数、深度。A三、实验结果分析ABCBCFDEED四、实验操作步骤按先序遍历顺序输入建树，
2、空节点输入#代替，采用递归建树。输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列。并计算输出该树的深度、叶子节点数量、总结点数量之后按层序遍历顺序输入建立完全二叉树，采用非递归建树。输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列。并计算输出该树的深度、叶子节点数量、总结点数量五、源代码#include#include #include #include using namespace std;/二叉树定义typedef char ElementType;typedef struct BiTreeNode ElementType data; struct BiTreeNode* l
3、child; 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); void creatBiTree_2(BiTree &rt,int n) char root2; scanf
4、(%s,root); rt=new BiTreeNode; rt-data=root0; for(int i=2; idata=tmp0; node-rchild=NULL; node-lchild=NULL; for(int j=num-2; j0; j-) if(aj)T=T-rchild; else T=T-lchild; if(a0)T-rchild=node; else T-lchild=node; int Nodenum(BiTreeNode* root)/二叉树节点数目 if(root = NULL) return 0; else return 1+Nodenum(root-lc
5、hild)+Nodenum(root-rchild);/递归销毁一棵二叉树void destroyBiTree(BiTree &T) if(T) destroyBiTree(T-lchild); destroyBiTree(T-rchild); delete T; T = NULL; /递归先序遍历二叉树void preOrderTraverse(const BiTree &T) if(T) coutdatalchild);/遍历左子树 preOrderTraverse(T-rchild);/遍历右子树 /递归中序遍历二叉树void inOrderTraverse(const BiTree &
6、T) if(T) inOrderTraverse(T-lchild);/遍历左子树 coutdatarchild);/遍历右子树 /递归后序遍历二叉树void postOrderTraverse(const BiTree &T) if(T) postOrderTraverse(T-lchild);/遍历左子树 postOrderTraverse(T-rchild);/遍历右子树 coutdatalchild); rdepth = depthOfBiTree(T-rchild); return (ldepthrdepth)?(ldepth+1):(rdepth+1);/递归求二叉树的叶子结点个数
7、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# cout先序遍历: ; /先序遍历 preOrderTraverse(T); coutendl; co
8、ut中序遍历: ;/中序遍历 inOrderTraverse(T); coutendl; cout后序遍历: ;/后序遍历 postOrderTraverse(T); coutendl; cout深度: depthOfBiTree(T)endl;/树的高度 cout叶子结点数: leafCountOfBiTree(T)endl;/叶子结点数 cout总结点数量: Nodenum(T)endl; destroyBiTree(T);/销毁二叉树，释放空间 int n; scanf(%d,&n); BiTree TT=NULL; creatBiTree_2(TT,n); cout先序遍历: ; /先
9、序遍历 preOrderTraverse(TT); coutendl; cout中序遍历: ;/中序遍历 inOrderTraverse(TT); coutendl; cout后序遍历: ;/后序遍历 postOrderTraverse(TT); coutendl; cout深度: depthOfBiTree(TT)endl;/树的高度 cout叶子结点数: leafCountOfBiTree(TT)endl;/叶子结点数 cout总结点数量: Nodenum(TT)endl; destroyBiTree(TT);/销毁二叉树，释放空间 system(PAUSE); return EXIT_SUCCESS;
