后序遍历的⾮递归算法(C详细)后序遍历⼆叉树是先访问左⼦树,再访问右⼦树,最后访问根结点。
算法思想:
1. 先沿根结点,依次⼊栈,直到左孩⼦为空
2. 读取栈顶元素;如果其右孩⼦不空且未被访问过,将右⼦树转执⾏ 1;
3. 否则,栈顶元素出栈并访问。
void PostOrder(BiTree T){
InitStack(S);
p=T;
r=NULL;
while(p!=NULL||!IsEmpty(s)){
if(p!=NULL){//⾛到最左边
push(S,p);
p=p->lchild;
}
else{//向右
GetTop(S,p);//读栈顶节点(⾮出栈)
if(p->rchild&&p->rchild!=r){//若右⼦树存在,且未被访问过
p=p->rchild;//转向右
}
else{//否则弹出结点并访问
pop(S,p);
visit(p->data);//访问该结点
r=p;//记录最近访问的结点
p=NULL;//结点访问完后,重置p指针
}
}
}
后序序列D E B C A
以此为例,按照代码推演⼀遍:
按照第⼀个if语句中的 p!=NULL 且 p=p->lchild;
依次将 ABD ⼊栈
此时,p指针是指向D结点的左⼦树,所以为空;
跳出第⼀个if(p!=NULL)判断
然后转到 GetTop(S,p); 语句
将p指针指向栈顶的D结点;
然⽽ if(p->rchild) 判断中,D也⽆右结点。
这时转到pop语句;将D结点作为后序遍历的第1个结点,且r指针指向D
因为p置为NULL了,所以跳转到GetTop(S,p);p指向了栈顶B结点.
可知p=p->rchild,把p指针指向了B的右结点E;(此时r指向D,p指向E)
因为p!=NULL,会push(S,p); E结点⼊栈
此时堆栈情况:
因为E⽆左⼦树,同时E也⽆右⼦树,
if(p->rchild&&p->rchild!=r)
所以出栈访问,将E结点作为后序遍历的第2个结点;
r指向E结点,p置空
pop(S,p);
visit(p->data);
r=p;
p=NULL;
之后因为r指向E,p指向B (因为GetTop(S,p); 会把p指向B)
p->rchild!=r 会阻⽌再次访问 访问过的结点,即E结点,所以将B出栈,将E结点作为后序遍历的第3个结点;
r指向B,p置空
接着对栈顶元素A进⾏判断,C结点相应⼊栈出栈,同理,r指针指向C,防⽌⼆次访问右⼦树C;
先序中序后序遍历二叉树最后将A出栈,栈空,break while循环。
r指针的作⽤:
可以看出p指针指向栈顶元素时,如果元素存在右⼦树,且r指针保留了访问过的右⼦树,就会阻⽌访问,直接使栈顶元素出栈这也是后序遍历不同于先序、中序,所要特别处理的地⽅。
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论