在后序遍历二叉树时,只有遍历完左右子树后才能访问节点元素。故在退栈到根节点时必须判断是左子树还是右子树返回 的。
若是从左子树返回,还要遍历完右子树,否则,即可访问节点元素。只要将返回到栈顶结点的前一个结点保存到一个变量中,
判断它是栈顶结点的左孩子还是右孩子就可以区分。
算法描述:
typedef struct node
{
char data;
node* lchild;
node* rchild;
}Node,*pNode;
void PostOTraverseNRC(pNode T)
{
pNode p=T;
stack<pNode> STACK;
do
{
while(p!=NULL)
{//先遍历完当前节点的左子树
STACK.push(p);
p=p->lchild;
}
while(!STACK.empty()&&STACK.top()->rchild==p)
{//判断是否是从右子树返回(p当前的值等于栈顶元素的右子树根节点时)
p=STACK.top();
STACK.pop();
VisitTree(p);
}
if(!STACK.empty())
{//遍历右子树
p=STACK.top()->rchild;
}
} while (!STACK.empty());
}
参考:孙泽宇, 赵国增, 舒云星《二叉树后序遍历的递归和非递归算法》