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

前序遍历

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

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

中序遍历

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

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

代码演示

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

// 二分搜索树的中序遍历
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();

    }
}

输出结果如下:
数据结构笔记总结(5.7)二分搜索树的中序遍历和后序遍历

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

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

后序遍历

后序遍历就是先访问节点的左子树,再访问节点的右子树,最后访问这个节点,这就是后序遍历
数据结构笔记总结(5.7)二分搜索树的中序遍历和后序遍历

代码演示

// 二分搜索树的后序遍历
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(),输出结果。

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

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

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

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

源码下载

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

导航目录

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

本站所有文章均来自互联网,如有侵权,请联系站长删除。极客文库 » 数据结构笔记总结(5.7)二分搜索树的中序遍历和后序遍历
分享到:
赞(0)

评论抢沙发

评论前必须登录!