前序遍历非递归算法：
二叉树前序遍历的非递归算法的关键：在前序遍历完某结点的整个左子树后，如何找到该结点的右子树的根指针。
解决办法：在访问完该结点后，将该结点的指针保存在栈中，以便以后能通过它找到该结点的右子树。
前序遍历非递归原理图：
1、边访问边进栈
2、左子树为空时，出栈，结点返回，转向右子树
当栈为空且p=NULL时，前序遍历完毕
伪代码：
void preorder(BiNode *bt)
{
linklist_t *s = linkstack_init();
BiNode *p=bt;
while (p!=NULL&&linkstack_isempty(s)!=1)
{
while(p!=NULL)
{
printf("%d ",p->data);
linkstack_push (s,p->data);
p=p->lchild;
}
if(linkstack_isempty(s)!=1)
{
p=linkstack_pop (s);
p=p->rchild;
}
}
}
中序遍历非递归算法
原理图
代码：
void inorder(BiNode *bt)
{
linklist_t *s = linkstack_init();
BiNode *p=bt;
while (p!=NULL&&linkstack_isempty(s)!=1)
{
while(p!=NULL)
{
linkstack_push (s,p->data);
p=p->lchild;
}
if(linkstack_isempty(s)!=1)
{
p=linkstack_pop (s);
printf("%d ",p->data);
p=p->rchild;
}
}
}
后序遍历非递归算法（较难）
typedef struct element {
BiNode *ptr;
int flag;
} element;
void PostOrder(BiNode *bt) { //树的后序遍历
SqStack s;
s = InitStack_1();
BiNode *p = bt;
element elem;
while (p != NULL || StackEmpty_1(&s) != 1) { //当p为空，栈也为空时退出循环
if (p != NULL) {//第一次入栈，访问左子树
elem.ptr = p;
elem.flag = 1; //标记flag为1，表示即将第一次入栈
Push_1(&s, elem); //将指针p的结点第一次压入栈中
p = p->Lchild;
} else {
elem = Pop_1(&s); //出栈
p = elem.ptr; //p指向当前要处理的结点
if (elem.flag == 1) {
//flag==1时，说明只访问过左子树，还要访问右子树
elem.flag = 2;
Push_1(&s, elem); //结点第二次压入栈中
p = p->rchild;
} else {
//flag==2时，左右子树都已经访问过了
visit(p->data);
p = NULL; //访问后，p赋为空，确保下次循环时继续出栈（相当于回退）
}
}
}
DestroyStack_1(&s);
}
