从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();
}

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

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

2.4 二叉搜索树的删除

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

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

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

2.8 析构和拷贝构造和赋值

热门文章

最新文章

相关课程

相关电子书