C++二叉树基本操作实验报告
- 格式：doc
- 大小：59.50 KB
- 文档页数：10
下载文档原格式
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
一、实验目的
选择二叉链式存储结构作为二叉树的存储结构，设计一个程序实现二叉树的基本操作（包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等）
二、实验开发环境
Windows 8.1 中文版
Microsoft Visual Studio 6.0
三、实验内容
程序的菜单功能项如下：
1------建立一棵二叉树
2------前序遍历递归算法
3------前序遍历非递归算法
4------中序遍历递归算法
5------中序遍历非递归算法
6------后序遍历递归算法
7------后序遍历非递归算法
8------求树高
9------求叶子总数
10-----输出二叉树
11-----退出
四、实验分析
1、建立一棵二叉树
2、输入二叉树各节点数据
cout<<"请按正确顺序输入二叉树的数据:";
cin.getline(t,1000); //先把输入的数据输入到一个t数组3、递归前序遍历
void BL1(ECS_data *t)
{
if(NULL!=t)
{
cout<
BL1(t->l);
BL1(t->r);
}
}
4、非递归前序遍历
void preOrder2(ECS_data *t)
{
stack
ECS_data *p=t;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<
s.push(p);
p=p->l;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->r;
}
}
}
5、递归中序遍历
void BL2(ECS_data *t)
{
if(NULL!=t)
{
BL2(t->l);
cout<
BL2(t->r);
}
}
6、非递归中序遍历
void inOrder2(ECS_data *t) //非递归中序遍历
{
stack
ECS_data *p=t;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->l;
}
if(!s.empty())
{
p=s.top();
cout<
s.pop();
p=p->r;
}
}
}
7、递归后序遍历
void BL3(ECS_data *t)
{
if(NULL!=t)
{
BL3(t->l);
BL3(t->r);
cout<
}
}
8、非递归后序遍历
void postOrder3(ECS_data *t)
{
stack
ECS_data *cur; //当前结点
ECS_data *pre=NULL; //前一次访问的结点
s.push(t);
while(!s.empty())
{
cur=s.top();
if((cur->l==NULL&&cur->r==NULL)||
(pre!=NULL&&(pre==cur->l||pre==cur->r)))
{
cout<
s.pop();
pre=cur;
}
else
{
if(cur->r!=NULL)
s.push(cur->r);
if(cur->l!=NULL)
s.push(cur->l);
}
}
}
9、求树高
int Height (ECS_data *t)
{
if(t==NULL) return 0;
else
{
int m = Height ( t->l );
int n = Height(t->r);
return (m > n) ? (m+1) : (n+1);
}
}
10、求叶子总数
int CountLeaf(ECS_data *t)
{
static int LeafNum=0;//叶子初始数目为0，使用静态变量
if(t)//树非空
{
if(t->l==NULL&&t->r==NULL)//为叶子结点
LeafNum++;//叶子数目加1
else//不为叶子结点
{