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

《数据结构》实验报告 ◎实验目: 实验目的：实验内容：一、需求分析 1、输入的形式和输入值的范围；2、输出的形式；3、程序所能达到的功能；4、测试数据：二 概要设计 三 详细设计 ?定义二叉树节点类型 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(numgettop(s)) { q=get(s1); q-lchild=p; push(s,num); push1(s1,p); } else if(numgettop(s)) { while(s-top!=-1numgettop(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!=-1give(s)-rchild==p) { p=pop1(s); printf(%c,p-data); } if(s-top!=-1) p=give(s)-rchild; }while(s-top!=-1); } 四 使用说明、测试分析及结果 1、说明如何使用你编写的程序；2、测试结果与分析；、运行界面。 五、实验总结 你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？你的收获有哪些？