我有一个关于这两种算法的问题:
正常工作:

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,程序就会进入循环。

最佳答案

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

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

但我不认为你真的需要分配node = NULL,因为你释放了它。所以,只要在调用deletetetree之后分配node = NULL,就不需要处理双指针了。

10-07 19:32
查看更多