《数据结构》实验报告
◎实验题目: 创建并遍历二叉树
◎实验目的：熟悉二叉树存储结构，熟悉二叉树的三种遍历方法，并能用非递归的方法建立并且遍历二叉树。
◎实验内容：用先序和中序建立二叉树，用后序遍历并输出二叉树，要求算法非递归。
一、需求分析
该程序用非递归的方法，利用先序和中序建立二叉树，然后用后序遍历的方法输出二叉树的元素。
1、输入的形式和输入值的范围；
程序运行时输入二叉树的先序和中序序列，为字符型元素。
2、输出的形式；
运行结果为输出二叉树的后序序列，亦为字符型元素。
3、程序所能达到的功能；
本程序可以建立一个二叉树存储结构，并且访问其结点元素。
4、测试数据：
输入：先序：abcde
中序：edcba
输出：后序：edcba
二概要设计
1. 本程序中首先需定义二叉树的节点类型，节点为一个含有数据与和指针域的结构体。
2. 其次，本程序中需要用两个栈，一个用来存放指针，一个用来存放数组元素的下标。
3. 主程序中，分别输入两个字符串，作为二叉树的先序和中序序列；两个子函数分别实现创建二叉树和后序遍历输出二叉树的功能。
而在子函数中还调用了例如出栈入栈等子函数。
三详细设计
1. 定义二叉树节点类型
struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTree;
2.定义两个栈的类型
struct snode
{
int top;
int a[MAX];
};
struct snode1
{
int top;
struct node *c[MAX];
};
3．主函数
void main()
{
char a[MAX]={0};
char b[MAX]={0};
char c=0,d=0;
int i=0,j=0;
struct node *g;
snode s;
snode1 s4,s1;
Initstack(&s);
Initstack1(&s4);
Initstack1(&s1);
printf("请输入先序序列:\n");
while(c!='\n')
{
c=getchar();
a[i]=c;
i++;
}
printf("请输入中序序列:\n");
while(d!='\n')
{
d=getchar();
b[j]=d;
j++;
}
g=create(&s,&s1,a,b);
printf("遍历输出后序序列:\n");
visit(&s4,g);
printf("\n");
}
4. 子函数一，创建二叉树
struct node * create(snode *s,snode1 *s1,char a[MAX],char b[MAX]) {
int i=1,num,x;
struct node *p,*q,*r,*root;
p=(struct node *)malloc(sizeof(BTree));
p->lchild=NULL;
p->rchild=NULL;
p->data=a[0];
root=p;
x=seek(a[0],b);
push(s,x);
push1(s1,p);
while(a[i]!='\n')
{
num=seek(a[i],b);
p=(struct node *)malloc(sizeof(BTree)); p->lchild=NULL;
p->rchild=NULL;
p->data=a[i];
if(num<gettop(s))
{
q=get(s1);
q->lchild=p;
push(s,num);
push1(s1,p);
}
else if(num>gettop(s))
{
while(s->top!=-1&&num>gettop(s))
{
r=pop1(s1);
pop(s);
}
r->rchild=p;
push(s,num);
push1(s1,p);
}
i++;
}
return root;
}
5. 子函数二，后序遍历输出二叉树
void visit(snode1 *s,struct node *root)
{
struct node *p;
p=root;
do
{
while(p!=NULL)
{
push1(s,p);
p=p->lchild;
}
while(s->top!=-1&&give(s)->rchild==p)
{
p=pop1(s);
printf("%c",p->data);
}
if(s->top!=-1)
p=give(s)->rchild;
}while(s->top!=-1);
}
四使用说明、测试分析及结果
1、说明如何使用你编写的程序；
程序名为4.exe，运行环境为visual C++。
程序执行后显示：请输入先序序列：
输入元素后显示
请输入中序序列：
然后程序自动运行，输出
遍历输出后序序列:以及结果
2、测试结果与分析；
请输入先序序列: abcde
请输入中序序列: edcba
遍历输出后序序列:edcba
3、运行界面。
五、实验总结
你在编程过程中花时多少？
五个小时
多少时间在纸上设计？
半个小时
多少时间上机输入和调试？
四个小时，主要是用来调试，程序编写完成后有很多错误，需要一个个的找，有些错误看起来没什么问题，所以用了很长时间。
你的收获有哪些？
用非递归法建立二叉树，让我们对于二叉树的建立过程掌握得更加清楚明了。
用先序中序建立，用后序遍历，让我们对于二叉树的三种遍历方法都能掌握。
教师评语：
实验成绩：
指导教师签名：
批阅日期：（注：可编辑下载，若有不当之处，请指正，谢谢!）。