递归删除二叉树 [英] recursive delete on a binary tree
问题描述
我试图了解删除二进制搜索树的递归方法如何工作.我在许多地方遇到的代码如下:
I am trying to understand how the recursive method of deletion of a binary search tree works. The code that I came across in many places looks as follows:
void destroy_tree(struct node *leaf)
{
if( leaf != 0 )
{
destroy_tree(leaf->left);
destroy_tree(leaf->right);
free( leaf );
}
}
但是我不明白a)如果例程中没有返回,它将如何工作? b)何时调用free()?我想到了例如一棵树:
I can't understand however a) how does it work if there are no returns in the routine? b) when free() gets to be called? I think about, e.g., such a tree:
10
/ \
6 14
/ \ / \
5 8 11 18
所以我的理解是我遍历10-> 6-> 5,然后调用destroy_tree(5-> left).因此,if内部的叶为NULL,并且不执行与if相关的内容,因此不会删除5.在这种推理中我会在哪里犯错误?收卷和放卷在这里如何工作?任何帮助,请感激:-)
So my understanding is that I traverse 10->6->5, and then I call destroy_tree(5->left). Therefore, leaf inside if is NULL, and what is if-dependent is not executed, hence 5 is not being deleted. Where do I make mistake in this reasoning? How does winding and unwinding work here? Any help kindly appreciated :-)
推荐答案
此时看起来像这样:
void destroy_tree(struct node *leaf_5)
{
if( leaf_5 != 0 ) // it's not
{
destroy_tree(leaf_5->left); // it's NULL so the call does nothing
destroy_tree(leaf_5->right); // it's NULL so the call does nothing
free( leaf_5 ); // free here
}
}
什么都不需要返回...步骤的历史记录"在调用堆栈上,此时看起来像这样:
Nothing is required to return... the "history" of the steps is on the call stack, which looks something like this at that point:
destroy_tree(leaf_10)
destroy_tree(leaf_10->left, which is leaf_6)
destroy_tree(leaf_6->left, which is leaf_5)
因此,leaf_5消失之后,它会返回堆栈并执行destroy_tree(leaf_6->right, which is leaf_8)
...等等...
So after leaf_5 is gone, it goes back up the stack and does destroy_tree(leaf_6->right, which is leaf_8)
... etc...
这篇关于递归删除二叉树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!