C++ BST删除操作详解（手把手教你实现二叉搜索树节点删除）

BST删除操作的三种情况

删除一个节点比插入复杂，因为要维持BST的结构不变。根据被删除节点的子节点数量，可分为以下三种情况：

1. 情况一：被删除节点是叶子节点（无左右子树）——直接删除即可。
2. 情况二：被删除节点只有一个子节点——用其子节点替代该节点。
3. 情况三：被删除节点有两个子节点——需找到中序后继（右子树中的最小值）或中序前驱（左子树中的最大值），用其值替换当前节点，再删除那个后继/前驱节点。

C++实现BST删除操作

下面我们用C++完整实现一个BST，并重点编写删除函数。代码包含注释，便于理解。

#include <iostream>using namespace std;struct Node {    int data;    Node* left;    Node* right;    Node(int val) : data(val), left(nullptr), right(nullptr) {}};class BST {private:    Node* root;    // 辅助函数：递归插入    Node* insertHelper(Node* node, int val) {        if (!node) return new Node(val);        if (val < node->data)            node->left = insertHelper(node->left, val);        else if (val > node->data)            node->right = insertHelper(node->right, val);        return node;    }    // 查找最小值节点（用于情况三）    Node* findMin(Node* node) {        while (node && node->left)            node = node->left;        return node;    }    // 删除操作的核心递归函数    Node* deleteNodeHelper(Node* node, int key) {        if (!node) return nullptr; // 未找到        if (key < node->data) {            node->left = deleteNodeHelper(node->left, key);        } else if (key > node->data) {            node->right = deleteNodeHelper(node->right, key);        } else {            // 找到要删除的节点            // 情况一：叶子节点 或 只有右子树            if (!node->left) {                Node* temp = node->right;                delete node;                return temp;            }            // 情况二：只有左子树            else if (!node->right) {                Node* temp = node->left;                delete node;                return temp;            }            // 情况三：左右子树都存在            Node* minRight = findMin(node->right);            node->data = minRight->data; // 用后继值覆盖            node->right = deleteNodeHelper(node->right, minRight->data); // 删除后继        }        return node;    }    void inorderHelper(Node* node) {        if (!node) return;        inorderHelper(node->left);        cout << node->data << " ";        inorderHelper(node->right);    }public:    BST() : root(nullptr) {}    void insert(int val) {        root = insertHelper(root, val);    }    void remove(int key) {        root = deleteNodeHelper(root, key);    }    void inorder() {        inorderHelper(root);        cout << endl;    }};int main() {    BST tree;    tree.insert(50);    tree.insert(30);    tree.insert(70);    tree.insert(20);    tree.insert(40);    tree.insert(60);    tree.insert(80);    cout << "初始中序遍历: ";    tree.inorder(); // 输出: 20 30 40 50 60 70 80    tree.remove(20); // 删除叶子节点    cout << "删除20后: ";    tree.inorder();    tree.remove(30); // 删除有一个子节点的节点    cout << "删除30后: ";    tree.inorder();    tree.remove(50); // 删除有两个子节点的根节点    cout << "删除50后: ";    tree.inorder();    return 0;}

关键点解析

- 在C++ BST删除操作中，使用递归方式处理更清晰。

- 情况三中我们选择中序后继（右子树最小值）来替换，也可以选中序前驱（左子树最大值）。

- 注意内存释放：使用 delete 防止内存泄漏。

总结

通过本教程，你已经掌握了如何在C++中实现二叉搜索树删除节点的功能。无论是面试还是实际开发，这都是数据结构中的核心技能。希望这篇数据结构BST删除教程对你有所帮助！

记住：多动手写代码，才能真正掌握BST删除逻辑！