Question

c++ 采用二叉链表作存储结构，实现二叉树非递归后序遍历算法

急用！！！

Answer 1

链接存储的二叉树类型和结构定义如下：
typedef struct bnode
{
ElemType data;
struct bnode *lchild, *rchild;
} btree;

后序遍历
void postorder(btree *bt)
{
btree *p=bt, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int tag[MAX];
int top=-1;

do
{
while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
tag[top] = 0;
p = p->lchild;
}

if(top >= 0) //所有左孩子处理完毕后
{
if(!tag[top]) //如果当前结点的右孩子还没被访问

{
p = stack[top];//输出栈顶结点 ，但不退栈 ，因为要先输出其孩子结点

p = p->rchild; //处理其右孩子结点

tag[top] = 1; //表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出

}
else //如果该结点的左右孩子都被访问过了

{

printf("%d", stack[top--]->data); //栈顶元素出栈，输出该结点，此时结点p指向NULL

}
}
} while((p != NULL)||(top >= 0));
}