C语言二叉搜索树(BST)插入后后序遍历异常崩溃问题排查

问题根因定位 #

异常终止由两处逻辑错误共同导致：

• 第一处：insert() 函数逻辑错误，新节点未真正挂载到二叉树结构上
• 第二处：postorder() 函数递归终止条件判断错误，触发空指针访问

错误1：insert函数修复 #

原代码的while循环在找到空指针位置后，仅修改了临时指针变量temp2的值，没有把新节点挂载到父节点的对应子指针上，除根节点外所有插入的节点都没有接入树结构。
修复后的insert代码：

void insert(int num)
{
    create(num);
    if (root == NULL)
    {
        root = temp1;
        printf("%d inserted\n", root->data);
    }
    else
    {
        struct btNode *parent = NULL; // 新增父节点指针记录挂载位置
        temp2 = root;
        while (temp2 != NULL)
        {
            parent = temp2; // 每次移动前保存当前节点为父节点
            if (temp2->data >= num)
            {
                temp2 = temp2->left;
            }
            else
            {
                temp2 = temp2->right;
            }
        }
        // 根据值大小挂载到父节点的左/右子节点
        if (parent->data >= num)
            parent->left = temp1;
        else
            parent->right = temp1;
        printf("%d inserted\n", temp1->data);
    }
}

错误2：postorder函数修复 #

原代码递归终止时判断的是全局变量root是否为空，没有判断当前传入的节点r是否为空，递归到叶子节点的子节点（NULL）时不会终止，会继续访问r->left触发空指针崩溃。
修复后的postorder代码：

void postorder(struct btNode *r)
{
    if (r == NULL) // 改为判断当前传入节点是否为空
    {
        return;
    }
    postorder(r->left);
    postorder(r->right);
    printf("%d ", r->data);
}

如果需要保留树为空的提示，可以在main函数调用postorder之前加判断：

case 4:
    if(root == NULL)
        printf("Tree is empty");
    else
        postorder(root);
    break;

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