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

简介: 从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

目录
相关文章
|
8天前
|
存储 C++
【C++】二叉树进阶之二叉搜索树(下)
【C++】二叉树进阶之二叉搜索树(下)
12 4
|
8天前
|
Java 编译器 C++
【C++】二叉树进阶之二叉搜索树(上)
【C++】二叉树进阶之二叉搜索树(上)
14 3
|
14天前
|
算法 测试技术 C++
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
【C++高阶】掌握AVL树:构建与维护平衡二叉搜索树的艺术
14 2
|
15天前
|
C++ 开发者
C++一分钟之-概念(concepts):C++20的类型约束
【7月更文挑战第4天】C++20引入了Concepts,提升模板编程的类型约束和可读性。概念定义了模板参数需遵循的规则。常见问题包括过度约束、约束不完整和重载决议复杂性。避免问题的关键在于适度约束、全面覆盖约束条件和理解重载决议。示例展示了如何用Concepts限制模板函数接受的类型。概念将增强模板的安全性和灵活性,但需谨慎使用以防止错误。随着C++的发展,Concepts将成为必备工具。
33 2
|
24天前
|
存储 C++
【C++航海王:追寻罗杰的编程之路】一篇文章带你了解二叉搜索树
【C++航海王:追寻罗杰的编程之路】一篇文章带你了解二叉搜索树
14 1
|
13天前
|
C++ 开发者
C++一分钟之-概念(concepts):C++20的类型约束
【7月更文挑战第6天】C++20引入了Concepts,提升模板编程的精确性和可读性。概念允许设定模板参数的编译时约束。常见问题包括过度约束、不完整约束及重载决议复杂性。要避免这些问题,需适度约束、全面覆盖约束条件并理解重载决议。示例展示了如何定义和使用`Incrementable`概念约束函数模板。概念是C++模板编程的强大力量,但也需谨慎使用以优化效率和代码质量。
38 0
|
14天前
|
编译器 程序员 C++
【C++高阶】掌握C++多态:探索代码的动态之美
【C++高阶】掌握C++多态:探索代码的动态之美
18 0
|
19天前
|
算法 程序员 编译器
C++一分钟之概念(concepts):C++20的类型约束
【6月更文挑战第30天】C++20的Concepts革新了模板编程,允许更清晰地表达类型要求,提升代码可读性和编译错误反馈。本文探讨Concepts基础、应用场景、易错点及避免策略,展示如何通过概念定义如Iterable、Addable,创建更健壮的泛型代码,强调了理解和利用编译器错误信息的重要性,以及概念与类型别名的区别。Concepts现已成为现代C++程序员的关键技能。
18 0
|
22天前
|
C语言
C语言实现猜数字游戏:代码详解与函数解析
C语言实现猜数字游戏:代码详解与函数解析
13 0
|
22天前
|
机器学习/深度学习 C语言 Windows
程序与技术分享:C语言学生宿舍管理系统代码(可运行)
程序与技术分享:C语言学生宿舍管理系统代码(可运行)
15 0