最新公告
  • 新注册用户请前往个人中心绑定邮箱以便接收相关凭证邮件!!!点击前往个人中心
  • 数据结构笔记总结(5.9)二分搜索树前序遍历的非递归实现

    二分搜索树前序遍历的非递归实现

    前面学习栈的时候知道栈有一种非常重要的应用,那就是在我们系统中做程序调用,可以把程序执行到了哪里给压入系统栈,方便在子过程结束之后找到原来的位置。

    现在对于我们的遍历代码来说,每次访问节点之后,其实就要先访问左子树,再访问右子树,这种情况下,我们就可以借助栈来记录我们之后要访问的节点的顺序,

    首先访问28节点,由于我们采用非递归的写法,所以一上来就把28压入栈,压入栈的意思就是接下来就要访问28这个根节点了。

    程序开始运行,首先把栈顶元素拿出来进行相应的操作,这样28这个节点就访问完了。

    之后,由于我们访问能力28,下面就要访问28的子树,这里将28的两个孩子压入栈,先压入右孩子,也就是30,再压入左孩子,也就是16,这是因为我们栈是后入先出的,所以我们要先压入后续访问的节点。

    然后现在栈顶的元素16就是我们先要访问的节点了,栈顶元素出栈,对16相应的进行操作,16这个节点就访问完了。

    接下来,对16这个节点,先压入右孩子,再压入左孩子。

    之后,栈顶元素13就是我们要访问的节点,将13拿出来进行相应的操作,13就访问完了,接下来应该压入13的右孩子和左孩子,不过这里13的左右孩子都是空,我们就什么都不用压入了。

    继续来看栈顶元素,现在栈顶元素是22,对22进行操作,22就访问完了。

    同理,22左右孩子都为空,下面继续来看栈顶元素,此时栈顶元素是30,出栈进行相应的操作,30这个节点就访问完了。

    接下来对30的右左节点压栈,依次压入42和29。

    此时栈顶元素是29,出栈进行相应操作,29就访问完了,此时29左右孩子为空,不做任何操作。

    再访问栈顶节点,拿出42,对42进行操作,42这个节点就访问完了。此时栈为空,至此整个二分搜索树就遍历完成了。

    代码演示

    // 二分搜索树的非递归前序遍历
    public void preOrderNR(){
    
        if(root == null)
            return;
    
        Stack stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);
    
            if(cur.right != null)
                stack.push(cur.right);
            if(cur.left != null)
                stack.push(cur.left);
        }
    }
    

    运行程序,输出结果

    • 二分搜索树的非递归实现比递归实现复杂很多
    • 中序遍历和后序遍历的非递归实现更复杂
    • 中序遍历和后序遍历的非递归实现的实际应用不广

    这一小节我们完成了二分搜索前序遍历的非递归写法。

    对于前序遍历来说,不管是递归写法还是非递归写法,对于我们这棵树遍历过程中都是一扎到底。

    这种方式其实还有另外一个名字,叫做“深度优先遍历”,和此对应的另一种方式就是“广度优先遍历”,广度优先遍历出的结果顺序其实是二分搜素层序遍历的顺序,具体下一小节再学习。

    源码下载

    [dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

    导航目录

    [dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

    本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
    极客文库 » 数据结构笔记总结(5.9)二分搜索树前序遍历的非递归实现

    常见问题FAQ

    如果资源链接失效了怎么办?
    本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
    如果用户分享的资源与描述不符怎么办?
    可以联系客服QQ:2580505920,如果要求合理可以安排退款或者退赞助积分。
    如何分享个人资源获取赞助积分或其他奖励?
    本站用户可以分享自己的资源,但是必须保证资源没有侵权行为。点击个人中心,根据操作填写并上传即可。资源所获收益完全归属上传者,每周可申请提现一次。
    如果您发现了本资源有侵权行为怎么办?
    及时联系客服QQ:2580505920,核实予以删除。

    参与讨论

    • 176会员总数(位)
    • 3737资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 542稳定运行(天)

    欢迎加入「极客文库」,成为原创作者从这里开始!

    立即加入 了解更多
    成为赞助用户享有更多特权立即升级