二叉树节点删除后遍历打印触发Segmentation Fault的问题排查

段错误的核心原因是删除操作没有正确更新二叉树的结构：

• 在main函数中，node = search(root, 3)得到的是指向值为3的节点的指针，随后调用delete(&node)时，传递的是局部变量node的地址。
• delete函数内部修改的是这个局部变量node的值，而非二叉树中父节点指向该待删节点的指针（比如原树中值为2的节点的right指针）。
• 这导致原树结构中，父节点的指针仍然指向已经被free的内存空间，后续preorderTraversal遍历到该位置时，访问已释放的内存触发段错误。

要解决这个问题，需要让delete函数能够修改二叉树中父节点指向待删节点的指针，而非局部变量。这里提供两种可行的修改方式：

方式一：修改delete函数，内部完成查找与删除 #

这种方式不需要依赖search函数，直接在delete内部定位待删节点及其父节点：

void delete(tree **root, int val) {
    tree *cur = *root;
    tree **parent_ptr = root; // 指向父节点中指向当前节点的指针

    // 查找待删节点，同时记录父节点的指针
    while (cur && cur->val != val) {
        parent_ptr = (cur->val > val) ? &cur->left : &cur->right;
        cur = (cur->val > val) ? cur->left : cur->right;
    }

    if (!cur) return; // 未找到要删除的节点

    // 执行删除逻辑，修改父节点的指针
    tree *tmp;
    if (!cur->left) {
        tmp = cur;
        *parent_ptr = cur->right;
        free(tmp);
    } else if (!cur->right) {
        tmp = cur;
        *parent_ptr = cur->left;
        free(tmp);
    } else {
        // 找到左子树的最大节点
        tree **max_right_ptr = &cur->left;
        tree *max_node = cur->left;
        while (max_node->right) {
            max_right_ptr = &max_node->right;
            max_node = max_node->right;
        }
        // 将待删节点的右子树挂到最大节点的右指针
        max_node->right = cur->right;
        // 用左子节点替换待删节点
        tmp = cur;
        *parent_ptr = cur->left;
        free(tmp);
        // 清空原最大节点父节点的指向，避免悬垂指针
        *max_right_ptr = NULL;
    }
}

修改main函数中的调用：

// 替换原来的node = search(...)和delete(&node)
delete(&root, 3);

方式二：修改search函数，返回指向待删节点指针的指针 #

让search函数返回父节点中指向待删节点的指针的地址，这样delete函数可以直接修改这个指针：

tree **search(tree **root, int val) {
    if (!*root) return NULL;
    tree **cur_ptr = root;
    while (*cur_ptr) {
        if ((*cur_ptr)->val == val) {
            return cur_ptr;
        } else if ((*cur_ptr)->val > val) {
            cur_ptr = &(*cur_ptr)->left;
        } else {
            cur_ptr = &(*cur_ptr)->right;
        }
    }
    return NULL;
}

修改main函数：

tree **node_ptr = search(&root, 3);
if (node_ptr) {
    delete(node_ptr);
}

原delete函数无需修改，此时传递的是树结构中指向待删节点的指针的地址，修改*node_ptr就能正确更新树的结构。

修改后重新编译运行，preorderTraversal可以正常输出删除后的树结构，不会触发段错误。

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