二叉树中序遍历的非递归算法实现.doc

试验五课程名称实验室名称实验名称二叉树中序遍历的非递归算法实现指导教师成绩实验目的 二叉树中序遍历的非递归算法实现 实验原理和内容 二叉树中序遍历的非递归算法实现实验步骤 1.链式存储结构的定义和栈结构的定义 2.编写进栈函数push和出栈函数pop实现中序遍历过程中需存储的数的进栈和出栈过程 3.创建一棵二叉树 4.对该二叉树进行中序遍历，采用非递归算法实现 程序及运行结果（或实验数据记录及分析） #includestdio.h #includestdlib.h typedef char datatype; //* 链式存储结构*// typedef struct node{ datatype data; struct node *lchild,*rchild; }bintnode; typedef bintnode *bintree; typedef struct stack{ /* 栈结构定义*/ bintree data[100]; int top; }seqstack; void push(seqstack *s,bintree t) { s-data[s-top]=t; s-top++; } bintree pop(seqstack *s) { if (s-top!=0) { s-top--; return(s-data[s-top]); } else return NULL; } void createbintree(bintree *t) { char ch; if ((ch=getchar())== ) *t=NULL; else { *t=(bintnode *)malloc(sizeof(bintnode)); (*t)-data=ch; createbintree((*t)-lchild); createbintree((*t)-rchild); } } void inorder1(bintree t) { seqstack s; s.top=0; while((t!=NULL) || (s.top!=0)) { while (t) { push(s,t); t=t-lchild; } if (s.top!=0) { t=pop(s); printf(%c ,t-data); t=t-rchild; } } } main() { bintree root; printf(input the tree as preorder:); createbintree(root); printf(\n中序遍历结果是: ); inorder1(root); } 在屏幕上输出的结果：