1

我很久没有做过指针运算了，所以我想我会尝试 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->rightNULL 而不是kill？在这种情况下我需要一个指向指针的指针吗？

4

2 回答 2

2

是的，如果要删除该节点，则需要设置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);.

于 2012-07-26T14:07:23.863 回答
0

是的，您需要使用双指针。您还需要确保递归删除要删除的节点的任何子节点：

void nodeDelete(Node **killNode)
{
    if(!*killNode)
        return;

    // Free child nodes
    nodeDelete((*killNode)->left);
    nodeDelete((*killNode)->right);

    // Free the node itself
    free(*killNode);
    *killNode=NULL;
}

空指针检查是有意在开始时执行的——这可以防止您将递归调用包装在空指针检查中。

于 2012-07-26T14:13:22.307 回答