在 C++ 中从二叉搜索树中删除节点
Jinku Hu
2023年10月12日
本文将讲解如何在二叉搜索树数据结构 C++ 中实现一个删除节点的函数。
C++ 中删除二叉搜索树中的节点
二叉搜索树是一种二叉树，它在每个节点中存储一个键值。该键用于构建有序树，以便每个节点的键大于其左子树中的所有键，并小于其右子树中的所有键。
每个节点通常包含两个指向 left 和 right 节点的指针，但我们还添加了另一个指针来表示父节点，因为它更容易实现 remove 成员函数。
请注意，以下二叉搜索树实现仅包含最少的成员函数来演示节点删除操作。
BinSearchTree 类只能将 int 类型存储为键值。除了 remove 之外的大多数函数都使用递归，因此我们提供了相应的在内部调用的 private 成员函数。通常，从树中删除节点是比插入和搜索更复杂的操作，因为它涉及多种场景。
第一个也是最简单的场景是我们需要删除一个没有子节点的节点（因此称为叶子节点）。叶子节点可以被解除分配并将 nullptr 分配给其父节点的相应指针。
第二种情况是删除只有一个孩子的节点。后者可以通过将目标的父级连接到其子级来解决，然后我们可以释放关联的内存。
#include <iostream>
using std::cerr;
using std::cout;
using std::endl;
using std::string;
struct BSTreeNode {
int key{};
BSTreeNode *parent{};
BSTreeNode *left{};
BSTreeNode *right{};
} typedef BSTreeNode;
class BinSearchTree {
public:
BinSearchTree() {
root = nullptr;
size = 0;
};
BinSearchTree(std::initializer_list<int> list);
void insert(int k);
BSTreeNode *find(int k);
int remove(int k);
void print();
size_t getSize() const;
~BinSearchTree();
private:
BSTreeNode *root;
size_t size;
void freeNodes(BSTreeNode *&rnode);
void printTree(BSTreeNode *node);
void insertNode(BSTreeNode *&rnode, int k, BSTreeNode *pnode);
BSTreeNode **findNode(BSTreeNode *&rnode, int k);
};
BinSearchTree::BinSearchTree(std::initializer_list<int> list) {
root = nullptr;
size = 0;
for (const auto &item : list) {
insertNode(root, item, nullptr);
}
}
BinSearchTree::~BinSearchTree() { freeNodes(root); }
void BinSearchTree::freeNodes(BSTreeNode *&rnode) {
if (rnode != nullptr) {
freeNodes(rnode->left);
freeNodes(rnode->right);
delete rnode;
}
}
BSTreeNode *BinSearchTree::find(const int k) { return *findNode(root, k); }
BSTreeNode **BinSearchTree::findNode(BSTreeNode *&rnode, const int k) {
if (rnode == nullptr) return nullptr;
if (k == rnode->key) return &rnode;
if (k < rnode->key)
return findNode(rnode->left, k);
else
return findNode(rnode->right, k);
}
void BinSearchTree::print() {
if (size > 0)
printTree(root);
else
cout << "tree is empty!" << endl;
}
void BinSearchTree::printTree(BSTreeNode *rnode) {
if (rnode != nullptr) {
printTree(rnode->left);
cout << rnode->key << "; ";
printTree(rnode->right);
}
}
void BinSearchTree::insert(const int k) { insertNode(root, k, nullptr); }
void BinSearchTree::insertNode(BSTreeNode *&rnode, const int k,
BSTreeNode *pnode) {
if (rnode == nullptr) {
rnode = new BSTreeNode;
rnode->key = k;
rnode->parent = pnode;
rnode->left = nullptr;
rnode->right = nullptr;
size++;
} else {
if (k < rnode->key)
insertNode(rnode->left, k, rnode);
else if (k == rnode->key)
return;
else
insertNode(rnode->right, k, rnode);
}
}
size_t BinSearchTree::getSize() const { return size; }
int BinSearchTree::remove(const int k) {
auto ret = findNode(root, k);
if (ret == nullptr) return -1;
if (size == 1) {
auto tmp = root;
root = nullptr;
delete tmp;
size--;
return 0;
}
if ((*ret)->left == nullptr && (*ret)->right == nullptr) {
auto tmp = *ret;
if ((*ret)->key < (*ret)->parent->key)
(*ret)->parent->left = nullptr;
else
(*ret)->parent->right = nullptr;
delete tmp;
size--;
return 0;
}
if ((*ret)->left != nullptr && (*ret)->right != nullptr) {
auto leftmost = (*ret)->right;
while (leftmost && leftmost->left != nullptr) leftmost = leftmost->left;
(*ret)->key = leftmost->key;
if (leftmost->right != nullptr) {
leftmost->right->parent = leftmost->parent;
auto tmp = leftmost->right;
*leftmost = *leftmost->right;
leftmost->parent->left = leftmost;
delete tmp;
} else {
leftmost->parent->right = nullptr;
delete leftmost;
}
size--;
return 0;
} else {
if ((*ret)->left != nullptr) {
auto tmp = *ret;
*ret = (*ret)->left;
(*ret)->parent = tmp->parent;
delete tmp;
} else {
auto tmp = *ret;
*ret = (*ret)->right;
(*ret)->parent = tmp->parent;
delete tmp;
}
size--;
return 0;
}
}
int main() {
BinSearchTree bst = {6, 5, 11, 3, 2, 10, 12, 4, 9};
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
bst.insert(7);
bst.insert(8);
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
bst.remove(6);
bst.remove(2);
bst.remove(12);
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
return EXIT_SUCCESS;
}
size of bst = 9
2; 3; 4; 5; 6; 9; 10; 11; 12;
size of bst = 11
2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12;
size of bst = 8
3; 4; 5; 7; 8; 9; 10; 11;
最复杂的场景是目标节点有两个孩子。在这种情况下，我们需要正确连接节点并保留为二叉搜索树结构指定的元素顺序。我们需要用最小的 key 和目标右子树的一部分替换目标节点。
在最左边的地方找到具有最小键的节点。因此我们应该遍历右子树，直到到达这个节点。一旦找到节点，我们可以将其键分配给目标节点，然后尝试删除前一个节点，就好像它是一个具有单个子节点的节点。后者是由这个节点是给定子树中最左边的一个事实所暗示的。因此，它只能有一个 right 子节点或根本没有子节点。
这三个场景是在 remove 成员函数中单独的 if...else 块中实现的，但我们还包含额外的代码来检查某些极端情况，例如在树中找不到元素或删除最后一个节点时。请注意，remove 函数也可以递归方式实现。
作者： Jinku Hu
