c - 递归删除树的所有节点

Question

/*
Recursively remove all nodes of the tree
*/
void dispose(node* root)
{
    if (root != NULL)
    {
        dispose(root->left);
        dispose(root->right);
        free(root);
    }
}

我不明白这段代码是如何删除整棵树的。

我看到的是它递归地转到左节点，直到到达空节点，然后转到右节点，然后再次向左移动直到为空，然后向右移动，如果为空，则释放父节点。

它似乎删除了树的最后一片叶子而不是整个树，

如果我弄错了，有人可以像我上面那样解释代码的过程吗？

Answer 1

写出程序执行时将进行的函数调用的顺序会有很大帮助。这是一个示例树:

            A
    B               C
D       E       F       G

对于这棵树，函数调用的顺序是:

dispose(A)
    dispose(B)
        dispose(D)
            dispose(NULL)
            dispose(NULL)
            free(D)
        dispose(E)
            dispose(NULL)
            dispose(NULL)
            free(E)
        free(B)
    dispose(C)
        dispose(F)
            dispose(NULL)
            dispose(NULL)
            free(F)
        dispose(G)
            dispose(NULL)
            dispose(NULL)
            free(G)
        free(C)
    free(A)