最新公告
  • 欢迎您光临极客文库,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 前序遍历

    • 前序遍历是最自然的遍历方式
    • 前序遍历是最常用的遍历方式

    中序遍历

    想象一下,可以先访问这个节点,再访问这个节点的左右子树,相应的我们访问节点的顺序就可以改变,比如我们可以先访问节点的左子树,再访问节点,然后访问节点的右子树,这样做也将整个二分搜素树进行了遍历。

    这种逻辑就叫二分搜索树的中序遍历,“中”体现在访问该节点放在了遍历这个节点的左子树和右子树的中间。

    代码演示

    下面用代码演示一下中序遍历

    // 二分搜索树的中序遍历
    public void inOrder(){
        inOrder(root);
    }
    
    // 中序遍历以node为根的二分搜索树, 递归算法
    private void inOrder(Node node){
        if(node == null)
            return;
    
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }
    

    下面我们就可以在main函数中测试一下

    public class Main {
    
        public static void main(String[] args) {
    
            BST bst = new BST<>();
            int[] nums = {5, 3, 6, 8, 4, 2};
            for(int num: nums)
                bst.add(num);
    
            /////////////////
            //      5      //
            //    /   \    //
            //   3    6    //
            //  / \    \   //
            // 2  4     8  //
            /////////////////
            bst.preOrder();
            System.out.println();
    
            bst.inOrder();
            System.out.println();
    
        }
    }
    

    输出结果如下:

    中序遍历的结果就是我们所有的二分搜索树排序后的结果

    后序遍历

    后序遍历就是先访问节点的左子树,再访问节点的右子树,最后访问这个节点,这就是后序遍历

    代码演示

    // 二分搜索树的后序遍历
    public void postOrder(){
        postOrder(root);
    }
    
    // 后序遍历以node为根的二分搜索树, 递归算法
    private void postOrder(Node node){
        if(node == null)
            return;
    
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }
    

    最后在main函数里调用postOrder(),输出结果。

    后序遍历也有它的应用场景,有些情况下,我们必须先处理完左子树所有节点以及右子树所有节点,也就是说必须先处理完这个节点的孩子节点之后再来处理这个节点。

    一个典型的应用是在内存释放方面,如果需要我们手动释放内存的话,我们就需要先把这个节点的孩子节点都释放完再释放这个节点本身,这种情况下就可以用后序遍历。

    对于java语言来说,有自动处理垃圾机制,所以就不需要对内存管理进行手动的控制。

    源码下载

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

    导航目录

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

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

    常见问题FAQ

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

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者

    Leave a Reply

    Hi, 如果你对这款资源有疑问,可以跟我联系哦!

    联系发布者
    • 108会员总数(位)
    • 3695资源总数(个)
    • 3本周发布(个)
    • 0 今日发布(个)
    • 182稳定运行(天)

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

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