二叉树叶子结点数和高度.doc

《二叉树叶子结点数和高度.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、江西理工大学软件学院计算机类课程实验报告课程名称：数据结构班级：姓名：学号：江西理工大学软件学院实验五实验名称求二叉树叶子结点数和高度实验日期2012-12-11实验成绩实验目的、要求及内容一、实验目的、要求：a)加深理解二叉树的定义和特性；b)掌握二叉树的存储结构与实现；c)掌握二叉树的遍历操作及其应用二、实验内容：1．写出程序的运行结果，并上机验证2．上机调试程序，根据键盘输入的扩展二叉树的前序遍历序列建立相应的二叉树，并计算该二叉树的叶子结点个数和高度。3．上机调试，程序分析4．编写程序5．填写实验报告实验环境3423机房操作系统：windowsXPC环境：VC++6.0算法描

2、述及实验步骤一、算法描述存储结构：二叉链表基本思想：利用二叉树的遍历操作，设计递归算法实现。递归模式：一整棵二叉树树的叶子结点数＝左子树的叶子结点数＋右子树的叶子结点数递归出口二、实验步骤1．写出程序的运行结果，并上机验证。程序及运行结果如下：（1）输入创建一棵二叉树的结点数据：ab#c##D##输出：前序遍历abcD该二叉树的叶子结点为：2该二叉树的高度为：3交换后的二叉树为：abDc(2)输入创建一棵二叉树的结点数据：ABC#D###E##输出：前序遍历ABCDE该二叉树的叶子结点为：2该二叉树的高度为：4交换后的二叉树为：AEBCD2．上机调试程序，按规定格式输入数据（1）输入

3、创建一棵二叉树的结点数据：ab#c##D##运行结果,正确。(2)输入创建一棵二叉树的结点数据：ABC#D###E##运行结果，正确。(3)若输入格式错误，则无法得到结果。3．上机调试，程序分析4．编写程序调试过程及实验结果实验执行的结果：（1）输入创建一棵二叉树的结点数据：ab#c##D##(2)输入创建一棵二叉树的结点数据：ABC#D###E##总结课程实验不仅要求对课本知识有较深刻的了解，同时要求我们有较强的思维和动手能力，需要进一步了解编程思想和编程技巧。通过课程实验，使我对课本知识掌握的更加深刻，增强了自己的思维和动手能力。通过这次试验加深理解二叉树的定义和特性；掌握二叉树

4、的存储结构与实现；掌握二叉树的遍历操作及其应用附录（源程序清单等）#includeintcount=0;structBiNode{chardata;BiNode*lchild,*rchild;};classBiTree{public:BiTree();~BiTree();voidCountLeaf(BiNode*root);intBiTreeDepth(BiNode*root);BiNode*getroot(){returnroot;}voidSwap(BiNode*root);//intIsSame(BiNode*root1,BiNode*root2);pr

5、ivate:BiNode*root;BiNode*Creat();voidRelease(BiNode*root);};BiTree::BiTree(){root=Creat();}BiNode*BiTree::Creat(){BiNode*root;charch;cin>>ch;if(ch=='#')returnNULL;else{root=newBiNode;root->data=ch;root->lchild=Creat();root->rchild=Creat();}returnroot;}BiTree::~BiTree(){Release(root);}voidBiTree

6、::Release(BiNode*root){if(root!=NULL){Release(root->lchild);Release(root->rchild);deleteroot;}}voidBiTree::CountLeaf(BiNode*root){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL)count++;cout<data<<"";CountLeaf(root->lchild);CountLeaf(root->rchild);}}intBiTree::BiTreeDepth(BiNode

7、*root){if(root==NULL)return0;else{intdep1=BiTreeDepth(root->lchild);intdep2=BiTreeDepth(root->rchild);if(dep1>dep2)returndep1+1;elsereturndep2+1;}}voidBiTree::Swap(BiNode*root){if(root!=NULL){BiNode*p;p=root->lchild;root->lchild=r