注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东南隅

wantnon的blog

 
 
 

日志

 
 
 
 

二叉树中序遍历的栈实现  

2010-09-13 23:05:56|  分类: 算法/程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

要点:在递归程序的栈模拟中,每次进栈出栈的节点是一个程序状态层,而且必须同时保存程序在此层的断点位置,或称此层的阶段。而在二叉树遍历的栈实现中虽然每个节点与递归程序节点相比很退化,但也同样需要“保存断点”,以便用来标记此节点是两个子树都还没有被访问过,还是左子树已被访问过而右子树还未访问,即此节点的阶段。如图:

image

有了上面这个“保存断点”的概念后,算法就很容易得到了。

数据结构说明:
struct v{
    int breakpoint;//取值为0或1。取0代表v处于阶段0;取1代表v处于阶段1
};
程序:
根节点vt.breakpoint=0;
根节点vt入栈;
while(1){
    if(栈空){//说明已遍历完
        break;
    }
    //检测栈顶节点v的断点位置
    if(v.breakpoint==0){//如果v处在阶段0,即左子树还未访问
        if(v有左孩子vl){
            v.breakpoint=1;//将断点位置改为1
            vl.breakpoint=0;
            vl入栈;
        }else{//v没有左孩子
            v.breakpoint=1;//将断点位置改为1
        }
    }else{//如果v处在阶段1,即左子树已访问
        输出v;
        v出栈;
        if(v有右孩子vr){
            vr.breakpoint=0;
            vr入栈;
        }else{//没有右孩子
            什么也不做;
        }
    }
}

  评论这张
 
阅读(56)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018