一． 实验目的 （1）掌握二叉树的逻辑结构，遍历二叉树的非递归方法； （2）熟悉掌握二叉链表存储二叉树的结点定义； （3）掌握中序非递归遍历二叉树过程中栈的变化情况； （4）学会利用递归方法建立二叉树； （5）会编写中序遍历二叉树的非递归算法。 二． 实验内容 编写程序，用先序递归的方法建立二叉树，建立二叉树后，用中序非递归方法遍历该 二叉树，并输出遍历序列。 三． 源程序及主要算法说明 # #include #include #define N 10 struct node { int data; struct node *lch; struct node *rch; }; typedef struct node bitree; typedef struct { bitree *elem[N]; int top; }Stack; Stack InitStack() { Stack S; S.top=-1; return(S); } void In_Bt(bitree *root) { bitree *Ss[10]; //定义栈数组 

bitree *p; Stack kk; kk=InitStack(); p=root; while((p!=NULL)||(kk.top!=-1)) { //当栈顶不空或者是结点不空时 if(p!=NULL) { kk.top++; Ss[kk.top]=p; //进栈 p=p->lch; // 进入左子树访问 } else { p=Ss[kk.top]; //栈顶元素赋值给 p kk.top--; //出栈 printf("%d",p->data); //访问该结点 p=p->rch; //进入右子树访问 }printf("\n"); } } bitree *creat() { bitree * t; int x; scanf("%d",&x); if (x==0) t=NULL; else { t=(bitree*)malloc(sizeof(bitree)); t->data=x; t->lch=creat(); t->rch=creat(); } return(t); } main(){ bitree *root; 

printf("\ninput the number:"); root=creat(); printf("\n\nInorder result:"); In_Bt(root); } 四． 主要问题和解决方案 主要问题：本来是想要把栈的定义封装起来的，结果老是出错。函数不会调 用，一直出错。 解决方案：一开始封装不成功的时候我是用数组，后来第二节上机课借鉴了 同学的程序自己改了过来。 五． 测试数据及结果 六． 心得体会与自我评价 体会：知识好像就是循环渐进，总是有运用到以前的知识，只不过改了方式去利 用。 自我评价：由于老师上课把实验基本的步骤都讲了，所以感觉很容易就能写出来，只 不过有些细节的地方还是不太会，出现错误也不知道怎么改，有时候只好 放弃换成别的。不断改进，加油。 

七． 教师评分