使用顺序遍历删除二叉树

Question

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

#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;
}

Answer 1

它显示的输出是正确的，因为按顺序它首先遍历左子树，然后遍历根，然后遍历右子树。

您不会得到4 2 1，因为4是左子树，然后它转到root，即2，然后到2的右子树。

当它太右时，子树根变成5，它的左子树是6。然后5然后到5的右子树即7。

1是根，因此如果不遍历左子树，它就不会转到1。

Answer 2

要按顺序遍历二叉树，需要执行以下操作

(i) Traverse the left most subtree starting at the left external node, 
(ii) Visit the root, and 
(iii) Traverse the right subtree starting at the left external node.

现在要删除节点，

(i) Traverse the left most subtree starting at the left external node,
(ii) delete the root, and 
(iii) Traverse the right subtree starting at the left external node.

Answer 3

我最初把它作为一条评论发布，但似乎问这个问题的人对我的回答很满意，所以我会在这里发布更详细的内容。

打电话给free时，一定要注意free到底做了什么，否则类似的事情可能会发生。

C库函数void free（void*ptr）释放之前通过调用calloc、malloc或realloc分配的内存。

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

root = VOID;

上面的代码在释放根节点后不会清除它，因此内存仍然全部存在。因此，C代码可以转到该内存位置（操作系统已经收到）并对其进行修改。这是非常危险的行为，因为操作系统会将此内存分配给另一个程序，然后您的程序可能会更改，从而导致明显的意外行为。解决这个问题的简单方法是在释放根节点之前移除正确的节点。