数据结构二叉树实践报告(共7页).doc

精选优质文档-----倾情为你奉上成绩：实 验 报 告课程名称：数据结构实验实验项目：二叉树的建立及遍历姓 名：专 业：班 级：学 号：计算机科学与技术学院实验教学中心2017 年 11 月 17 日专心---专注---专业实验项目名称： 二叉树的建立及遍历 一、实验目的：(1)熟练掌握二叉树的建立方法；(2)熟练掌握二叉树的遍历算法；(3)掌握二叉树的应用算法二、实验内容：(1)编写算法建立一棵二叉树的二叉链表；(2)输出二叉树的三种遍历序列，包括递归算法、非递归算法；(3)编写算法统计二叉树结点数、叶子数、深度A三、实验结果分析ABCBCFDEED四、实验操作步骤按先序遍历顺序输入建树，空节点输入#代替，采用递归建树输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列并计算输出该树的深度、叶子节点数量、总结点数量之后按层序遍历顺序输入建立完全二叉树，采用非递归建树输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列并计算输出该树的深度、叶子节点数量、总结点数量五、源代码#include#include #include #include using namespace std;//二叉树定义typedef char ElementType;typedef struct BiTreeNode{ ElementType 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); }}void creatBiTree_2(BiTree &rt,int n){ char root[2]; scanf("%s",root); rt=new BiTreeNode; rt->data=root[0]; for(int i=2; i<=n; i++) { BiTreeNode* T=rt; char tmp[2]; int num=0,a[16]; scanf("%s",tmp); int ii=i; while(ii) { a[num++]=ii%2; ii/=2; } BiTreeNode *node=new BiTreeNode; node->data=tmp[0]; node->rchild=NULL; node->lchild=NULL; for(int j=num-2; j>0; j--) if(a[j])T=T->rchild; else T=T->lchild; if(a[0])T->rchild=node; else T->lchild=node; }}int Nodenum(BiTreeNode* root)//二叉树节点数目{ if(root == NULL) return 0; else return 1+Nodenum(root->lchild)+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) { cout<data<<" ";//输出根节点值 preOrderTraverse(T->lchild);//遍历左子树 preOrderTraverse(T->rchild);//遍历右子树 }}//递归中序遍历二叉树void inOrderTraverse(const BiTree &T){ if(T) { inOrderTraverse(T->lchild);//遍历左子树 cout<data<<" ";//输出根节点值 inOrderTraverse(T->rchild);//遍历右子树 }}//递归后序遍历二叉树void postOrderTraverse(const BiTree &T){ if(T) { postOrderTraverse(T->lchild);//遍历左子树 postOrderTraverse(T->rchild);//遍历右子树 cout<data<<" ";//输出根节点值 }}//递归求树的深度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):(rdepth+1);}//递归求二叉树的叶子结点个数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); cout<