完整版C++二叉树基本操作实验报告.docx
- 文档编号:18158722
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:13
- 大小:49.46KB
完整版C++二叉树基本操作实验报告.docx
《完整版C++二叉树基本操作实验报告.docx》由会员分享,可在线阅读,更多相关《完整版C++二叉树基本操作实验报告.docx(13页珍藏版)》请在冰点文库上搜索。
完整版C++二叉树基本操作实验报告
、实验目的
选择二叉链式存储结构作为二叉树的存储结构,设计一个程序实现二叉树的基本操作(包括建立、输出、前序遍历、中序遍历、后序遍历、求树高、统计叶子总数等)
二、实验开发环境
MicrosoftVisualStudio6.0
三、实验内容程序的菜单功能项如下:
1建立一棵二叉树
2前序遍历递归算法
3前序遍历非递归算法
4中序遍历递归算法
5中序遍历非递归算法
6后序遍历递归算法
7后序遍历非递归算法
8求树高
9求叶子总数
10输出二叉树
11退出四、实验分析
1、建立一棵二叉树
2、输入二叉树各节点数据
coutvv"请按正确顺序输入二叉树的数据:
";
cin.getline(t,1000);//先把输入的数据输入到一个t数组
3、递归前序遍历
voidBL1(ECS_data*t){
if(NULL!
=t)
{
cout<
BL1(t->l);
BL1(t->r);
}
}
4、非递归前序遍历
voidpreOrder2(ECS_data*t)
{stack
=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、递归中序遍历
voidBL2(ECS_data*t){
if(NULL!
=t)
{
BL2(t->l);
cout<
BL2(t->r);
}
}
6、非递归中序遍历
voidinOrder2(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<
p=p->r;
}
7、递归后序遍历
voidBL3(ECS_data*t){
if(NULL!
=t)
{
BL3(t->l);
BL3(t->r);cout<
voidpostOrder3(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、求树高
intHeight(ECS_data*t){
if(t==NULL)return0;else
{
intm=Height(t->l);
intn=Height(t->r);
return(m>n)?
(m+1):
(n+1);}
intCountLeaf(ECS_data*t)
{
staticintLeafNum=O;//叶子初始数目为0,使用静态变量if(t)//树非空
{
if(t->l==NULL&&t->r==NULL)//为叶子结点
LeafNum++;//叶子数目加1else//不为叶子结点
{
CountLeaf(t->l);//递归统计左子树叶子数目
CountLeaf(t->r);//递归统计右子树叶子数目
}
}
returnLeafNum;
}
五、运行结果
附:
完整程序源代码:
〃二叉树链式存储的实现
#includeviostream>
#include
#inelude
structECS_data//先定义好一个数据的结构{
chardata;
ECS_data*l;
ECS_data*r;
classECS
{
Private:
//intlevel;intn;
intn1;
进行删除判断
};"
//树高
//表示有多少个节点数
〃表示的是数组的总长度值,(包括#),因为后面要
ECS_data*temp[1000];
public:
ECS_data*root;
ECS()//初始化
{
ECS_data*p;chart[1000];inti;intfront=0,rear=1;
入的点的父母
//front表示有多少个节点,rear表示当前插
coutvv"请按正确顺序输入二叉树的数据:
";cin.getline(t,1000);//cout< ='#'){ //先把输入的数据输入到一个t数组 //测量数据的长度 p=NULL; if(t[i]! =',') { n++; p=newECS_data;p->data=t[i];p->l=NULL;p->r=NULL; }front++;temp[front]=p; if(1==front){root=p;}else { //满足条件并开辟内存 if((p! =NULL)&&(0==front%2)){ temp[rear]->l=p;//刚开始把这里写成了==}if((p! =NULL)&&(1==front%2)){ temp[rear]->r=p;}if(1==front%2)rear++; //就当前的数据找这个数据 的父母 //释放内存 } ~ECS() { inti; for(i=1;i<=n;i++)if(temp[i]! =NULL)deletetemp[i]; //记录节点的个数 }voidJS() { ints;s=n; coutvv"该二叉树的节点数为: "vvsvvendl;} voidBL1(ECS_data*t)//递归前序遍历{ if(NULL! =t) { cout< BL1(t->l); BL1(t->r); } voidpreOrder2(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; if(NUL匚丛) 宀 BL2(e_)-coufAvdafaAfr BL2(g- voidino「de「2(Ecslda応J)二卅融丘甘甸壷逗宀sfackAECSIdafa*vs八ECSIdafa*PHCwhi-e(p一hnul匚-一s.empfyo) 宀 wh=e(p一"NULL) 宀 s.push(p)八 PHP—vr if(一s.empfyo) 宀 PHSlopucoufAAP—vdafaAA s.popw PHP* voidBL3(Ecsldafa*U1融&训引筍已 宀 if(NUL匚丛) 宀 BL3(e_)- BL3(g- coufAAf—vdafaAdr voidposfo「de「3(Ecsldafa*0&可甸壷逗宀 sfackAECSIdafa*vs八ECSIdafa*cucm遡璋、的 ECSIdafa*p「eHNUF二遡—舟曲亘兼叫、的 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); } } } intHeight(ECS_data*t)//求树高 { if(t==NULL)return0;else { intm=Height(t->l); intn=Height(t->r); return(m>n)? (m+1): (n+1); } } intCountLeaf(ECS_data*t)//求叶子总数 { staticintLeafNum=0;//叶子初始数目为0,使用静态变量if(t)//树非空 { if(t->l==NULL&&t->r==NULL)//为叶子结点LeafNum++;//叶子数目加1 else//不为叶子结点 { CountLeaf(t->l);//递归统计左子树叶子数目 CountLeaf(t->r);//递归统计右子树叶子数目} returnLeafNum;} }; intmain() { ECSa; a.JS(); coutvv"递归前序遍历: "; a.BL1(a.root); cout< coutvv"非递归前序遍历: "; a.preOrder2(a.root); coutvvendl; coutvv"递归中序遍历: "; a.BL2(a.root); coutvvendl; coutvv"非递归中序遍历: "; a.inOrder2(a.root); coutvvendl; coutvv"递归后序遍历: "; a.BL3(a.root); coutvvendl; coutvv"非递归后序遍历: "; a.postOrder3(a.root); coutvvendl; coutvv"树高为: "vva.Height(a.root)vvendl; coutvv"叶子总数为: "vva.CountLeaf(a.root)vvendl;return0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整版 C+ 二叉 基本 操作 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)