二叉树后序遍历的非递归算法
- 格式：doc
- 大小：320.50 KB
- 文档页数：11
}
else //如果该结点的左右孩子都被访问过了
{
cout<<stack[top--]->data<<" ";
}
}
} while((p != NULL)||(top >= 0));
}
void main()
{
bitree *bintree=creattree();
cout<<"\n后根非递归遍历序列如下：\n\n";
在这次试验当中有两个比较重要的地方一个是怎样讲一个二叉树输入到计算机中，另外，怎样用非递归的方法将这个二叉树遍历，所以经过思考后发小了解决的一些方法，像输入二叉树的时候就要应用到递归思想而二叉树的遍历的时候就要用到栈的应用
3.源程序代码：
#include<iostream>
using namespace std;
*stack[MaxNode];//p表示当前结点，栈stack[]用来存储结点
int tag[MAX];
int top=-1;
do
{
while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
tag[top] = 0;
p = p->lchild;
武 汉 工 程 大 学
计算机科学与工程学院
《数据结构》实验报告
专业班级
实验地点
学生学号
指导教师
学生姓名
实验时间
实验项目
数的应用
实验类别
操作性（）验证性（ ）设计性（ ）综合性（Y ）其它（ ）
实验目的及要求
（1）针对问题的实际要求，正确应用树形结构组织和存储数据；
（2）掌握二叉树的存储方法。
（3）掌握二叉树的各种遍历方法。
postorder(bintree);
n=0;
cout<<"\n"<<endl;
}
4.测试用例：
1.当测试用例为如下所示的二叉树时，程序运行的结果如下：
图表1
2.当测试用例为如下所示的二叉树时，程序运行的结果如下：
图表2
实 验 内 容
实 验 总 结
本次试验发现了很多问题，开始的时候对着课本上的算法只有发呆，虽然课本上以及老师对于后序遍历非递归的算法讲得比较详细，但是我还是不知从何入手，在本次试验当中，关键是如何将二叉树输入计算机，以及二叉树的输出，后来通过大量的实践以及资料的查阅，慢慢的掌握了这次试验的编写.
}
if(top >= 0) //所有左孩子处理完毕后
{
if(!tag[top]) //如果当前结点的右孩子还没被访问
{
p = stack[top];//输出栈顶结点 ，但不退栈 ，因为要先输出其孩子结点
p = p->rchild; //处理其右孩子结点
tag[top] = 1; //表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出
else
{
t=(struct node *)malloc(sizeof(bitree));
t->data=x;
t->lchild=creattree();
t->rchild=creattree();
}
return(t);
}
void postorder(bitree *t)//后序遍历的非递归算法
{
bitree *p=t,
2.实验分析：
二叉树后序遍历的非递归算法伪代码如下：
1. 栈s初始化；
2. 循环直到root为空且栈s为空
2.1 当root非空时循环
2.1.1将root连同标志flag=1入栈；
2.1.2 继续遍历root的左子树；
2.2 当栈s非空且栈顶元素的标志为2时，出栈并输出栈顶结点;
2.3 若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结点的右子树；
#define MAX 100
#define Mtatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *root;
int n;
char c;
bitree *creattree()
{
bitree *t;
datatype x;
cout<<"\n请按照二叉树的规律依次输入各结点，以0作为每个节点的结束标志:";
cin>>x;
while((c=getchar())!='\n'&&c!=EOF); //清除缓冲区的方法
if(x=='0')t=NULL;
成 绩 评 定 表
类 别
评 分 标 准
分值
得分
合 计
上机表现
积极出勤、遵守纪律
认真完成实验任务
30分
报告质量
程序代码规范、功能正确
填写内容完整、体现收获
70分
说明：
评阅教师：日 期：年月日
1.实验内容:
二叉树后序遍历的非递归算法。
实验说明：
二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。
设根指针为root，则可能有以下两种情况：
2若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树；
⑵ 若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。
else //如果该结点的左右孩子都被访问过了
{
cout<<stack[top--]->data<<" ";
}
}
} while((p != NULL)||(top >= 0));
}
void main()
{
bitree *bintree=creattree();
cout<<"\n后根非递归遍历序列如下：\n\n";
在这次试验当中有两个比较重要的地方一个是怎样讲一个二叉树输入到计算机中，另外，怎样用非递归的方法将这个二叉树遍历，所以经过思考后发小了解决的一些方法，像输入二叉树的时候就要应用到递归思想而二叉树的遍历的时候就要用到栈的应用
3.源程序代码：
#include<iostream>
using namespace std;
*stack[MaxNode];//p表示当前结点，栈stack[]用来存储结点
int tag[MAX];
int top=-1;
do
{
while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
tag[top] = 0;
p = p->lchild;
武 汉 工 程 大 学
计算机科学与工程学院
《数据结构》实验报告
专业班级
实验地点
学生学号
指导教师
学生姓名
实验时间
实验项目
数的应用
实验类别
操作性（）验证性（ ）设计性（ ）综合性（Y ）其它（ ）
实验目的及要求
（1）针对问题的实际要求，正确应用树形结构组织和存储数据；
（2）掌握二叉树的存储方法。
（3）掌握二叉树的各种遍历方法。
postorder(bintree);
n=0;
cout<<"\n"<<endl;
}
4.测试用例：
1.当测试用例为如下所示的二叉树时，程序运行的结果如下：
图表1
2.当测试用例为如下所示的二叉树时，程序运行的结果如下：
图表2
实 验 内 容
实 验 总 结
本次试验发现了很多问题，开始的时候对着课本上的算法只有发呆，虽然课本上以及老师对于后序遍历非递归的算法讲得比较详细，但是我还是不知从何入手，在本次试验当中，关键是如何将二叉树输入计算机，以及二叉树的输出，后来通过大量的实践以及资料的查阅，慢慢的掌握了这次试验的编写.
}
if(top >= 0) //所有左孩子处理完毕后
{
if(!tag[top]) //如果当前结点的右孩子还没被访问
{
p = stack[top];//输出栈顶结点 ，但不退栈 ，因为要先输出其孩子结点
p = p->rchild; //处理其右孩子结点
tag[top] = 1; //表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出
else
{
t=(struct node *)malloc(sizeof(bitree));
t->data=x;
t->lchild=creattree();
t->rchild=creattree();
}
return(t);
}
void postorder(bitree *t)//后序遍历的非递归算法
{
bitree *p=t,
2.实验分析：
二叉树后序遍历的非递归算法伪代码如下：
1. 栈s初始化；
2. 循环直到root为空且栈s为空
2.1 当root非空时循环
2.1.1将root连同标志flag=1入栈；
2.1.2 继续遍历root的左子树；
2.2 当栈s非空且栈顶元素的标志为2时，出栈并输出栈顶结点;
2.3 若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结点的右子树；
#define MAX 100
#define Mtatype;
typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *root;
int n;
char c;
bitree *creattree()
{
bitree *t;
datatype x;
cout<<"\n请按照二叉树的规律依次输入各结点，以0作为每个节点的结束标志:";
cin>>x;
while((c=getchar())!='\n'&&c!=EOF); //清除缓冲区的方法
if(x=='0')t=NULL;
成 绩 评 定 表
类 别
评 分 标 准
分值
得分
合 计
上机表现
积极出勤、遵守纪律
认真完成实验任务
30分
报告质量
程序代码规范、功能正确
填写内容完整、体现收获
70分
说明：
评阅教师：日 期：年月日
1.实验内容:
二叉树后序遍历的非递归算法。
实验说明：
二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag，当结点进、出栈时，其标志flag也同时进、出栈。
设根指针为root，则可能有以下两种情况：
2若root!=NULL，则root及标志flag（置为1）入栈，遍历其左子树；
⑵ 若root=NULL，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。
