C语言中二级指针在红黑树中的应用：为何用struct Node** root？

在C语言里实现红黑树这类需要动态修改根节点的结构时，用Node** root本质是解决值传递带来的指针副本问题——先搞懂为什么Node* root满足不了需求，就能明白二级指针的必要性。

为什么struct Node* root不行？ #

C语言的函数参数是值传递，不管你传的是普通变量还是指针，函数拿到的都是原变量的副本。如果传Node* root，函数里的root是外部根指针的一个拷贝：

• 当你在函数里修改这个拷贝的指向（比如把它指向新的根节点），外部的原根指针完全不会变；
• 只有通过这个拷贝去修改指针指向的节点内容（比如root->data = 5），才会影响外部的节点，但这解决不了根节点本身被替换的场景。

红黑树的很多操作（比如插入第一个节点、删除最后一个节点、旋转调整后根节点变更）都需要修改根指针的指向，这时候用一级指针就做不到了。

这里二级指针Node** root的含义 #

Node** root是一个指向根节点指针的指针，它存储的是外部根指针的内存地址。通过这个二级指针，函数可以直接操作外部根指针本身：

• 解引用一次*root，就能拿到外部根指针的当前值（也就是根节点的地址）；
• 修改*root的内容，就是直接修改外部根指针的指向，外部代码能立刻看到这个变化。

示例对比 #

错误的一级指针实现（插入第一个节点时失效） #

#include <stdlib.h>
#include <stdio.h>

typedef struct Node {
    int data;
    char color;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;

// 用一级指针的插入函数
void insert_wrong(Node* root, int data) {
    if (root == NULL) {
        // 这里修改的是函数内的root副本，外部的根指针完全没变化
        root = malloc(sizeof(Node));
        root->data = data;
        root->color = 'B'; // 红黑树根节点初始为黑
        root->left = root->right = root->parent = NULL;
        return;
    }
    // 其他插入逻辑...
}

int main() {
    Node* root = NULL;
    insert_wrong(root, 10);
    // 这里root还是NULL，因为函数里修改的是副本
    if (root == NULL) {
        printf("根节点还是空的！\n");
    }
    return 0;
}

正确的二级指针实现 #

#include <stdlib.h>
#include <stdio.h>

typedef struct Node {
    int data;
    char color;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;

// 用二级指针的插入函数
void insert_correct(Node** root, int data) {
    if (*root == NULL) {
        // 直接修改外部根指针的指向
        *root = malloc(sizeof(Node));
        (*root)->data = data;
        (*root)->color = 'B';
        (*root)->left = (*root)->right = (*root)->parent = NULL;
        return;
    }
    // 其他插入逻辑（比如找到插入位置、调整红黑树性质）...
}

int main() {
    Node* root = NULL;
    insert_correct(&root, 10);
    if (root != NULL) {
        printf("根节点数据：%d，颜色：%c\n", root->data, root->color);
        // 输出：根节点数据：10，颜色：B
    }
    return 0;
}

除了插入操作，红黑树的旋转、删除等需要调整根节点的操作，都依赖二级指针来保证外部的根指针能同步更新，维持整个树结构的正确性。

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