从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
