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

1、数据结构实验报告实验题目:创办并遍历二叉树实验目的：熟悉二叉树积蓄结构，熟悉二叉树的三种遍历方法，并能用非递归的方法建立并且遍历二叉树。实验内容：用先序和中序建立二叉树，用后序遍历并输出二叉树，要求算法非递归。一、需求剖析该程序用非递归的方法，利用先序和中序建立二叉树，今后用后序遍历的方法输出二叉树的元素。1、输入的形式和输入值的范围；程序运行时输入二叉树的先序和中序序列，为字符型元素。2、输出的形式；运行结果为输出二叉树的后序序列，亦为字符型元素。3、程序所能达到的功能；本程序可以建立一个二叉树积蓄结构，并且接见其结点元素。4、测试数据：输入：先序：abcde中序：edcba输出：后序：ed

2、cba二大纲设计本程序中第一需定义二叉树的节点种类，节点为一个含有数据与和指针域的结构体。其次，本程序中需要用两个栈，一个用来存放指针，一个用来存放数组元素的下标。主程序中，分别输入两个字符串，作为二叉树的先序和中序序列；两个子函数分别实现创办二叉树和后序遍历输出二叉树的功能。而在子函数中还调用了比方出栈入栈等子函数。三详细设计1.?定义二叉树节点种类structnodechardata;structnode*lchild;structnode*rchild;BTree;?定义两个栈的种类structsnodeinttop;intaMAX;structsnode1inttop;structno

3、de*cMAX;3主函数voidmain()charaMAX=0;charbMAX=0;charc=0,d=0;inti=0,j=0;structnode*g;snodes;snode1s4,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);printf(遍历输出后序序列:n);visit(&s4,g);prin

4、tf(n);子函数一，创办二叉树structnode*create(snode*s,snode1*s1,charaMAX,charbMAX)inti=1,num,x;structnode*p,*q,*r,*root;p=(structnode*)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(ai,b);p=(structnode*)malloc(sizeof(BTree);p-lchild=NULL

5、;p-rchild=NULL;p-data=ai;if(numlchild=p;push(s,num);push1(s1,p);elseif(numgettop(s)while(s-top!=-1&numgettop(s)r=pop1(s1);pop(s);r-rchild=p;push(s,num);push1(s1,p);i+;returnroot;子函数二，后序遍历输出二叉树voidvisit(snode1*s,structnode*root)structnode*p;p=root;dowhile(p!=NULL)push1(s,p);p=p-lchild;while(s-top!=-1

6、&give(s)-rchild=p)p=pop1(s);printf(%c,p-data);if(s-top!=-1)p=give(s)-rchild;while(s-top!=-1);四使用说明、测试剖析及结果1、说明如何使用你编写的程序；程序名为，运行环境为visualC+。程序执行后显示：请输入先序序列：输入元素后显示请输入中序序列：今后程序自动运行，输出遍历输出后序序列:以及结果2、测试结果与剖析；请输入先序序列:abcde请输入中序序列:edcba遍历输出后序序列:edcba3、运行界面。五、实验总结你在编程过程中花时多少？五个小时多少时间在纸上设计？半个小时多少时间上机输入和调试？四个小时，主若是用来调试，程序编写完成后有很多错误，需要一个个的找，有些错误看起来没什么问题，所以用了很长时间。你