• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(5.7)二分搜索树的中序遍历和后序遍历

极客笔记 Geekerstar 11个月前 (05-16) 319次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

前序遍历

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

中序遍历

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

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

代码演示

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

// 二分搜索树的中序遍历
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<Integer> 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语言来说,有自动处理垃圾机制,所以就不需要对内存管理进行手动的控制。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(5.7)二分搜索树的中序遍历和后序遍历
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00