我有一个关于这两种算法的问题:
正常工作:
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
,就不需要处理双指针了。