AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题（中）

2024-05-28 33
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题

从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题(上）：https://developer.aliyun.com/article/1521938

2.4 二叉搜索树的删除

搜索二叉树删除的实现是有很有难度的。

没有孩子或者只有一个孩子，可以直接删除，孩子托管给父亲。

两个还是没办法给父亲，父亲养不了这么多孩子，但是可以找个人替代父亲养孩子。

当然，也不能随便找，找的人必须仍然维持搜索二叉树的性质，这是原则。


必须比左边的大，比右边的小。所以在家族中找是最合适的。


找左子树的最大值结点，或者右子树的最小值结点。


首先要查找元素是否在二叉搜索树中，如果不存在，则返回。


如果存在，那么删除的结点可能分为下面四种情况：


a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左孩子结点也有右孩子结点


看起来有待删除节点有 4 种情况，但实际上 a 和 b，或 a 和 c 可以合并。


因此，真正的删除过程如下：

我们还是定义一个 cur 变量，定义一个prev为空，后面是cur的父亲。

先找到要删除的结点，然后分下面三种情况

① 该结点无左孩子

如果要删除下面这颗二叉树的 10 节点和 4 节点：

当 cur 找到 10 结点后，如果左侧为空情况如下：


若该结点为 _root，直接让 _root 等于它的右孩子结点。

对于删除 10 结点：若 cur是右孩子，则令其父亲的右孩子指向其右孩子 （如图所示）

对于删除 4 结点：若 cur是左孩子，则令其父亲的左孩子指向其右孩子（如图所示）

最后删除 cur 结点

② 该结点无右孩子

如果要删除 14 结点，删除逻辑和删除左孩子是类似的：

③ 该结点有左右两个孩子

如果删除的结点有左右两个孩子，我们就在它的右子树中寻找中序的第一个结点。

即与右子树的最小值进行替换，当然也可以选择左子树的最大值进行替换。

例子：比如下面这颗子树，我们要删除 3 结点：

如果该结点有两个孩子，则采用如下替换法：

该结点和右子树的最小值或左子树的最大值进行值的替换，然后删除替换后的结点。

这里我们采用与右子树的最小值进行替换。

Erase代码：

  bool Erase(const K& key)
  {
    Node* cur = _root;
    Node* father = nullptr;
    while (cur) // 找到要删除的结点
    {
      if (key < cur->_key)
      {
        father = cur;
        cur = cur->_left;
      }
      else if (key > cur->_key)
      {
        father = cur;
        cur = cur->_right;
      }
      else // 找到后开始删除，分三种情况
      {
        if (cur->_left == nullptr) // ①该结点无左孩子
        {
          if (cur == _root)
          {
            _root = cur->_right;
          }
          else
          {
            if (cur == father->_left)
            {
              father->_left = cur->_right;
            }
            else //(cur == father->_right)
            {
              father->_right = cur->_right;
            }
          }
          delete cur;
          cur = nullptr;
        }
        else if (cur->_right == nullptr) //  ②该结点无右孩子
        {
          if (cur == _root)
          {
            _root = cur->_left;
          }
          else
          {
            if (cur == father->_left)
            {
              father->_left = cur->_left;
            }
            else //(cur == father->_left)
            {
              father->_right = cur->_left;
            }
          }
          delete cur;
          cur = nullptr;
        }
        else // ③有两个结点，替换法删除
        {
          Node* MinNode = cur->_right;
          Node* MinParNode = cur;
          while (MinNode->_left) // 找右子树的最小
          {
            MinParNode = MinNode;
            MinNode = MinNode->_left;
          }
          swap(cur->_key, MinNode->_key); // 找到后交换
 
          if(MinParNode->_right == MinNode) // 链接父亲结点，这步易漏
          {
            MinParNode->_right = MinNode->_right;
          }
          else
          {
            MinParNode->_left = MinNode->_right;
          }
          delete MinNode;
          MinNode = nullptr;
        }
        return true;
      }
    }
    return false;
  }

Test.c:

#include "BinarySearchTree.h"
 
void TestBSTree1() 
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.Insert(e);
  }
  t.InOrder();
 
  t.Erase(8);
  t.Erase(3);
  t.InOrder();
  for (const auto& e : arr)
  {
    t.Erase(e);
  }
  t.InOrder();
}
 
int main()
{
  TestBSTree1();
 
  return 0;
}

2.5 二叉搜索树的查找（递归）

二叉搜索树的递归查找很简单，因为外面不能传根，这里像InOrder一样封装起来

  bool FindR(const K& key)
  {
    return _FindR(_root, key);
  }
 
  bool _FindR(Node* root, const K& key)
  {
    if (root == nullptr)
    {
      return false;
    }
    if (key < root->_key)
    {
      _FindR(root->_left, key);
    }
    else if (key > root->_key)
    {
      _FindR(root->_right, key);
    }
    else
    {
      return true;
    }
  }

2.6 二叉搜索树的插入（递归）

二叉搜索树的递归插入如果这样写是插入不了的：

  bool InsertR(const K& key)
  {
    return _InsertR(_root, key);
  }
 
  bool _InsertR(Node* root, const K& key)
  {
    if (root == nullptr)
    {
      root = new Node(key);
      return true;
    }
 
    if (key < root->_key)
    {
      return _InsertR(root->_left, key);
    }
    else if (key > root->_key)
    {
      return _InsertR(root->_right, key);
    }
    else
    {
      return false;
    }
  }

因为递归到最后一步的时候，root只是一个局部变量，根本插入不了数据。

可以一步一步的把父亲传下来，但是这里有一个神之一手：加引用：

  bool InsertR(const K& key)
  {
    return _InsertR(_root, key);
  }
 
  bool _InsertR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
      root = new Node(key);
      return true;
    }
 
    if (key < root->_key)
    {
      return _InsertR(root->_left, key);
    }
    else if (key > root->_key)
    {
      return _InsertR(root->_right, key);
    }
    else
    {
      return false;
    }
  }

这里的引用最后一步才起作用，它是空，但它也是上一层传下来的别名。

给给root，就把父亲链接起来了，可以用二级指针，但是用引用很方便。

2.7 二叉搜索树的删除（递归）

这里的递归删除和上面的递归插入一样，也用到了非常巧妙的引用：

  bool EraseR(const K& key)
  {
    return _EraseR(_root, key);
  }
 
  bool _EraseR(Node*& root, const K& key)
  {
    if (root == nullptr)
    {
      return false;
    }
 
    if (root->_key < key)
    {
      return _EraseR(root->_right, key);
    }
    else if (root->_key > key)
    {
      return _EraseR(root->_left, key);
    }
    else // 找到要删除的结点，开始删除
    {
      Node* del = root;
      if (root->_left == nullptr) // 这里就体现了引用的神之一手，根本不用判断父亲
      {
        root = root->_right;
      }
      else if (root->_right == nullptr)
      {
        root = root->_left;
      }
      else // 找右树的最左节点替换删除
      {
        Node* MinNode = root->_right;
        while (MinNode->_left)
        {
          MinNode = MinNode->_left;
        }
        swap(root->_key, MinNode->_key);
        //return EraseR(key);  错的
        return _EraseR(root->_right, key);
      }
      delete del;
      return true;
    }
  }

Test.c:

#include "BinarySearchTree.h"
 
void TestBSTree1() 
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.Insert(e);
  }
  t.InOrder();
 
  t.Erase(8);
  t.Erase(3);
  t.InOrder();
  for (const auto& e : arr)
  {
    t.Erase(e);
  }
  t.InOrder();
}
 
void TestBSTree2()
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.InsertR(e);
  }
  t.InOrder();
 
  t.EraseR(8);
  t.EraseR(3);
  t.EraseR(2);
  t.InOrder();
  cout << t.Find(10) << endl;
  cout << t.Find(100) << endl;
  cout << t.FindR(10) << endl;
  cout << t.FindR(100) << endl;
  for (const auto& e : arr)
  {
    t.EraseR(e);
  }
  t.InOrder();
}
 
int main()
{
  TestBSTree2();
 
  return 0;
}

2.8 析构和拷贝构造和赋值

Test.c: 默认生成的：

#include "BinarySearchTree.h"
 
void TestBSTree3()
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.InsertR(e);
  }
  t.InOrder();
 
  BSTree<int> copy = t;
  copy.InOrder();
}
 
int main()
{
  TestBSTree3();
 
  return 0;
}

这里也是浅拷贝的问题，指向的是同一颗树，没崩只是没写析构，写下析构：

  ~BSTree()
  {
    _Destory(_root);
  }
 
protected:
  void _Destory(Node*& root) // 加引用下面的置空就起作用了
  {
    if (root == nullptr)
    {
      return;
    }
    _Destory(root->_left);
    _Destory(root->_right);
    delete root;
    root = nullptr;
  }

再运行刚才测试，程序崩溃：

这时我们就应该自己写拷贝构造了：

  BSTree(const BSTree<K>& t)
  {
    _root = _Copy(t._root);
  }
 
protected:
  Node* _Copy(Node* root)
  {
    if (root == nullptr)
    {
      return nullptr;
    }
 
    Node* CopyRoot = new Node(root->_key); // 中序递归链接左右子树
    CopyRoot->_left = _Copy(root->_left);
    CopyRoot->_right = _Copy(root->_right);
    return CopyRoot;
  }

这时运行就会报错：

错误(活动)    E0291    类 "BSTree" 不存在默认构造函数

这时写个默认的拷贝构造：

  BSTree(const BSTree<K>& t)
  {
    _root = _Copy(t._root);
  }
 
  //BSTree() // 这样写也行，但是下面是C++11的用法
  //{}
  BSTree() = default; // C++11的关键字，强制编译器生成默认的构造
 
protected:
  Node* _Copy(Node* root)
  {
    if (root == nullptr)
    {
      return nullptr;
    }
 
    Node* CopyRoot = new Node(root->_key); // 中序递归链接左右子树
    CopyRoot->_left = _Copy(root->_left);
    CopyRoot->_right = _Copy(root->_right);
    return CopyRoot;
  }

运行程序：

写了拷贝构造我们就可以直接用现代写法写一个赋值：

  BSTree<K> operator=(BSTree<K> t)
  {
    swap(_root, t._root);
    return *this;
  }

测试：

void TestBSTree3()
{
  BSTree<int> t;
  int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
  for (const auto& e : arr)
  {
    t.InsertR(e);
  }
  t.InOrder();
 
  BSTree<int> copy = t;
  copy.InOrder();
 
  BSTree<int> t2;
  t2.Insert(3);
  t2.Insert(5);
  t2.Insert(4);
  copy = t2;
  t2.InOrder();
  copy.InOrder();
}

259cca5b138444eb99e6c84712b7d6f1.png

从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题（下）：https://developer.aliyun.com/article/1521943?spm=a2c6h.13148508.setting.20.50c04f0eHmAr4x

文章标签：
C语言
关键词：
C++代码
C语言代码
C++ c语言
C语言二叉搜索树
C语言C++
GR鲸鱼
目录
相关文章
shliang0603
|
2月前
|
算法框架/工具 C++ Python
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角（Euler Angles）之间的相互转换，以及python和C++代码实现
根据相机旋转矩阵求解三个轴的旋转角/欧拉角/姿态角 或 旋转矩阵与欧拉角（Euler Angles）之间的相互转换，以及python和C++代码实现
shliang0603
110 0
小徐在进步
|
24天前
|
存储 算法 C语言
C语言手撕实战代码_二叉排序树(二叉搜索树)_构建_删除_插入操作详解
这份二叉排序树习题集涵盖了二叉搜索树（BST）的基本操作，包括构建、查找、删除等核心功能。通过多个具体示例，如构建BST、查找节点所在层数、删除特定节点及查找小于某个关键字的所有节点等，帮助读者深入理解二叉排序树的工作原理与应用技巧。此外，还介绍了如何将一棵二叉树分解为两棵满足特定条件的BST，以及删除所有关键字小于指定值的节点等高级操作。每个题目均配有详细解释与代码实现，便于学习与实践。
小徐在进步
14 2
游客qeoynko2nmbgk
|
4天前
|
C++
继续更新完善：C++ 结构体代码转MASM32代码
继续更新完善：C++ 结构体代码转MASM32代码
游客qeoynko2nmbgk
10 0
游客qeoynko2nmbgk
|
4天前
|
C++ Windows
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
HTML+JavaScript构建C++类代码一键转换MASM32代码平台
游客qeoynko2nmbgk
5 0
游客qeoynko2nmbgk
|
4天前
|
C++
2合1，整合C++类（Class）代码转换为MASM32代码的平台
2合1，整合C++类（Class）代码转换为MASM32代码的平台
游客qeoynko2nmbgk
5 0
yantuguiguziPGJ
|
4天前
|
前端开发 C++ Windows
C++生成QML代码与QML里面集成QWidget
这篇文章介绍了如何在C++中生成QML代码，以及如何在QML中集成QWidget，包括使用Qt Widgets嵌入到QML界面中的技术示例。
yantuguiguziPGJ
9 0
可能只会写BUG
|
29天前
|
编译器 C语言 C++
从C语言到C++
本文档详细介绍了C++相较于C语言的一些改进和新特性，包括类型检查、逻辑类型 `bool`、枚举类型、可赋值的表达式等。同时，文档还讲解了C++中的标准输入输出流 `cin` 和 `cout` 的使用方法及格式化输出技巧。此外，还介绍了函数重载、运算符重载、默认参数等高级特性，并探讨了引用的概念及其应用，包括常引用和引用的本质分析。以下是简要概述： 本文档适合有一定C语言基础的学习者深入了解C++的新特性及其应用。
可能只会写BUG
16 0
hylreg
|
2月前
|
C++
C++代码来计算一个点围绕另一个点旋转45度后的坐标
C++代码来计算一个点围绕另一个点旋转45度后的坐标
hylreg
47 0
developerguy
|
算法 C语言
二叉搜索树（Binary Search Tree）--C语言描述(转)
图解二叉搜索树概念 二叉树呢，其实就是链表的一个二维形式，而二叉搜索树，就是一种特殊的二叉树，这种二叉树有个特点：对任意节点而言，左孩子（当然了，存在的话）的值总是小于本身，而右孩子（存在的话）的值总是大于本身。
developerguy
1155 0
小徐在进步
|
21天前
|
存储 Serverless C语言
【C语言基础考研向】11 gets函数与puts函数及str系列字符串操作函数
本文介绍了C语言中的`gets`和`puts`函数，`gets`用于从标准输入读取字符串直至换行符，并自动添加字符串结束标志`\0`。`puts`则用于向标准输出打印字符串并自动换行。此外，文章还详细讲解了`str`系列字符串操作函数，包括统计字符串长度的`strlen`、复制字符串的`strcpy`、比较字符串的`strcmp`以及拼接字符串的`strcat`。通过示例代码展示了这些函数的具体应用及注意事项。
小徐在进步
47 7