《数据结构试验报告用先序中序建立二叉树后序遍历非递归.doc》由会员分享，可在线阅读，更多相关《数据结构试验报告用先序中序建立二叉树后序遍历非递归.doc（5页珍藏版）》请在三一文库上搜索。
1、数据结构实验报告实验题目: 创建并遍历二叉树实验目的：熟悉二叉树存储结构，熟悉二叉树的三种遍历方法，并能用非递归的方法建立并且遍历二叉树。实验内容：用先序和中序建立二叉树，用后序遍历并输出二叉树，要求算法非递归。一、需求分析该程序用非递归的方法，利用先序和中序建立二叉树，然后用后序遍历的方法输出二叉树的元素。1、输入的形式和输入值的范围；程序运行时输入二叉树的先序和中序序列，为字符型元素。2、输出的形式；运行结果为输出二叉树的后序序列，亦为字符型元素。3、程序所能达到的功能；本程序可以建立一个二叉树存储结构，并且访问其结点元素。4、测试数据：输入：先序：abcde中序：edcba输出：后序：e
2、dcba二 概要设计1. 本程序中首先需定义二叉树的节点类型，节点为一个含有数据与和指针域的结构体。2. 其次，本程序中需要用两个栈，一个用来存放指针，一个用来存放数组元素的下标。3. 主程序中，分别输入两个字符串，作为二叉树的先序和中序序列；两个子函数分别实现创建二叉树和后序遍历输出二叉树的功能。而在子函数中还调用了例如出栈入栈等子函数。三 详细设计1.定义二叉树节点类型struct nodechar data;struct node *lchild;struct node *rchild;BTree;2.定义两个栈的类型struct snodeint top;int aMAX; struc
3、t snode1int top;struct node *cMAX;3主函数void main()char aMAX=0;char bMAX=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(); ai=c; i+;printf(请输入中序序列:n);while(d!=n)d=getchar();bj=d;j+;g=create(&s,&s1,a,b
4、);printf(遍历输出后序序列:n);visit(&s4,g);printf(n);4. 子函数一，创建二叉树struct node * create(snode *s,snode1 *s1,char aMAX,char bMAX)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=a0; root=p;x=seek(a0,b);push(s,x);push1(s1,p);while(ai!=n) num=seek
5、(ai,b); p=(struct node *)malloc(sizeof(BTree); p-lchild=NULL;p-rchild=NULL;p-data=ai; if(numlchild=p;push(s,num);push1(s1,p); else if(numgettop(s) while(s-top!=-1&numgettop(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 *
6、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遍历输出后序序列:edcba3、运行界面。五、实验总结你在编程过程中花时多少？五个小时多少时间在纸上设计？半个小时多少时间上机输入和调试？四个小时，主要是用来调试，程序编写完成后有很多错误，需要一个个的找，有些错误看起来没什么问题，所以用了很长时间。你的收获有哪些？用非递归法建立二叉树，让我们对于二叉树的建立过程掌握得更加清楚明了。用先序中序建立，用后序遍历，让我们对于二叉树的三种遍历方法都能掌握。教师评语：实验成绩：指导教师签名： 批阅日期：