c - 为什么指针在删除函数调用后不将 BST 的节点归零？

Question

BST 有一个递归删除函数，它不会将指向叶节点的指针归零。

bool removeNode(Node* tree, int key)
{
    bool removed = false;

    if (tree)
    {
        if (key < tree->key)
        {
            removeNode(tree->left, key);
        }
        else if (key > tree->key)
        {
            removeNode(tree->right, key);
        }
        else // this node is the key
        {
            if (!tree->left && !tree->right) // leaf
            {
                free(tree);
                tree = 0;
            }
            else if (!tree->left)
            {
                *tree = *tree->right;
            }
            else if (!tree->right)
            {
                *tree = *tree->left;
            }
            else // this node has 2 children
            { 
                Node* paux = tree->left;

                if (paux->right)
                {
                    while (paux->right)
                    {
                        paux = paux->right;
                    }
                }

                tree->key = paux->key;
                tree->left = paux->left;
            }

            removed = true;
        }
    }

    return removed;
}

我用

Node* node = (Node*)malloc(sizeof(Node));

分配内存。我的叶子的地址已正确归零，但当它返回到上一个调用时，地址仍然保持不变。如果地址被归零，为什么它会返回到以前的值？更改应该会影响指针...不是吗？

数据结构及相关函数:

typedef struct Node
{
    int key;
    struct Node* left;
    struct Node* right;
} Node;

// init a binary tree
void init(Node** tree, int key)
{
    *tree = (Node*) malloc(sizeof(Node));

    (*tree)->key = key;
    (*tree)->left = 0;
    (*tree)->right = 0;
}

// insert at binary tree
bool insert(Node** tree, int key)
{
    bool inserted = false;

    if (!*tree)
    {
        init(&*tree, key);
    }
    else
    {
        Node* node = (Node*)malloc(sizeof(Node));
        node->key = key;
        node->left = 0;
        node->right = 0;

        Node* paux = *tree;
        Node* root = paux;

        while (paux != 0)
        {
            root = paux;

            if (key < paux->key)
            {
                paux = paux->left;
            }
            else
            {
                paux = paux->right;
            }
        }

        paux = node;
        if (key < root->key)
        {
            root->left = paux;
        }
        else
        {
            root->right = paux;
        }

        inserted = true;
    }

    return inserted;
}

void print(Node* tree)
{
    if (tree != 0)
    {
        printf("%d  ", tree->key);

        print(tree->left);
        print(tree->right);
}

Answer 1

您遇到的问题是因为该函数无法修改输入指针。指针本身按值传递。

想想一个递增整数的函数。由于参数是“按值”传递的，因此简单的实现将不起作用。

void inc(int x)
{
    x++;
}

您可以通过引用(指针)传递它来修复此示例

void inc(int *x)
{
    (*x)++;
}

因此，如果您希望能够从函数内部使指针无效，请将指针传递给指针:

bool removeNode(Node **tree, int key)