寻求C++代码帮助：替换BST节点键值并修复BST属性

直接替换节点键值容易破坏BST的左小右大特性，更可靠的方式是先删除存储key1的节点，再将key2插入到树中——这两个都是BST的标准操作，能保证最终树的结构完全符合BST属性。

实现步骤 #

• 定义二叉搜索树的节点结构
• 实现BST的查找、删除、插入核心函数
• 封装替换操作：先删除key1对应的节点，再插入key2

C++代码实现 #

#include <iostream>

// 定义BST节点结构
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 查找目标节点，同时记录其父节点
TreeNode* findNode(TreeNode* root, int key, TreeNode*& parent) {
    parent = nullptr;
    TreeNode* curr = root;
    while (curr != nullptr && curr->val != key) {
        parent = curr;
        curr = key < curr->val ? curr->left : curr->right;
    }
    return curr;
}

// 找到子树中最小的节点（用于删除双子节点的场景）
TreeNode* findMinNode(TreeNode* node) {
    while (node->left != nullptr) {
        node = node->left;
    }
    return node;
}

// 删除BST中的指定节点
TreeNode* deleteNode(TreeNode* root, int key) {
    TreeNode* parent = nullptr;
    TreeNode* target = findNode(root, key, parent);
    if (target == nullptr) return root; // 未找到目标节点，直接返回原树

    // 场景1：目标节点是叶子节点
    if (!target->left && !target->right) {
        if (target == root) {
            delete target;
            return nullptr;
        }
        (parent->left == target) ? parent->left = nullptr : parent->right = nullptr;
        delete target;
    }
    // 场景2：目标节点有两个子节点
    else if (target->left && target->right) {
        TreeNode* minRight = findMinNode(target->right);
        int minVal = minRight->val;
        root = deleteNode(root, minVal);
        target->val = minVal;
    }
    // 场景3：目标节点只有一个子节点
    else {
        TreeNode* child = target->left ? target->left : target->right;
        if (target == root) {
            delete target;
            return child;
        }
        (parent->left == target) ? parent->left = child : parent->right = child;
        delete target;
    }
    return root;
}

// 插入节点到BST
TreeNode* insertNode(TreeNode* root, int key) {
    if (!root) return new TreeNode(key);
    if (key < root->val) {
        root->left = insertNode(root->left, key);
    } else if (key > root->val) {
        root->right = insertNode(root->right, key);
    }
    return root; // 若key已存在，不做任何操作
}

// 核心替换操作：删除key1，插入key2
TreeNode* replaceKey(TreeNode* root, int key1, int key2) {
    root = deleteNode(root, key1);
    root = insertNode(root, key2);
    return root;
}

// 中序遍历验证BST（结果应为升序）
void inorderTraversal(TreeNode* root) {
    if (!root) return;
    inorderTraversal(root->left);
    std::cout << root->val << " ";
    inorderTraversal(root->right);
}

// 测试示例
int main() {
    // 构建示例BST:
    //       5
    //      / \
    //     3   7
    //    / \ / \
    //   2  4 6  8
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(8);

    std::cout << "替换前中序遍历: ";
    inorderTraversal(root);
    std::cout << "\n";

    // 替换key=3为key=9
    root = replaceKey(root, 3, 9);

    std::cout << "替换后中序遍历: ";
    inorderTraversal(root);
    std::cout << "\n";

    // 实际使用时需手动释放内存，避免泄漏
    return 0;
}

代码说明 #

• findNode：定位目标节点并记录其父节点，为删除操作提供必要信息
• deleteNode：覆盖BST删除的三种典型场景，确保删除后树的结构依然合法
• insertNode：严格遵循BST插入规则，自动维护左小右大的特性
• replaceKey：封装核心逻辑，通过先删后插的方式实现键值替换，同时保证BST属性不被破坏
• 中序遍历用于验证结果，BST的中序遍历结果必然是升序序列

内容的提问来源于stack exchange，提问作者Codeit