c - 二叉树删除

Question

已知:deleteTree() 函数删除树，但不会将根更改为 NULL，如果 deleteTree() 的用户不将根更改为 NULL 并尝试使用根指针访问值，则可能会导致问题。我们可以修改deleteTree()函数来引用根节点，这样就不会出现这个问题。

[链接] http://www.geeksforgeeks.org/write-a-c-program-to-delete-a-tree/

疑问:在deleteTree函数中传递了来自主节点的节点副本，那么如何在deleteTree()中释放所有这些节点的实际内存。据说树被删除了，但是要删除树，我们不应该传递地址吗？另外，如果我们认为树实际上被删除了，那么根节点也随之被删除，那么为什么它不在主节点中更改为 NULL 呢？

void deleteTree(struct node* node) 
{
  if (node == NULL) return;
  deleteTree(node->left);
  deleteTree(node->right);
  printf("\n Deleting node: %d", node->data);
  free(node);
}
int main()
{
  struct node *root = newNode(1); 
  root->left            = newNode(2);
  root->right          = newNode(3);
  root->left->left     = newNode(4);
  root->left->right   = newNode(5); 

  deleteTree(root);  
  root = NULL;

  printf("\n Tree deleted ");

  getchar();
  return 0;
}

修改后的代码:

void _deleteTree(struct node* node)
{
  if (node == NULL) return;

  _deleteTree(node->left);
  _deleteTree(node->right);
  printf("\n Deleting node: %d", node->data);
  free(node);
}


void deleteTree(struct node** node_ref)
{
  _deleteTree(*node_ref);
  *node_ref = NULL;
}

int main()
{
  struct node *root = newNode(1);
  root->left            = newNode(2);
  root->right          = newNode(3);
  root->left->left     = newNode(4);
  root->left->right   = newNode(5);


  deleteTree(&root);
  printf("\n Tree deleted ");

  getchar();
  return 0;
}

在这种情况下，如果我们在 main 中设置 root=NULL 而不是在 deleteTree 函数中设置 root=NULL，那么释放是如何发生的？

Answer 1

您混淆了两个概念 - 内存释放和将指针设置为 NULL。通过使用free，内存被释放，并且指针现在指向一 block 未分配的内存。通过将 node* 设置为 NULL，您表明该指针无效 - 您可以看到代码检查了这一点 - if (node ==NULL) return;。如果您只是将 root 设置为 NULL，则会造成内存泄漏，因为指向的内存仍处于分配状态。

另外 - 据说树已被删除，但是要删除树，我们不应该传递地址 - 你正在传递地址 - deleteTree(&root); code> - root 是包含根节点地址的节点*。

希望这有帮助。