前几日闲来无事,便自己写写二叉树的实现,其中在释放二叉树时引发了内存访问非法的错误。
我的思路是,采用递归,自底向上释放每一个结点。
错误的函数头设计为:bool FreeTree(Tree *root);传入根节点的地址。调用函数后使用main函数中root出现上述错误。苦思,突然得到灵感,将函数头改为:bool FreeTree(Tree **root);传入指向根节点的指针的地址。
为什么要这样改呢?因为释放后需要同时改变根节点指针。则必须传入根节点指针的地址。
让我们来回忆一下c的函数(不考虑传引用)的传值知识。3个字足以概括全部:“值传递”。
如声明void fn(T t),调用fn(t)。实际传入函数的是实参t的值。我们来讨论一下t的类型。
1.如果实参是常量,fn(“abc”),fn(1),fn(‘a’)等等,则是将传入的值复制一份存入T t中,值传递;
2.如果实参是普通变量,如fn(a),则是将a中得值复制一份存入T t中;不论如何改变t,a不变,值传递;
3.如果实参是指针,如T a,fn(a),此时调用,传入指针a的值,是一个地址;将地址保存在T t中,此时我们可以透过*t取到实际的值,但仍然是值传递;
故c中调用函数,皆是传值。
由第三条可以得知,但凡要在函数改变一个变量的值,则一定要传入该变量的地址或者指向该变量的指针。
回到最初的问题,由于需要释放整个二叉树的内存,并且使树指向根节点的指针的值设为NULL。所以需要实参必须是&tree;
附上bool FreeTree(Tree **root)实现,希望大家多多点评:
bool FreeTree(Tree **root)
{
if ((*root)->left != NULL)
{
FreeTree(&((*root)->left));
}
if ((*root)->right != NULL)
{
FreeTree(&((*root)->right));
}
if ((*root)->left!=NULL||(*root)->right!=NULL)
{
return false;//释放内存失败
}
else
{
free(*root);//释放内存并置空
*root=NULL;
return true;
}
}