本文是数据结构基础系列(6)：树和二叉树中第11课时二叉树遍历非递归算法的例程。
【二叉树遍历的非递归算法】 实现二叉树的先序、中序、后序遍历的非递归算法，，并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。 请利用二叉树算法库。
［参考解答］（btreee.h见算法库）
PreOrder1(BTNode *b){BTNode *St[MaxSize],*p;int top=-1;if (b!=NULL){top++;//根节点入栈St[top]=b;while (top>-1)//栈不为空时循环{p=St[top];//退栈并访问该节点top–;printf(“%c “,p->data);if (p->rchild!=NULL) //右孩子入栈{top++;St[top]=p->rchild;}if (p->lchild!=NULL) //左孩子入栈{top++;St[top]=p->lchild;}}printf(“\n”);}}void InOrder1(BTNode *b){BTNode *St[MaxSize],*p;int top=-1;if (b!=NULL){p=b;while (top>-1 || p!=NULL){while (p!=NULL){top++;St[top]=p;p=p->lchild;}if (top>-1){p=St[top];top–;printf(“%c “,p->data);p=p->rchild;}}printf(“\n”);}}void PostOrder1(BTNode *b){BTNode *St[MaxSize];BTNode *p;int flag,top=-1;//栈指针置初值if (b!=NULL){do{while (b!=NULL)//将t的所有左节点入栈{top++;St[top]=b;b=b->lchild;}p=NULL;//p指向当前节点的前一个已访问的节点flag=1;while (top!=-1 && flag){b=St[top];//取出当前的栈顶元素if (b->rchild==p)//右子树不存在或已被访问,访问之{printf(“%c “,b->data); //访问*b节点top–;p=b;//p指向则被访问的节点}else{b=b->rchild;//t指向右子树flag=0;}}}while (top!=-1);printf(“\n”);}}int main(){BTNode *b;CreateBTNode(b,”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”);printf(“二叉树b: “);DispBTNode(b);printf(“\n”);printf(“先序遍历序列:\n”);PreOrder1(b);printf(“中序遍历序列:\n”);InOrder1(b);printf(“后序遍历序列:\n”);PostOrder1(b);DestroyBTNode(b);return 0;}
注：在main函数中，创建的用于测试的二叉树如下——
送给中意的TA，背面写上：某年某月某日，
