我有这段代码可以从内存中删除二叉树,但我不知道当您对 destroy(<#node* tree#>)
进行递归调用时堆栈的外观或递归的工作方式。 .我知道当您到达分支的末尾时递归结束,因此得出调用并开始在递归中上升的结论,但是如果递归函数调用保持在它停止的位置,是对 destroy(tree->right)
的调用等待执行 destroy(tree->left)
完成?
struct node{
int value;
node* left;
node* right;
};
void destroy(node* tree){
if(tree != NULL){
destroy(tree->left);
destroy(tree->right);
delete tree;
}
}
最佳答案
destroy(tree->left) 在 destroy(tree->right) 之前完全执行。
但是,请记住左树既有左边也有右边。所以在这里它会再次先向左走,然后在返回的路上向右走。右侧可能包含最先处理的左侧节点。
堆栈对此影响不大。每当您深入树中的一个杠杆(即在左侧或右侧调用 destroy)时,函数调用可能会将一些变量压入堆栈——例如返回地址和当前节点指针。当到达一片叶子并且函数调用开始返回时,这些变量会再次从堆栈中取出。
通常这应该不是类(class)问题,但如果您的树有很多级别,您可能需要考虑堆栈的使用。
如果您假设一个空堆栈开始并查看第一个 destroy left 调用,您将拥有:
stack = |first left|
现在这可能会导致对 left 的另一个调用:
堆栈 = |第一个左边|左二|
甚至第三次向左调用:
堆栈 = |第一个左边|左二|左三|
现在对左三的调用返回:
堆栈 = |第一个左边|左二|
但是右边会调用:
堆栈 = |第一个左边|左二|先右|
这个右边可能在左边有一个节点所以我们会得到:
堆栈 = |第一个左边|左二|第一个权利 |第一个离开 |
这将一直持续到所有节点返回 - 就像这样
堆栈 = |第一个左边|左二|先右|
堆栈 = |第一个左边|左二|
stack = |first left|
堆栈 =
现在是时候从右侧的顶部做同样的事情了
stack = |第一个右边|
等等……
对于代码中的简单示例,它很可能会导致树中每个级别的 4 字节返回地址被插入堆栈。因此,即使树级别相当深,堆栈使用率也会很低。
关于c++ - 堆栈是如何组织的? : Deleting a Binary Tree,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29441828/