c++ - 堆栈是如何组织的？ : Deleting a Binary Tree

Question

我有这段代码可以从内存中删除二叉树，但我不知道当您对 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;
    }
}

Answer 1

destroy(tree->left) 在 destroy(tree->right) 之前完全执行。

但是，请记住左树既有左边也有右边。所以在这里它会再次先向左走，然后在返回的路上向右走。右侧可能包含最先处理的左侧节点。

堆栈对此影响不大。每当您深入树中的一个杠杆(即在左侧或右侧调用 destroy)时，函数调用可能会将一些变量压入堆栈——例如返回地址和当前节点指针。当到达一片叶子并且函数调用开始返回时，这些变量会再次从堆栈中取出。

通常这应该不是类(class)问题，但如果您的树有很多级别，您可能需要考虑堆栈的使用。

如果您假设一个空堆栈开始并查看第一个 destroy left 调用，您将拥有:

stack = |first left|

现在这可能会导致对 left 的另一个调用:

堆栈 = |第一个左边|左二|

甚至第三次向左调用:

堆栈 = |第一个左边|左二|左三|

现在对左三的调用返回:

堆栈 = |第一个左边|左二|

但是右边会调用:

堆栈 = |第一个左边|左二|先右|

这个右边可能在左边有一个节点所以我们会得到:

堆栈 = |第一个左边|左二|第一个权利 |第一个离开 |

这将一直持续到所有节点返回 - 就像这样

堆栈 = |第一个左边|左二|先右|

堆栈 = |第一个左边|左二|

stack = |first left|

堆栈 =

现在是时候从右侧的顶部做同样的事情了

stack = |第一个右边|

等等……

对于代码中的简单示例，它很可能会导致树中每个级别的 4 字节返回地址被插入堆栈。因此，即使树级别相当深，堆栈使用率也会很低。