二叉树叶子结点数和高度docWord文档下载推荐.docx
《二叉树叶子结点数和高度docWord文档下载推荐.docx》由会员分享，可在线阅读，更多相关《二叉树叶子结点数和高度docWord文档下载推荐.docx（8页珍藏版）》请在冰点文库上搜索。
实验目的、要求及内容
一、实验目的、要求：
a）加深理解二叉树的定义和特性；
b）掌握二叉树的存储结构与实现；
c）掌握二叉树的遍历操作及其应用
二、实验内容：
1．写出程序的运行结果，并上机验证
2．上机调试程序，根据键盘输入的扩展二叉树的前序遍历序列建立相应的二叉树，并计算该二叉树的叶子结点个数和高度。
3．上机调试，程序分析
4．编写程序
5．填写实验报告
实验环境
3423机房
操作系统：
windowsXP
C环境：
VC++6.0
算法描述及实验步骤
一、算法描述
存储结构：
二叉链表
基本思想：
利用二叉树的遍历操作，设计递归算法实现。
递归模式：
一整棵二叉树树的叶子结点数＝左子树的叶子结点数＋右子树的叶子结点数
递归出口
二、实验步骤
1．写出程序的运行结果，并上机验证。
程序及运行结果如下：
（1）输入创建一棵二叉树的结点数据：
ab#c##D##
输出：
前序遍历abcD
该二叉树的叶子结点为：
2
该二叉树的高度为：
3
交换后的二叉树为：
abDc
（2）输入创建一棵二叉树的结点数据：
ABC#D###E##
前序遍历ABCDE
4
AEBCD
2．上机调试程序，按规定格式输入数据
运行结果,正确。
运行结果，正确。
（3）若输入格式错误，则无法得到结果。
调试过程及实验结果
实验执行的结果：
总结
课程实验不仅要求对课本知识有较深刻的了解，
同时要求我们有较强的思维和动手能力，需要
进一步了解编程思想和编程技巧。
通过课程实验，
使我对课本知识掌握的更加深刻，增强了自己的
思维和动手能力。
通过这次试验加深理解二叉树的定义
和特性；
掌握二叉树的存储结构与实现；
掌握二叉树的遍历操作及其应用
附录
（源程序清单等）
#include<
iostream.h>
intcount=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）;
private:
BiNode*root;
BiNode*Creat（）;
voidRelease（BiNode*root）;
};
BiTree:
:
BiTree（）
root=Creat（）;
BiNode*BiTree:
Creat（）
{
charch;
cin>
>
ch;
if（ch=='
#'
）returnNULL;
else
{
root=newBiNode;
root->
data=ch;
root->
lchild=Creat（）;
root->
rchild=Creat（）;
}
returnroot;
~BiTree（）
Release（root）;
voidBiTree:
Release（BiNode*root）
if（root!
=NULL）
Release（root->
lchild）;
rchild）;
deleteroot;
CountLeaf（BiNode*root）
{
if（root->
lchild==NULL&
&
rchild==NULL）
count++;
cout<
<
data<
"
"
;
CountLeaf（root->
lchild）;
rchild）;
}
intBiTree:
BiTreeDepth（BiNode*root）
if（root==NULL）
return0;
intdep1=BiTreeDepth（root->
intdep2=BiTreeDepth（root->
if（dep1>
dep2）
returndep1+1;
else
returndep2+1;
}
Swap（BiNode*root）
=NULL）
{BiNode*p;
p=root->
lchild;
lchild=root->
rchild;
rchild=p;
cout<
Swap（root->
Swap（root->
voidmain（）
cout<
请依次输入创建一棵二叉树的结点数据:
<
endl;
BiTreeB;
---前序遍历---"
endl;
B.CountLeaf（B.getroot（））;
该二叉树的叶子结点数为:
count<
该二叉树的高度为:
B.BiTreeDepth（B.getroot（））<
交换后的二叉树为:
B.Swap（B.getroot（））;
升级会员 