从指针中取消值

我很长时间没有做过指针运算，所以我想我会尝试用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); 。

Answer 2

是的，你需要使用双指针。 您还需要确保以递归方式删除要删除的节点的所有子节点：

 void nodeDelete(Node **killNode) { if(!*killNode) return; // Free child nodes nodeDelete((*killNode)->left); nodeDelete((*killNode)->right); // Free the node itself free(*killNode); *killNode=NULL; } 

有意在开头执行空指针检查 – 这可以防止您必须在空指针检查中包装递归调用。