c - 使用中序遍历删除二叉树

Question

我正在学习如何使用后序遍历删除二叉树。我理解删除一个节点，首先我们需要删除它的子节点，然后是节点本身，所以后序遍历最适合删除二叉树。我想过使用中序遍历做同样的事情，一切正常，但我不明白下面的代码是如何工作的？

#include<stdio.h>
#include<malloc.h>

struct b_tree{
    int data;
    struct b_tree *left,*right;
};

typedef struct b_tree tree;

tree* create_node(int data)
{
    struct b_tree* new_node=(tree*)malloc(sizeof(tree));
    new_node->data=data;
    new_node->left=NULL;
    new_node->right=NULL;
    return new_node;
}

void delete_tree(tree *root)
{
    if(root==NULL)
        return;
    delete_tree(root->left);
    printf("Deleting %d node.\n",root->data);
    free(root);
    delete_tree(root->right);
}

int main()
{
    tree *root=NULL;
    root=create_node(1);
    root->left=create_node(2);
    root->right=create_node(3);
    root->left->left=create_node(4);
    root->left->right=create_node(5);
    root->left->right->left=create_node(6);
    root->left->right->right=create_node(7);
    root->right->right=create_node(8);
    root->right->right->left=create_node(9);
    delete_tree(root);
    root=NULL;
    return 0;
}

根据中序遍历，第一个要删除的节点是4，然后是2，但是一旦我们释放了2，它就会丢失所有的数据，意味着它不应该保留指向右节点的指针，即 5，但即使在 2 被释放后，它的左子节点 5 也是仍在遍历，但不应发生，因为节点 2 已被释放。

上面代码的输出是:


我期望输出按以下节点顺序排列:4 2 1。

我不明白这一切是如何运作的。如果我错了，请纠正我。

Answer 1

我最初将此作为评论发布，但似乎提出问题的人对我的回答很满意，所以我将在此处发布更详细的信息。

当调用 free 时，重要的是要准确地注意 free 实际做了什么，否则可能会发生这样的事情。

The C library function void free(void *ptr) deallocates the memory previously allocated by a call to calloc, malloc, or realloc.

请注意，free 函数不会更改指针的值，它只是将内存返回给操作系统，以便可以将其分配给另一个程序。因此，人们通常会在调用 free 后“清除”指针，以避免访问另一个程序已更改的内存。

root = VOID;

上面的代码在释放根节点后并没有清除它，因为内存仍然在那里。因此，C 代码能够转到该内存位置(操作系统已经收到)并修改它。这是极其危险的行为，因为操作系统可以将此内存提供给另一个程序，然后您的程序可能会发生变化，从而导致明显的意外行为。解决这个问题的简单方法是在释放根节点之前删除正确的节点。