填空题
[说明] 假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。
Void postorder (btree * B)
{
btree * stack [m0] , *p;
int tag [m0], top =0;
p=b;
do
{
while (p! =NULL)
{
top+ +;
{{U}}(1) {{/U}}
tag [top] =0;
p =p- ＞left;
}
if (top ＞0)
{
{{U}}(2) {{/U}}
if (tag[top3 = =1)
{
{{U}}(3) {{/U}}
print ("%d", p- ＞data);
}
if(top＞0)
{
{{U}}(4) {{/U}}
tag [top] = 1;
}
}
} while (p! = NULL && top ! =0)
}
【正确答案】
1、(1) stack [top]=p；
【答案解析】(2) p=stack [top]；
(3) top--；
(4) p=p->right；
[解答要点] 根据后序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的结点，先扫描根结点的所有左结点并入栈，出栈一个结点，然后扫描该结点的右结点并入栈，再扫描该右结点的所有左结点并入栈，当一个结点的左右子树均访问后再访问该结点，如此这样，直到栈空为止。在访问根结点的右子树后，当指针p指向右子树树根时，必须记下根结点的位置，以便在遍历右子树之后正确返回。这里采用两个栈stack 和tag，并用一个共同的栈顶指针，并用一个共同的栈顶指针，一个存放指针值，一个存放左右子树标志(0为左子树，1为右子树)。退栈时在退出结点指针的同时去判断是遍历左子树返回的还是遍历右子树返回的，以决定下一步是继续遍历右子树还是访问根结点。