c - 删除二叉搜索树的两种递归算法之间的区别

Question

我对这两个算法有疑问:

这正常工作:

node* deleteTree(node* root)
{
    if(root != NULL)
    {
       deleteTree(root->left);
       deleteTree(root->right);
       deallocateNode(root);
    }
    return root=NULL;
}

这不:

void deleteTree(node* root)
{
   if(root != NULL)
   {
      deleteTree(root->left);
      deleteTree(root->right);
      deallocateNode(root);
   }
   root=NULL;
}

为什么？我需要将 root 设置为 null，这样删除 BST 后的节点指针就不会指向未分配的内存。我更喜欢第二种算法，因为函数的召回更直观。

理论上，这两种算法是等效的，但如果我使用第二种算法并尝试打印 BST，程序将进入循环。

Answer 1

当您拥有 node *root 并分配 node = NULL 时，它不会影响其在外部的值。如果要修改指针值，则必须传递双指针。

类似于:

void deleteTree(node** root)
{
   if(*root != NULL)
   {
      deleteTree(&((*root)->left));
      deleteTree(&((*root)->right));
      deallocateNode(*root);
   }
   *root = NULL;
}

但我真的不认为你需要分配 node = NULL 因为你释放了它。因此，您可以在调用 deleteTree 后分配 node = NULL，而无需使用双指针。