在 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
