C语言二叉树后序遍历删除后插入新节点残留旧数据问题修复

原代码的deltree存在核心的C语言指针和内存管理逻辑错误：

• 函数参数传的是一级指针，属于值传递：调用deltree(root)时，只是把root保存的旧根节点地址拷贝给了函数形参，函数内部释放内存的操作不会修改main函数里root变量本身的值。free执行完后，root还存着已经被释放的旧内存地址，变成了野指针。
• free操作本身只会把对应内存块标记为可重新分配，不会自动把指针置空，也不会擦除内存里残留的旧数据。后续调用insert时，判断if(!(*tree))发现root不是NULL，就会顺着旧内存里残留的左右孩子指针往下遍历插入，自然就出现新旧节点混杂的情况，属于典型的*释放后使用（use-after-free）*未定义行为。

另外原代码还附带两个隐性bug：search函数的递归分支漏写return，搜索非根节点时会返回随机值；main函数定义为void返回值不符合C标准要求。

1. 把deltree的参数改为二级指针，递归释放每个节点后，立刻把对应指针置为NULL，最终把根节点也置为NULL，彻底消除野指针。
2. 给search函数的两个递归分支补上return，修正返回值错误。
3. 调整main函数为标准的int返回值类型，调用deltree时传入root的地址&root。

#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);
        *tree = NULL; // 释放后立即置空，杜绝野指针
    }
}

// 修正递归分支漏return的问题
node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        return NULL;
    }

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

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

    root = NULL;
    /* 插入第一棵树节点 */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    /* 打印第一棵树 */
    printf("Pre Order Display\n");
    print_preorder(root);

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

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

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

    /* 删除整棵树 */
    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);

    /* 打印第二棵树，仅会输出新节点的排序结果：20/40/60/90/120/150/170 */
    print_inorder(root);

    // 用完释放避免内存泄漏
    deltree(&root);
    return 0;
}

• C语言中如果需要在函数内部修改外部指针变量的指向，必须传入该指针的地址（即二级指针），否则函数内操作的只是指针的副本，修改不会生效到外部。
• 所有堆内存调用free释放后，必须立刻将对应指针赋值为NULL，从根源避免野指针、重复释放、释放后使用等内存错误。

内容的提问来源于stack exchange，提问作者Steven Underhill