c++ - 对于二叉搜索树中的递归删除调用，调用堆栈看起来如何？

Question

我正在学习二叉搜索树教程。我找到了这个功能destroy_tree(node* leaf)。它的行为让我很担心——我无法想象调用堆栈的样子，你能解释一下吗？

void btree::destroy_tree(node* leaf)
{
    if (leaf !=NULL)
    {
        destroy_tree(leaf->left);
        destroy_tree(leaf->right);
        delete leaf;
    }
}

Answer 1

对于递归函数的问题，有时想想或画一棵简单的树，然后在纸上画出函数是如何通过它的，这会有所帮助。

首先，自从我使用 c++ 以来已经有一段时间了，但是为了这个示例，我将把你的代码更改为：

void btree::destroy_tree(node* leaf)
{
    if(leaf !=NULL)
    {
        if (leaf->left != NULL)
            destroy_tree(leaf->left);

        if (leaf->right != NULL)
            destroy_tree(leaf->right);

        delete leaf;
    }
}

只是这样堆栈上的东西就更少了。

想想这个函数的逻辑是如何通过树递归工作的。以我从 Wikipedia 中获取的以下树示例为例

假设你打电话给destroy_tree(root). 该函数首先destroy_tree(root)调用destroy_tree(node->left)，然后destroy_tree(node->right). 这意味着左孩子总是在任何右孩子之前迭代。因此，要使用上述树中的数字，树将按以下顺序遍历：8,3,1,6,4,7,10,14,13。基于此可以看到遍历了所有的left children。当仍有未遍历的左侧时，不会遍历右侧孩子。

调用堆栈应与程序运行类似。在到达任何右节点之前，调用将在每个destroy_tree(left)连续的左节点上调用“destroy_tree()” 。