c - 使指针中的值无效

Question

我已经很长时间没有做指针运算了，所以我想我应该试试 C 语言并做一个简单的二叉搜索树。但是，我无法掌握删除的窍门。按照我的预期，这些方面的工作:

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

typedef struct Tree{
    struct Node* root;
}Tree;

int main(){
    Tree *tree = createTree(); 

    treeInsert(10, tree);    // Inserts 10 at root
    treeInsert(30, tree);    // Inserts 30 to root->right
    treeInsert(5, tree);     // Inserts 5 to root->left
    treeInsert(7, tree);     // Inserts 7 to root->left->right
    treeInsert(12, tree);    // Inserts 12 to root->right->left

    // Removes Node "7" from the tree successfully
    free(tree->root->left->right);   // Free memory for this node in the tree
    tree->root->left->right = NULL;  // Set the pointer to NULL

    return 0;
}

我想编写一个 nodeDelete(Node *killNode) 函数来释放与节点关联的内存，然后将其指向 NULL，但我发现它并没有像我预期的那样工作

int main(){
   // ... snip ...

   Node *kill = tree->root->left->right  // Points kill node to Node "7"
   free(kill);                           // Deallocates memory
   kill = NULL;                          // Points kill to NULL, but keeps 
                                         //   tree->root->left->right **undefined** 
   // ... snip ...
}

我认为我的问题是我告诉它 kill 现在指向 NULL，这会断开它与树中节点的连接并且不会影响原始节点指针。我如何告诉它我想将 tree->root->left->right 指向 NULL 而不是 kill？在这种情况下我需要一个指向指针的指针吗？

Answer 1

是的，如果您想删除该节点，您需要将tree->root->left->right 设置为NULL。这意味着您不能只将该指针的值传递给删除函数。

您有两个选择:您可以将指针传递给要删除的节点的父节点，以及有关要删除哪个子节点的信息:

nodeDelete(Node *parent, int kill_right)
{
    Node *kill;

    if (kill_right) {
        kill = parent->right;
        parent->right = NULL;
    } else {
        kill = parent->left;
        parent->left = NULL;
    }

    free(kill);
}

在这种情况下，您将调用 nodeDelete(tree->root->left, 1);。

或者，您可以将指针传递给要删除的指针:

nodeDelete(Node **killptr)
{
    free(*killptr);
    *killptr = NULL;
}

在这种情况下，您将调用 nodeDelete(&tree->root->left->right);。