C++红黑树插入后访问root->data触发访问违规问题求助

嘿，我一眼就看出你遇到的问题了——这是C++里传值参数机制导致的经典错误，你的红黑树根本没真正插入节点，所以root一直是NULL，访问root->data当然会触发内存访问违规啦。

问题根源拆解 #

咱们看你写的insertBST函数：

void insertBST(Node* node, int key) {
    if (node == NULL) {
        node = new Node(key); // 这里改的只是函数内部的局部变量副本！
    } else {
        if (key < node->data) {
            insertBST(node->left, key);
        } else {
            insertBST(node->right, key);
        }
    }
}

当你第一次调用insertBST(root, 10)时，root是NULL，进入第一个分支创建了新节点，但这个赋值只改变了函数里的node变量（它是root的副本），外面的tree.root还是NULL。递归调用时也一样：你传的是node->left的副本，修改副本完全不会影响原节点的left指针，新节点根本没被挂到树上！

修复方案：用指针引用传递参数 #

要让函数能直接修改外部的指针变量，你需要把参数改成指针的引用（Node*&）。这样函数内部对node的修改会直接作用于传入的指针本身，而不是它的副本。

修改后的完整代码：

#define BLACK 0
#define RED 1
using namespace std;
struct Node {
    Node* left, *right;
    int data;
    bool color;
    Node(int key) {
        data = key;
        left = right = NULL;
        color = RED;
    }
};
struct RBTree {
    Node* root;
    RBTree() {
        root = NULL;
    }
    // 参数改为Node*&，传递指针的引用
    void insertBST(Node*& node, int key) {
        if (node == NULL) {
            node = new Node(key); // 现在修改的是外部的指针（比如root或父节点的left/right）
        } else {
            if (key < node->data) {
                insertBST(node->left, key);
            } else {
                insertBST(node->right, key);
            }
        }
    }
    void insert(int key) {
        insertBST(root, key);
    }
};
int main() {
    RBTree tree;
    tree.insert(10);
    cout << tree.root->data; // 现在root指向有效节点，能正常访问了
    _getch();
    return 0;
}

额外提醒 #

• 指针引用（T*&）是C++里修改外部指针的常用手段，记住：如果要在函数里改变一个指针本身的指向，就得传引用或者指针的指针。
• 另外，你现在的代码只是完成了普通二叉搜索树的插入，红黑树还需要插入后的颜色调整和旋转操作来维持它的5条性质，后续别忘了补充这部分逻辑哦！

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