C语言中void函数修改BST指针失效问题求助

我尝试实现一个二叉搜索树（BST）的查找函数，功能是查找指定int类型的key，找到后将found指针指向该节点，同时找到该节点的前驱（pre）和后继（suc）并赋值给对应指针。

实现的函数代码 #

void findPreSuc(struct node *root, struct node* found, struct node* pre, struct node* suc, int key)
{
    // Base case
    if (root == NULL){  
        return ;
    }
    // If key is present at root
    if (root->data == key)
    {
        found=root;
        printf("\n%d",found->data); //test if root node gets passed to found
        // the maximum value in left subtree is predecessor
        if (root->left_child != NULL)
        {
            struct node* tmp = root->left_child;
            while (tmp->right_child){
                tmp = tmp->right_child;
                pre = tmp ;
            }
        }
 
        // the minimum value in right subtree is successor
        if (root->right_child != NULL)
        {
            struct node* tmp = root->right_child;
            while (tmp->left_child){
                tmp = tmp->left_child;
                suc = tmp ;
            }
        }
        return ;
    }
 
    // If key is smaller than root's key, go to left subtree
    if (root->data > key)
    {
        suc = root ;
        findPreSuc(root->left_child, found, pre, suc, key) ;
    }
    else // go to right subtree
    {
        pre = root ;
        findPreSuc(root->right_child, found, pre, suc, key) ;
    }
}

测试的main函数代码 #

int main()
{
    struct node *root=NULL;
    struct node *suc=NULL;
    struct node* pre=NULL;  
    struct node* found=NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
    findPreSuc(root, found, pre, suc, 60);
    if (found==NULL)
    {
        printf("\ndidnt work");
    }    
    return 0;
}

运行输出 #

60
didnt work

可以看到函数执行时确实修改了内部的found指针（打印出了60），但函数返回后main中的found、pre、suc又变回NULL，导致输出“didnt work”。

问题原因 #

C语言中参数传递采用值传递：当你把指针作为参数传入函数时，函数会创建一个该指针的副本。你在函数内部修改的只是这个副本的指向，并不会影响main函数中原来的指针变量。比如found=root;这行代码，只是修改了函数内部found副本的值，main里的found还是初始的NULL。

解决方案 #

将found、pre、suc的参数类型改为指针的指针（struct node**），这样函数就能通过指针的指针修改原指针的指向。

修改后的函数代码 #

void findPreSuc(struct node *root, struct node** found, struct node** pre, struct node** suc, int key)
{
    // Base case
    if (root == NULL){  
        return ;
    }
    // If key is present at root
    if (root->data == key)
    {
        *found = root;
        printf("\n%d", (*found)->data); //test if root node gets passed to found
        // the maximum value in left subtree is predecessor
        if (root->left_child != NULL)
        {
            struct node* tmp = root->left_child;
            while (tmp->right_child){
                tmp = tmp->right_child;
            }
            *pre = tmp ;
        }
 
        // the minimum value in right subtree is successor
        if (root->right_child != NULL)
        {
            struct node* tmp = root->right_child;
            while (tmp->left_child){
                tmp = tmp->left_child;
            }
            *suc = tmp ;
        }
        return ;
    }
 
    // If key is smaller than root's key, go to left subtree
    if (root->data > key)
    {
        *suc = root ;
        findPreSuc(root->left_child, found, pre, suc, key) ;
    }
    else // go to right subtree
    {
        *pre = root ;
        findPreSuc(root->right_child, found, pre, suc, key) ;
    }
}

修改后的main函数调用 #

在调用findPreSuc时，需要传入指针的地址：

findPreSuc(root, &found, &pre, &suc, 60);

这样修改后，函数内部对*found、*pre、*suc的赋值会直接作用于main中的原指针变量，函数返回后这些指针就能保留正确的指向。

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