二叉树后序遍历 数据结构实验
- 格式：doc
- 大小：152.00 KB
- 文档页数：5
《算法与数据结构》试验报告[六]专业班级试验地点
学生学号指导教师
学生姓名试验时间
试验项目算法与数据结构
试验类别基础性（）设计性（）综合性（√）其它（）
试验目的及要求（1）掌握用VC++上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。
成绩评定表
类别评分标准分值得分合计
上机表现积极出勤、遵守纪律
主动完成设计任务
30分
程序与报告程序代码规范、功能正确
报告详实完整、体现收获
70分
备注：
评阅教师：
日期：年月日
试验内容
一、实验目的和要求
1、实验目的：
（1）针对问题的实际要求，正确应用树形结构组织和存储数据；
（2）掌握二叉树的存储方法。
（3）掌握二叉树的各种遍历方法。
2、实验内容: 二叉树后序遍历的非递归算法。
3、实验说明：
二叉树后序遍历的非递归算法：结点要入两次栈，出两次栈；为了区别同一个结点的两次出栈，设置标志flag ，当结点进、出栈时，其标志flag 也同时进、出栈。
设根指针为root ，则可能有以下两种情况：
⑴ 若root!=NULL ，则root 及标志flag （置为1）入栈，遍历其左子树； ⑵ 若root=NULL ，此时若栈空，则整个遍历结束；若栈不空，则表明栈顶结点的左子树或右子树已遍历完毕。
若栈顶结点的标志flag=1，则表明栈顶结点的左子树已遍历完毕，将flag 修改为2，并遍历栈顶结点的右子树；若栈顶结点的标志flag=2，则表明栈顶结点的右子树也遍历完毕，输出栈顶结点。
二叉树后序遍历的非递归算法伪代码如下：
二、设计分析
在输入二叉树时，按照先序的顺序来进行构建，若输入’#’表示该点为空不
存在，每个孩子节点都必须有数据不管它是否为空，后续遍历函数则利用了非递归算法按照了实验指导，加入了上述算法。
三、源程序代码
#include <stdio.h> #include <iostream> #include <stdlib.h> struct tree {
char data;
struct tree *lchild; struct tree *rchild; };
typedef struct tree * treptr;
treptr build(treptr t) //先序建树 {
char c;
c=getchar(); if(c=='#')
1 第一次出栈，只遍历完左子树，该结点不能访问
2 第二次出栈，遍历完右子树，该结点可以访问 flag ＝
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，准备遍历栈顶结点的右子树；
{
t=NULL;
}
else
{
t=(treptr)malloc(sizeof(struct tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return t;
}
void postdorder(treptr root)
{
if (root!=NULL)
{
postdorder(root->lchild);
postdorder(root->rchild);
printf("%c",root->data);
}
}
struct stack
{
treptr *top,*base;
};
typedef struct stack *stackptr;
void init (stackptr s)//初始化栈
{
s->base=(treptr*)malloc(sizeof(treptr)*100); s->top=s->base;
}
void push(stackptr s,treptr t)//入栈
{
*(s->top++)=t;
}
treptr pop(stackptr s)//弹出栈顶元素
{
treptr t;
t=*(--(s->top));
return t;
}
treptr gettop(stackptr s)//取栈顶元素
{
treptr *l=s->top-1;
return *(l);
}
void postorder(treptr t)//这是非递归后序实现{
stackptr s=(stackptr)malloc(sizeof(struct stack)); treptr temp=t;
treptr p;
treptr lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist) {
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
int main()
{
treptr t=NULL;
printf("请输入需要遍历的二叉树：\n");
t=build(t);
postdorder(t);
printf("非递归后序遍历\n");
postorder(t);
printf("\n");
return 0;
}四、测试用例
1.该数为空，用只有一个节点且为空
此时没有节点，无法遍历。
2。
普通的树
3.树中只有一个根节点设为1，两个孩子节点分别设为2和3
先序为123，后序遍历
五、实验总结
这一次实验是二叉树的后序遍历，创建树的时候为先序创建。
运用了刚刚学习过的二叉树的相关知识。
什么知识都是在实践中加深理解，更好地掌握。
这次实验很困难，树的遍历算法很难写，老师让我们要多加讨论，通过和同学的讨论，一些问题迎刃而解，各个问题逐步击破，此外还参考了相关书籍和上网查资料。
每一次的实验都能然我收获很多，我觉得树是一个很总要的数据结构，一定要好好掌握。
