数据结构》实验报告
◎实验题目: 创建并遍历二叉树◎实验目的：熟悉二叉树存储结构，熟悉二叉树的三种遍历方法，并能用非递归的方法建立并且遍历二叉树。
◎实验内容：用先序和中序建立二叉树，用后序遍历并输出二叉树，要求算法非递归。
一、需求分析
该程序用非递归的方法，利用先序和中序建立二叉树，然后用后序遍历的方法输出二叉树的
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、运行界面。
』r［訐rtt當：诃I]
五、实验总结
你在编程过程中花时多少？
五个小时
多少时间在纸上设计？
半个小时
多少时间上机输入和调试？
四个小时，主要是用来调试，程序编写完成后有很多错误，需要一个个的找，有些错误看起来没什么问题，所以用了很长时间。
你的收获有哪些？
用非递归法建立二叉树，让我们对于二叉树的建立过程掌握得更加清楚明了。
用先序中序建立，用后序遍历，让我们对于二叉树的三种遍历方法都能掌握。
教师评语：实验成绩:
指导教师签名：
批阅日期:。