【数据结构】二叉搜索树BST的实现(递归)

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉搜索树BST的实现(递归)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1.概念

2.图解:

3.元素插入操作

1.思路分析:

2.代码展示:

4.元素查找操作

1.前提根节点不为空

2.代码展示:

5.查找BST中的最大最小值

代码展示:

6.删除BST中的最大最小值

代码展示:

7.删除BST中的任意元素

代码展示:


 文章来源地址https://www.toymoban.com/news/detail-408345.html

1.概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

 

2.图解:

以下数组为例 :int [] arr = [5,3,4,1,7,8,6]

【数据结构】二叉搜索树BST的实现(递归)

 

 

3.元素插入操作

1.思路分析:

  1. 如果树为空树,即根 == null,直接插入
  2.  如果树不是空树,按照查找逻辑确定插入位置,插入新结点

2.代码展示:

    //在二分搜索树中添加元素
    public void add(int val){
        root = add(root,val);
    }

    private Node add(Node root, int val){
        if(root == null){
            Node node = new Node(val);
            userSize++;
            return node;
        }else if(val < root.val){
            root.left = add(root.left, val);
            return root;
        }else{
            root.right = add(root.right,val);
            return root;
        }
    }

4.元素查找操作

1.前提根节点不为空

  • root.val == key 返回true;
  • key > root.val  root= root.right;继续查找
  • key < root.val  root= root.left;继续查找

2.代码展示:

    //判断某元素是否在二叉搜索树中
    public boolean contains(int val){
        return contains(root,val);
    }

    private boolean contains(Node root, int val){
        if(root == null){
            return false;
        }else if (root.val == val){
            return true;
        }else if(val < root.val){
            return contains(root.left,val);
        }else {
            return contains(root.right,val);
        }
    }

5.查找BST中的最大最小值

  • 最大值一定在最右边,且右子树为空,顺着右子树往下寻找即可
  • 最小值一定在最左边,且左子树为空,顺着左子树往下寻找即可

代码展示:

    public int min(){
        return findMin(root).val;
    }
    public int max(){
        return findMax(root).val;
    }
    private Node findMin(Node root){
        if(root == null){
            throw new NoSuchElementException("没有元素哇~~");
        }
        Node x = root;
        while(x.left != null){
            x = x.left;
        }
        return x;
    }

    private Node findMax(Node root){
        if(this.root == null){
            throw new NoSuchElementException("没有元素哇~~");
        }
        Node x = this.root;
        while(x.right != null){
            x = x.right;
        }
        return x;
    }

6.删除BST中的最大最小值

  1. 删除最大值,找到最大值所在的节点,将其左子树记录下来,将最大值所在节点和其左子树置空,返回记录下来的左子树给其父节点
  2. 删除最小值,找到最小值所在的节点,将其右子树记录下来,将最小值所在节点和其右子树置空,返回记录下来的右子树给其父节点

代码展示:

    //删除最大值
    public void removeMax(){
        removeMax(root);
    }

    private Node removeMax(Node root){
        if(root == null){
            return null;
        }
        if(root.right == null){
            Node left = root.left;
            root.right = root = null;
            userSize--;
            return left;
        }
        root.right = removeMax(root.right);
        return root;
    }

    //删除最小值
    public void removeMin(){
        removeMin(root);
    }

    private Node removeMin(Node root) {
        if(root == null){
            return null;
        }
        if(root.left == null){
            Node right = root.right;
            root.left = root = null;
            userSize--;
            return right;
        }
        root.left = removeMin(root.left);

        return root;
    }

7.删除BST中的任意元素

  • 先在二叉搜索树中寻找需要被删除的元素,不存在返回null
  • 判断被删除的元素是否左右子树有为空的情况,有则按照删除最大最小值的操作来删除当前元素
  • 若左右子树都不为空,则需要在BST中寻找一个新节点,将其右边连接删除新节点后的右子树,
  • 左边链接左子树,最后将root,root.left.root.right全部置空,返回新节点即可

代码展示:

    //在二叉搜索树中删除元素
    public void remove(int val){
        root = remove(root,val);
    }

    private Node remove(Node root, int val) {
        if(root == null){
            return root;
        }else if(val < root.val){
            root.left =  remove(root.left,val);
            return root;
        }else if(val > root.val){
            root.right = remove(root.right,val);
            return root;
        }else {
            //当前节点就是被删除的节点
            if(root.right == null){
                //删除最小值的操作一样
                Node left = root.left;
                root.left = root = null;
                userSize--;
                return left;
            }else if(root.left == null){
                Node right = root.right;
                root.right = root = null;
                userSize--;
                return right;
            }else {
                //左右两边都有子树
                Node prev = findMin(root.right);
                prev.right = removeMin(root.right);
                prev.left = root.left;
                root.right = root.left = root = null;
                return prev;
            }
        }
    }

 

 

 

到了这里,关于【数据结构】二叉搜索树BST的实现(递归)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:非完全二叉树(递归实现)

      非完全二叉树是指在二叉树中,除了叶子节点(无子节点)外,其他节点的子节点个数可以不同,即不一定是每个节点都有两个子节点,有右孩子时也不一定有左孩子。 tree.h tree.c main.c 结果

    2024年01月21日
    浏览(49)
  • 【数据结构】——二叉树的递归实现,看完不再害怕递归

     创作不易,感谢三连加支持?! 递归无非就是相信它,只有你相信它,你才能写好递归!为什么?请往下看 在进入二叉树的实现之前,我们得先理解一遍递归,可能很多人对于递归感到恐惧或者害怕, 有时候还不敢面对, 其实大可不必,  递归其实分为两个东西: 1.递归

    2024年04月09日
    浏览(37)
  • 数据结构:二叉树的递归实现(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 本篇博客主要讲解二叉树的相关操作如下: 树是一种非线性结构,它是由n个有限节点组成的一个有层次关系的集合。 图中 A节点 没有前驱节点,被称为根节点 除根节点外,其余节点被分成两个无不相交的集合T1(

    2024年02月12日
    浏览(33)
  • 数据结构07:查找[C++][朴素二叉排序树BST]

    图源:文心一言 考研笔记整理 8k+ 字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_1 二叉排序树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月10日
    浏览(39)
  • DSt:数据结构的最强学习路线之数据结构知识讲解与刷题平台、刷题集合、问题为导向的十大类刷题算法(数组和字符串、栈和队列、二叉树、堆实现、图、哈希表、排序和搜索、动态规划/回溯法/递归/贪心/分治)总

    Algorithm:【算法进阶之路】之算法面试刷题集合—数据结构知识和算法刷题及其平台、问题为导向的十大类刷题算法(数组和字符串、链表、栈和队列、二叉树、堆、图、哈希表、排序和搜索、回溯算法、枚举/递归/分治/动态规划/贪心算法)总结 目录 相关文章

    2024年02月08日
    浏览(52)
  • 数据结构:二叉树的基本操作(用递归实现)

             本文将通过完成以下内容来展示二叉树的基本操作,代码解释标注全面而且清晰,代码书写也十分规范,适合初学者进行学习,本篇文章算是本人的一些学习记录分享,希望对有需要的小伙伴提供一些帮助~ 本文的内容为: 用递归的方法实现以下算法: 1.以二叉

    2024年02月06日
    浏览(49)
  • Java 数据结构篇-二叉树的深度优先遍历(实现:递归方式、非递归方式)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 二叉树的说明         1.1 二叉树的实现         2.0 二叉树的优先遍历说明         3.0 用递归方式实现二叉树遍历         3.1 用递归方式实现遍历 - 前序遍历         3.2 用递归

    2024年02月05日
    浏览(48)
  • 【数据结构|二叉树遍历】递归与非递归实现前序遍历、中序遍历、后序遍历

    递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。 二叉树图 定义 前序遍历(Preorder Traversal): 前序遍历的顺序是先访问根节点,然后按照先左后右的顺序访问子节点。对于上面的二叉树,前序遍历的结果是:4 - 2 - 1 - 3 - 6 - 5 - 7。 中序遍历(Inorder Traversal): 中

    2024年02月14日
    浏览(43)
  • 【数据结构】 二叉搜索树的实现

    二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 比如以下就为一个人二叉搜

    2024年02月09日
    浏览(36)
  • 【数据结构】搜索二叉树(C++实现)

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 上一篇博客:【C++】C++模板进阶 —— 非类型模板参数、模板的特化以及模板的分离编译 二叉搜索树又称二叉排序树,它或者是一棵空

    2024年02月07日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包