数据结构二叉树实践报告(1)

成绩:实验报告课程名称：数据结构实验实验项目：二叉树的建立及遍历 姓 名：专 业：班 级：学 号：计算机科学与技术学院实验教学中心2017 年 11 月17日实验项目名称：二叉树的建立及遍历一、实验目的：(1) 熟练掌握二叉树的建立方法;(2) 熟练掌握二叉树的遍历算法;(3) 掌握二叉树的应用算法。、实验内容：(1) 编写算法建立一棵二叉树的二叉链表;(2) 输出二叉树的三种遍历序列，包括递归算法、非递归算法;(3) 编写算法统计二叉树结点数、叶子数、深度。三、实验结果分析C:User5KuroNe koD es kto p篌樹便数据结构匚叉树遍历.exeAB疏曲瞎 先序遍历：A B D C E 中京遍厉：D B A C E 后序遍厉:D B E C A 深度：3叶子结点数:2 总结点数量：56A B C D E F先序遍历：A B D E C F 中京遍厉：D B E A F C 后序遍彷：D E B F C A 深度：3口-心古点数：3 总结点数量：6 请按任慝键继续”四、实验操作步骤 按先序遍历顺序输入建树，空节点输入#代替，采用递归建树。 输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列。 并计算输出该树的深度、叶子节点数量、总结点数量之后按层序遍历顺序输入建立完全二叉树，采用非递归建树。 输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列。 并计算输出该树的深度、叶子节点数量、总结点数量五、源代码#include#include #include #include using namespace std;/二叉树定义typedef char ElementType;typedef struct BiTreeNodeElementType data;struct BiTreeNode* lchild;struct BiTreeNode* rchild; BiTreeNode, *BiTree;/递归的建立一棵二叉树 /输入为二叉树的先序序列 void createBiTree(BiTree &T) char data;data = getchar();if(data = #)T = NULL;elseT = new BiTreeNode; T-data = data; createBiTree(T-lchild); createBiTree(T-rchild);void creatBiTree_2(BiTree &rt,int n)char root2; scanf(%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 Node num(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)coutdatalchild);遍历左子树 preOrderTraverse (T-rchild);/遍 历右子树/递归中序遍历二叉树void inOrderTraverse(const BiTree &T)if(T)in OrderTraverse(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);/递归求二叉树的叶子结点个数int leafCou ntO f BiTree(co nst 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# coutvv先序遍历:;/先序遍历 preOrderTraverse(T);coutendl;coutvv中序遍历:;/中序遍历inOrderTraverse(T);coutvvendl;coutvv后序遍历:;/后序遍历postOrderTraverse(T);coutvvendl;coutvv深度：vvdepthO f BiTree(T)vve ndl;/树的高度coutvv叶子结点数:vvleafCou ntOfBiTree(T)vve ndl; 叶子结点数 coutvv总结点数量:vvNode num(T)vve ndl;destroyBiTree(T);/销毁二叉树，释放空间int n;scanf(%d,&n);BiTree TT=NULL;creatBiTree_2(TT,n);coutvv先序遍历:;/先序遍历 preOrderTraverse(TT);coutvvendl;coutvv中序遍历:;/中序遍历inOrderTraverse(TT);coutvvendl;coutvv后序遍历:;/后序遍历postOrderTraverse(TT);coutvvendl;coutvv深度：vvdepthO f BiTree(TT)vve ndl;/树的高度coutvv叶子结点数:vvleafCou ntOfBiTree(TT)vve ndl; 叶子结点数 coutvv总结点数量:vvNode num(TT)vve ndl;destroyBiTree(TT);/销毁二叉树，释放空间 system(PAUSE);return EXIT_SUCCESS;