请帮我详细解释这个算法

来源:百度知道 编辑:UC知道 时间:2024/05/22 00:41:43
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; //有mark域的结点指针类型
void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈
{
PMType a;
InitStack(S); //S的元素为PMType类型
Push (S,{T,0}); //根结点入栈
while(!StackEmpty(S))
{
Pop(S,a);
switch(a.mark)
{
case 0:
Push(S,{a.ptr,1}); //修改mark域
if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树
break;
case 1:
Push(S,{a.ptr,2}); //修改mark域
if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树
break;
case 2:
visit(a.ptr); //访问结点,返回
}
}//while
}//PostOrder_Stack
分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作.

这个注释已经比较清楚了,就是利用栈,只有当从栈中弹出的元素mark为2时才访问该节点,以此来保证后序遍历
mark=0则修改mark为1,存在左子树就进栈,不存在也无所谓因为已经标记为左子树已访问了
mark=1则修改mark为2,存在右子树就进栈,不存在也无所谓因为已经标记为右子树已访问了
mark=2访问节点,进入下次循环处理弹出的下一个节点