【正确答案】根据后序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的结点，先遍历根结点的所有左结点并入栈，出栈一个结点，然后遍历该结点的右结点并入栈，再遍历该右结点的所有左结点并入栈，当一个结点的左、右子树均访问后再访问该结点，直到栈空为止。其中的难点是如何判断一个结点t的右结点已访问过，为此用p保存已访问过的结点(初值为NULL)，若t→right==p成立(在后序遍历中，t的右结点一定是在t之前访问)，说明t的左、右子树均已访问，现在应访问t。 实现本题功能的程序代码如下： void psorder(BTNode *t) { BTNode *stack[MaxSize]; BTNode *p; int flag,top=-1; //栈指针置初值 do { while(t) //将t的所有左结点入栈 { ++top; stack[top]=t; t=t→left; } p=NULL; //p指向当前结点的前一个已访问的结点 flag=1; //设置t的访问标记为已访问过 while(top!=-1 && flag) { t=stack[top]; //取出当前的栈顶元素 if(t→right==p) //右子树不存在或已被访问，访问之 { visit(t); //访问t,visit是已定义的函数 --top; p=t; //p指向已被访问的结点 } else { t=t→right; //t指向右子树 flag=0; //设置未被访问的标记 } } }while(top!=-1); }