数据结构试验报告用先序中序建立二叉树后序遍历非递归

《数据结构试验报告用先序中序建立二叉树后序遍历非递归》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《数据结构》实验报告◎实验题目:创建并遍历二叉树◎实验目的：熟悉二叉树存储结构，熟悉二叉树的三种遍历方法，并能用非递归的方法建立并且遍历二叉树。◎实验内容：用先序和中序建立二叉树，用后序遍历并输出二叉树，要求算法非递归。一、需求分析该程序用非递归的方法，利用先序和中序建立二叉树，然后用后序遍历的方法输出二叉树的元素。1、输入的形式和输入值的范围；程序运行时输入二叉树的先序和中序序列，为字符型元素。2、输出的形式；运行结果为输出二叉树的后序序列，亦为字符型元素。3、程序所能达到的功能；本程序可以建立一个二叉树存储结构，并且访问其结

2、点元素。4、测试数据：输入：先序：abcde中序：edcba输出：后序：edcba二概要设计1.本程序中首先需定义二叉树的节点类型，节点为一个含有数据与和指针域的结构体。2.其次，本程序中需要用两个栈，一个用来存放指针，一个用来存放数组元素的下标。3.主程序中，分别输入两个字符串，作为二叉树的先序和中序序列；两个子函数分别实现创建二叉树和后序遍历输出二叉树的功能。而在子函数中还调用了例如出栈入栈等子函数。三详细设计1. 定义二叉树节点类型structnode{chardata;structnode*lchild;structno

3、de*rchild;}BTree; 2.定义两个栈的类型structsnode{inttop;inta[MAX];};structsnode1{inttop;structnode*c[MAX];};3．主函数voidmain(){chara[MAX]={0};charb[MAX]={0};charc=0,d=0;inti=0,j=0;structnode*g;snodes;snode1s4,s1;Initstack(&s);Initstack1(&s4);Initstack1(&s1);printf("请输入先序序列:");

4、while(c!=''){c=getchar();a[i]=c;i++;}printf("请输入中序序列:");while(d!=''){d=getchar();b[j]=d;j++;}g=create(&s,&s1,a,b);printf("遍历输出后序序列:");visit(&s4,g);printf("");}4.子函数一，创建二叉树structnode*create(snode*s,snode1*s1,chara[MAX],charb[MAX]){inti=1,num,x;structnode*p,*

5、q,*r,*root;p=(structnode*)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]!=''){num=seek(a[i],b);p=(structnode*)malloc(sizeof(BTree));p->lchild=NULL;p->rchild=NULL;p->data=a[i];if(num

6、{q=get(s1);q->lchild=p;push(s,num);push1(s1,p);}elseif(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++;}returnroot;}5.子函数二，后序遍历输出二叉树voidvisit(snode1*s,structnode*root){structnode*p;p=root;do{while(p!=NULL){p

7、ush1(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，运行环境为visualC++。程序执行后显示：请输入先序序列：输入元素后显示请输入中序序列：然后程序自动运行，输出遍历输出后序序列:以及结果2、测试结果与分析；请输入先

8、序序列:abcde请输入中序序列:edcba遍历输出后序序列:edcba3、运行界面。五、实验总结你在编程过程中花时多少？五个小时多少时间在纸上设计？半个小时多少时间上机输入和调试？四个小时，主要是用来调试，程序编写完成后有很多错误，需要一个个的找，有些错误看起