堆栈是如何组织的？ : 删除二叉树

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(root)
>destroy(l)
    >l
         >l
         (...)
    >r
    (...)
>r
    >l
    (...)
    >r
    (...)
>delete root
>end

因此，您将开始一个接一个地推送地址，直到您最终到达分支的末尾，然后弹出一次，并继续探索直到下一个分支的末尾，依此类推。最后，在最后一个分支上，弹出所有函数，直到回到原来的函数，然后删除根节点。

Answer 2

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

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

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

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

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

堆栈 = |左一|

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

stack = |第一个左边|左二|

甚至第三次向左呼叫：

stack = |第一个左边|左二|左三|

现在呼叫左三 returns:

stack = |第一个左边|左二|

但是右边会叫：

stack = |第一个左边|左二|第一个右边 |

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

这将持续到所有节点 returns - 就像这样

stack = |第一个左边|左二|第一个右边 |

stack = |第一个左边|左二|

堆栈 = |左一|

堆栈=

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

堆栈 = |第一个右边|

等等...

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

堆栈是如何组织的？ : 删除二叉树

How is the stack organized? : Deleting a Binary Tree

c++

recursion

binary-tree

stack-trace