资讯专栏INFORMATION COLUMN

算法 | 遍历二分搜索树

vvpvvp / 1615人阅读

摘要:又是来自我的好朋友的投稿,以下是原文基本定义二分搜索树的每个子节点最多有两个叶子节点二分搜索树的每个节点最多有一个根节点存储的元素必须具有可比较性二分搜索树每个子节点的值大于其左子节的所有节点的值小于其右子节点的所有节点的值二分搜索树不一定

又是来自我的好朋友 EvilSay 的投稿,以下是原文:

1、基本定义

二分搜索树的每个子节点最多有两个叶子节点

二分搜索树的每个节点最多有一个根节点

存储的元素必须具有可比较性

二分搜索树每个子节点的值

大于其左子节的所有节点的值

小于其右子节点的所有节点的值

二分搜索树不一定是满的

2、二分搜索树 Java 实现
/**
 * @Author: EvilSay
 * @Date: 2019/8/6 19:00
 */
public class BSTMain > {
    private class Node {
        public E e;
        private Node left, right;

        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    //根节点
    private Node root;
    private int size;

    public BSTMain() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
    public void add(E e){

        root = add(this.root, e);

    }

    // 向node为根的二分搜索树中插入元素E,递归算法
    // 返回插入新节点后二分搜索树的根
    private Node add(Node node, E e){

        if (node == null){

            size ++;
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0)
            node.left = add(node.left, e);
        else if (e.compareTo(node.e) > 0)
            node.right = add(node.right,e);
        return node;
    }

    // 看二分搜索树中是否包含元素e
    public boolean contains(E e){
        return contains(root,e);
    }

    // 看以node为根的二分搜索树中是否包含元素e,递归算法
    private boolean contains(Node node, E e){
        if (node == null)
            return false;
        if (e.compareTo(node.e) == 0)
            return true;
        else if (e.compareTo(node.e) < 0)
            return contains(node.left, e);
        else
            return contains(node.right,e);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTSString(root,0,res);
        return res.toString();
    }

    // 生成以node为根节点,深度为depth的描述二叉树的字符串
    private void generateBSTSString(Node root, int depth, StringBuilder res) {
        if (root == null){
            res.append(generateDepthString(depth) + "null
");
            return;
        }
        res.append(generateDepthString(depth) + root.e + "
");
        generateBSTSString(root.left, depth + 1 ,res);
        generateBSTSString(root.right, depth + 1, res);

    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++)
            res.append("--");
        return res.toString();
    }
}
3、图解二分搜索树

从图上我们看出二分搜索树每个节点的值大于其左子节的所有节点的值小于其右子节点的所有节点的值。

4、前序遍历

前序遍历也叫先序遍历,访问顺序是根左右,也就是先访问根节点,再到左子树,最后才到右子树。所以上图所示的访问顺序是 5、3、2、4、8、7、9。

二分搜索树前序遍历递归版与非递归版

    //前序遍历以node为根的二分搜索树,递归算法
    private void preOrder(Node node){

        if (node == null)
            return;

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }
    
    //二分搜索树的前序遍历递归调用
    public void preOrder(){
        preOrder(root);
    }
    
    //二分搜索树的前序遍历非递归写法
    public void preOrderNG(){
        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);
        }
    }

理解非递归的实现逻辑、推导出前序递归的实现

创建一个堆栈,我们把根节点 5 推入栈中,接下来我们就要访问 5 这个根节点了,所有把 5 从栈中推出 。

推出的元素有 {5},栈中的元素有 [] 。

在推入 5 的子节点就是 3,8,我们先入后出,先推入 8 再推入 3,现在堆栈的元素有 [8,3],栈顶的 3 就是我们下一次要访问的节点所以把 3 推出 。

推出的元素有 {5,3},栈中的元素有 [8] 。

在推入 3 的子节点就是 2,4 继续先入后出,先推入 4 再推入 2,现在堆栈的元素有 [8,4,2],栈顶的 2 就是我们下一次要访问的节点所以把 2 推出 。

推出的元素有 {5,3,2},栈中的元素有 [8,4] 。

访问栈顶 4,由于 2 和 4 没有子节点。所以我们直接把栈顶中的 4 推出 。

推出的元素有 {5,3,2,4},栈中的元素有 [8] 。

访问栈顶 8 把 8 推出栈堆,再把 8 的子节点 7、9 推入栈中,先推入 9 后推入 7 。

推出的元素有 {5,3,2,4,8},栈中的元素有 [9,7] 。

访问 7,没有子节点,推出。

推出的元素有 {5,3,2,4,8,7},栈中的元素有 [9] 。

访问 9,没有子节点,推出。

推出的元素有 {5,3,2,4,8,7,9},栈中的元素有 [] 。

5、中序遍历

中序遍历,访问顺序是左根右,也就是先访问左子树,再到根节点,最后才到右子树。所以上图所示的访问顺序是 2、3、4、5、7、8、9。

二分搜索树中序遍历递归版与非递归版

    //递归调用
    public void inOrder(){
        inOrder(root);
    }
    //二分搜索树的中序遍历递归写法
    private void inOrder(Node root){
        if (root == null)
            return;

        inOrder(root.left);
        System.out.println(root.e);
        inOrder(root.right);
    }
    //二分搜索树中序遍历给递归写法
    public void preInOrderNG(){
        // 创建栈,和前序遍历类似
        Stack stack = new Stack<>();
        
        Node node = root;
        //添加暂时完毕,开始pop元素
        while(node!=null || stack.size()>0 ){

            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            //一边pop并且一边进行判断,右结点不会null的,右子树,继续按照添加方法,将最左结点全部添加进去
            if(stack.size()>0){
                Node pop = stack.pop();
                System.out.print(pop.e+"  ");
                if(pop.right!=null){
                    node = pop.right;
                }
            }
        }

理解非递归的实现逻辑、推导出中序递归的实现

首先我们把 5 这个节点推入栈中,再把 5 的左子节点 3 推入,再把 3的 左子节点 2 推入,再把 2 的左子节点推入(此时 2 的左子节点为空,node==null while 循环退出)。

推出的元素有 {},栈中的元素有 [5,3,2]。

node 为空,但我们栈中还有元素,访问栈顶元素 2,并查看 2 是否有右子节点。没有则推出栈并结束循环。

推出的元素有 {2},栈中的元素有 [5,3]。

访问栈顶元素 3,把 3 推出栈中,并把 3 的右子节点 4 推入栈中,结束循环。

推出的元素有 {2,3},栈中的元素有 [5]。

访问栈顶元素5,把5推出栈中。把5的右子节点8推入栈中,并把8的左子节点7推入栈中,结束循环。

推出的元素有 {2,3,5},栈中的元素有 [8,7]

访问栈顶元素 7,并查看 2 是否有右子节点。没有则推出栈并结束循环。

推出的元素有 {2,3,5,7},栈中的元素有 [8]。

访问栈顶元素 8,把 8 推出栈中。把 8 的右子节点 9 推入栈中

推出的元素有 {2,3,5,7,8},栈中的元素有 [9]。

访问栈顶元素 9,并查看 2 是否有右子节点。没有则推出栈并结束循环。

推出的元素有 {2,3,4,5,7,8,9},栈中的元素有 []。

6、后序遍历

中序遍历,访问顺序是左右根,也就是先访问左子树,再到右子树,最后才到根节点。所以上图所示的访问顺序是 2、4、3、7、9、8、5。

二分搜索树后序遍历递归版与非递归版

//递归调用
public void postOrder() {
    postOrder(root);
} 

//二分搜索树的后序遍历递归方法
private void postOrder(Node node){
    if (node == null)
        return;

    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.e);
} 

public void postOrderNG(){
    Stack stack = new Stack<>();
    //利用一个list集合记录已将被遍历过的根节点,防止产生死循环
    ArrayList list = new ArrayList<>();
    Node node = root;
    Node proud; 
    int flag; 

    //首页检查完树的左子树,再右子数,最后将根节点输出
    while (node != null || stack.size() > 0){
        //将最左子树添加完毕
        while (node != null){
            stack.push(node);

            node = node.left;
        } 

        //和中序遍历相似,为先输出左子节点,但是做节点输出完毕之后,不能直接将根节点弹出,而是必须先将右节点弹出,
        //最后再将根节点弹出来,就会牵扯到一个根节点的访问状态的问题,是否已经被遍历过了
        if (stack.size() > 0){

            Node peek = stack.peek();
            if (peek.right != null){
                boolean con = list.contains(peek);
                if (con){
                    Node pop = stack.pop();
                    System.out.println(pop.e);
                }else{
                    list.add(peek);
                    node = peek.right;
                }
            }else {
                Node pop = stack.pop();
                System.out.println(pop.e);
            }

        }

    }
}

理解非递归的实现逻辑、推导出后序递归的实现

把 5 这个节点推入栈中,再把 5 的左子节点 3 推入,再把 3 的左子节点 2 推入,再把 2 的左子节点推入(此时 2 的左子节点为空,node==null while 循环退出)。

推出的元素有 {},栈中的元素有 [5,3,2]。

node 为空但我们栈中还有元素,访问栈顶元素 2,并查看 2 是否有左子节点。没有则推出栈并结束循环。

推出的元素有 {2},栈中的元素有 [5,3]。

访问栈顶元素 3,3 的右子节为 4,判断 list 中是否有 3,没有则把 3 放入 list 中并把 node 赋值为 4 结束循环。

推出的元素有 {2},栈中的元素有 [5,3]。

node 为 4,把 4 推入栈中,并访问栈顶元素 4,并查看 4 是否有右子节点。没有则推出栈并结束循环。

推出的元素有 {2,4},栈中的元素有 [5,3]。

访问栈顶元素 3,list 中有 3,把 3 的推出栈中并结束循环。

推出的元素有 {2,4,3},栈中的元素有 [5]。

访问栈顶元素 5,5 的右子节为 8,判断 lis t中是否有 8,没有则把 5 放入 list 中并把 node 赋值为 8 结束循环。

推出的元素有 {2,4,3},栈中的元素有 [5]。

node 为 8,把 8 推入栈中,并访问栈顶元 素8,8 有左子节点为 7。把 7 推入栈中。

推出的元素有 {2,4,3},栈中的元素有 [5,8,7]。

访问栈顶元素 7,并查看 7 是否有右子节点。没有则推出栈并结束循环。

推出的元素有 {2,4,3,7},栈中的元素有 [5,8]。

访问栈顶元素 8,8 的右子节点为 9。判断 list 中是否有 9,没有则把 8 放入 list 中并把 node 并把 node 赋值为 9 结束循环。

推出的元素有 {2,4,3,7},栈中的元素有 [5,8]。

node 为 9,把 9 推入栈中,并访问栈顶元素 9,并查看 9 是否有右子节点。没有则推出栈并结束循环。

推出的元素有 {2,4,3,7,9},栈中的元素有 [5,8]。

访问栈顶元素 8,list 中有 8,把 8 的推出栈中并结束循环。

推出的元素有 {2,4,3,7,9,8},栈中的元素有 [5]。

node 为空栈中还有元素,访问栈顶元素 5,list 中有 5,把 5 的推出栈中并结束循环。

推出的元素有 {2,4,3,7,9,8,5},栈中的元素有 []。

推荐阅读:

1、java | 什么是动态代理

2、SpringBoot | 启动原理

3、SpringBoot | 自动配置原理

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/76286.html

相关文章

  • 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索

    摘要:在数据结构领域对应树结构来说二叉树是最常用的一种树结构,二叉树具有一个唯一的根节点,也就是最上面的节点。二叉树每个节点最多有两个孩子,一个孩子都没有的节点通常称之为叶子节点,二叉树每个节点最多有一个父亲,根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

    ghnor 评论0 收藏0
  • 【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索

    摘要:在数据结构领域对应树结构来说二叉树是最常用的一种树结构,二叉树具有一个唯一的根节点,也就是最上面的节点。二叉树每个节点最多有两个孩子,一个孩子都没有的节点通常称之为叶子节点,二叉树每个节点最多有一个父亲,根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

    FuisonDesign 评论0 收藏0
  • 我理解的数据结构(五)—— 二分搜索(Binary Search Tree)

    摘要:我理解的数据结构五二分搜索树一二叉树和链表一样,动态数据结构具有唯一根节点每个节点最多有两个子节点每个节点最多有一个父节点具有天然的递归结构每个节点的左子树也是二叉树每个节点的右子树也是二叉树一个节点或者空也是二叉树二二分搜索树是二叉树每个 我理解的数据结构(五)—— 二分搜索树(Binary Search Tree) 一、二叉树 和链表一样,动态数据结构 具有唯一根节点 每个节点最...

    xeblog 评论0 收藏0
  • 我理解的数据结构(五)—— 二分搜索(Binary Search Tree)

    摘要:我理解的数据结构五二分搜索树一二叉树和链表一样,动态数据结构具有唯一根节点每个节点最多有两个子节点每个节点最多有一个父节点具有天然的递归结构每个节点的左子树也是二叉树每个节点的右子树也是二叉树一个节点或者空也是二叉树二二分搜索树是二叉树每个 我理解的数据结构(五)—— 二分搜索树(Binary Search Tree) 一、二叉树 和链表一样,动态数据结构 具有唯一根节点 每个节点最...

    snowell 评论0 收藏0
  • PHP面试:常见查找算法一篇说透

    摘要:我们现在来看二分搜索算法的两种变形插值搜索和指数搜索。插值搜索是对二分搜索算法的改进,插值搜索可以基于搜索的值选择到达不同的位置。 预警 在本篇文章中,将为各位老铁介绍不同的搜索算法以及它们的复杂度。因为力求通俗易懂,所以篇幅可能较长,大伙可以先Mark下来,每天抽时间看一点理解一点。本文配套的Github Repo,欢迎各位老铁star,会一直更新的。 开篇 和排序类似,搜索或者叫做...

    付永刚 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<