使用中序遍历删除二叉树

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

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

以上代码的输出为：

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

我不明白这一切是如何运作的。如有不妥请指正

Answer 1

它显示的输出是正确的，因为它按顺序首先遍历 left sub-tree 然后 root 然后 right sub-tree.

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

当它走得太右时，子树的根变为5，其左子树为6。然后是5，然后是[=18的右子树=] 即 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

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

这是一个中序遍历，指针首先指向最左边的节点，然后是根节点，然后是最右边的节点。由于 4 是最左边的节点，因此它已被打印，然后遍历到 2 。之后最右边的节点是 5。因为 5 有两个节点连接到它。它将再次迭代到最左边的节点，即 6。因此它打印为 4,2,6,5,7,3,9,8

Answer 4

我最初 post 将此作为评论编辑，但看起来问这个问题的人对我的回答很满意，所以我会 post 在这里更详细一点。

调用 free 时，请务必准确注意 free 实际执行的操作，否则可能会发生此类情况。

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

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

root = VOID;

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

使用中序遍历删除二叉树

Deleting a binary tree using inorder traversal

c

tree

binary-tree

data-structures