删除的二进制树有不正确的后续遍历

Question

我有一个问题，现在真的让我很烦。我想制作一棵二进制树，将其删除，然后创建一个新的树。我一直在尝试自己制作该程序，但我一直陷入问题上：使用后遍历删除二进制树后，我尝试制造一棵新的二进制树。但是最初的树尚未被删除，因此实际上我要添加到树上，而不是制作一棵新树。

我以为我在做一些非常错误的事情，所以我在网上找到了一些C代码，该c代码与我的代码相同的核心功能（ c代码中的二进制树）：

#include<stdlib.h>
#include<stdio.h>

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

void deltree(node * tree)
{
    if (tree)
    {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        return NULL;
    }

    if(val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return *tree;
    }
}

void main()
{
    node *root;
    node *tmp;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);

    /* Search node into tree */
    tmp = search(&root, 4);
    if (tmp)
    {
        printf("Searched node=%d\n", tmp->data);
    }
    else
    {
        printf("Data Not found in tree.\n");
    }

    /* Deleting all nodes of tree */
    deltree(root);
    printf("Tree has been deleted\n");

    insert(&root, 90);
    insert(&root, 40);
    insert(&root, 150);
    insert(&root, 60);
    insert(&root, 120);
    insert(&root, 170);
    insert(&root, 20);

    print_inorder(root);
}

但是奇怪的是，我在网上发现的代码与我的问题相同。在上面的代码中，在main（）函数中，将树被删除，然后将新节点添加到树中。但是，一旦添加了节点并将树在有序中打印出来，就可以看出输出是两棵树的组合，而不是第二个树的组合。

换句话说，此代码与我的问题完全相同。如何解决上述代码的问题？作为参考，我将CodeBlocks用作编译器，并且可以在此处找到程序的输出，可以在此处找到：

注意：我已经在Internet上包含了一个代码，因为我想要尝试解决精确描述的问题而不共享我的个人代码太多。

Answer 1

如评论中所述，这可能是由于未将删除树的指针设置为null。

以下是deltree的修改版本，该版本将删除树的指针设置为null。

void deltree(node** tree) // pass by reference 
{
    if (*tree)
    {
        deltree(&(*tree)->left);
        deltree(&(*tree)->right);
        free(*tree);
    }
    *tree = NULL; // set the pointer to the deleted tree to null
}

请注意，为了使要在deltree函数中修改的deltree参数，您将必须将指针传递给该指针，例如deltree（root）;现在应为deltree（＆amp; root）;。这被指针称为通行证。