数据结构之二叉搜索树

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

二叉搜索树

满足条件:

1.对于根节点:左子树中所有节点的值小于右子树中所有节点的值

2.任意节点的左右子树也是二叉搜索树,同样满足条件1

二叉搜索树的常用操作

我们将二叉搜索树封装为一个类 BinarySearchTree ,并声明一个成员变量 root ,指向树的根节点

查找节点

给定目标值target,我们可以根据二叉搜索树的性质来查找,声明一个节点cur从根节点开始遍历

  • cur.val<target说明targetcur的右子树,执行cur=cur.right
  • cur.val>target说明targetcur的左子树,执行cur=cur.left
  • cur.val=target,返回该节点,跳出循环
/* 查找节点 */
TreeNode *search(int num) {
    TreeNode *cur = root;
    // 循环查找,越过叶节点后跳出
    while (cur != nullptr) {
        // 目标节点在 cur 的右子树中
        if (cur->val < num)
            cur = cur->right;
        // 目标节点在 cur 的左子树中
        else if (cur->val > num)
            cur = cur->left;
        // 找到目标节点,跳出循环
        else
            break;
    }
    // 返回目标节点
    return cur;
}

插入节点

  • 查找插入位置:从根节点出发,根据当前节点值和 num 的大小关系循环向下搜索,直到越过叶节点(遍历至 None )时跳出循环

  • 在该位置插入节点:初始化节点 num ,将该节点置于 None 的位置。

注意:

二叉搜索树中不允许有重复的元素,否则就违反了二叉搜索树的定义,若待插入的节点在二叉搜索树中,则不执行任何操作,直接返回

为了实现插入节点,我们需要借助节点 pre 保存上一轮循环的节点。这样在遍历至 None 时,我们可以获取到其父节点,从而完成节点插入操作

/* 插入节点 */
void insert(int num) {
    // 若树为空,则初始化根节点
    if (root == nullptr) {
        root = new TreeNode(num);
        return;
    }
    TreeNode *cur = root, *pre = nullptr;
    // 循环查找,越过叶节点后跳出
    while (cur != nullptr) {
        // 找到重复节点,直接返回
        if (cur->val == num)
            return;
        pre = cur;
        // 插入位置在 cur 的右子树中
        if (cur->val < num)
            cur = cur->right;
        // 插入位置在 cur 的左子树中
        else
            cur = cur->left;
    }
    // 插入节点
    TreeNode *node = new TreeNode(num);
    if (pre->val < num)
        pre->right = node;
    else
        pre->left = node;
}

删除节点

二叉搜索树的删除分为三种情况文章来源地址https://www.toymoban.com/news/detail-807092.html

  • 当待删除节点的度为0时,可以直接删除这个节点。
  • 当待删除节点的度为1时,我们将子节点替换待删除的节点即可
  • 当待删除节点的度为2时,我们无法删除这个节点,而是需要一个节点替换这个节点,因为要维持搜索二叉树的性质,所以这个待删除节点的值可以是右子树的最小节点或者左子树的最大节点
/* 删除节点 */
void remove(int num) {
    // 若树为空,直接提前返回
    if (root == nullptr)
        return;
    TreeNode *cur = root, *pre = nullptr;
    // 循环查找,越过叶节点后跳出
    while (cur != nullptr) {
        // 找到待删除节点,跳出循环
        if (cur->val == num)
            break;
        pre = cur;
        // 待删除节点在 cur 的右子树中
        if (cur->val < num)
            cur = cur->right;
        // 待删除节点在 cur 的左子树中
        else
            cur = cur->left;
    }
    // 若无待删除节点,则直接返回
    if (cur == nullptr)
        return;
    // 子节点数量 = 0 or 1
    if (cur->left == nullptr || cur->right == nullptr) {
        // 当子节点数量 = 0 / 1 时, child = nullptr / 该子节点
        TreeNode *child = cur->left != nullptr ? cur->left : cur->right;
        // 删除节点 cur
        if (cur != root) {
            if (pre->left == cur)
                pre->left = child;
            else
                pre->right = child;
        } else {
            // 若删除节点为根节点,则重新指定根节点
            root = child;
        }
        // 释放内存
        delete cur;
    }
    // 子节点数量 = 2
    else {
        // 获取中序遍历中 cur 的下一个节点
        TreeNode *tmp = cur->right;
        while (tmp->left != nullptr) {
            tmp = tmp->left;
        }
        int tmpVal = tmp->val;
        // 递归删除节点 tmp
        remove(tmp->val);
        // 用 tmp 覆盖 cur
        cur->val = tmpVal;
    }
}

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

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

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

相关文章

  • 数据结构之二叉树(Java)

    在这里先说明一下,结点和节点其实一样的,无须关注这个。 1. 概念:树是一种非线性的数据结构,它是由n个有限节点组成一个具有层次关系的集合。 如上图所示,把此种数据结构称作树是因为它看起来像一个倒挂的树。  2. 特点 有一个特殊的节点,称为根节点,它是唯一

    2024年02月07日
    浏览(39)
  • 数据结构之二叉树(详细版)

            二叉树作为数据结构的一种,尤为重要,下面是对二叉树的详细讲解。想要了解二叉树,首先要了解 二叉树的基本概念,以及创建二叉树的结构,再深层点,遍历二叉树的前序中序和后续,其次是层序,后面将会讲解如何计算二叉树的高和叶结点 等等。        

    2024年02月03日
    浏览(46)
  • 数据结构之二叉树和平衡二叉树

    1、二叉树: 2、平衡二叉树:

    2024年04月17日
    浏览(44)
  • 数据结构之二叉树的性质与存储结构

      数据结构是程序设计的重要基础,它所讨论的内容和技术对从事软件项目的开发有重要作用。学习数据结构要达到的目标是学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作方法,为提高利用

    2024年01月21日
    浏览(49)
  • 数据结构之二叉树的实现

    目录 前言 1. 二叉树的遍历 1.1二叉树的前、中、后序遍历 1.2 层序遍历 2.二叉树的实现 2.1 二叉树的结构 2.2构建二叉树  2.2 前序遍历的实现 2.3 中序遍历的实现 2.4 后序遍历的实现 2.5 计算树的节点个数 2.6 计算树的深度 2.7 计算叶子节点个数 2.8 计算树第k层的节点数 2.9 以内容

    2023年04月10日
    浏览(49)
  • 《数据结构与算法》之二叉树(补充树)

    二叉搜索树,也称二叉排序树或二叉查找树 二叉搜索树:一棵二叉树,可以为空,如果不为空,应该满足以下性质: 非空左子树的所有结点小于其根结点的键值 非空右子树的所有结点大于其根结点的键值 左右子树都是二叉搜索树 对于二叉树的查找,其实沿用的是分治法的

    2024年02月08日
    浏览(49)
  • 数据结构奇妙旅程之二叉树初阶

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年01月19日
    浏览(64)
  • 数据结构之二叉树的数组表示

    若某节点的索引为 i ,则该节点的左子节点的索引为 2i+1 ,右子节点的索引为 2i+2 给定某节点,获取它的左右字节点,父节点 获取前序遍历,中序遍历,后序遍历,层序遍历

    2024年01月18日
    浏览(51)
  • 数据结构奇妙旅程之二叉平衡树

    ꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶ 个人主页:xiaoxieʕ̯

    2024年03月11日
    浏览(59)
  • 【数据结构之二叉树的构建和遍历】

    前言: 前篇学习了 数据结构之树和二叉树的基本概念知识,那么这篇继续完善二叉树的相关知识并完成实现二叉树的构建和遍历的内容。 / 知识点汇总 / 因为前篇已经非常详细的单独学习了数和二叉树的基本知识概念,那么这里就简单回顾一下即可。 概念 : 二叉树(Bina

    2024年02月21日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包