二叉搜索树删除函数输出异常问题排查求助

核心问题梳理 #

你的代码存在几个关键问题，导致Delete功能异常：

1. 递归函数未返回递归结果 #

search和minimum函数在递归调用时没有返回值，导致函数最终返回栈上的随机地址，无法正确定位目标节点或中序后继节点：

• search中，递归调用search(tnode->right, data)或search(tnode->left, data)时，没有用return返回结果。
• minimum中，递归调用minimum(tnode->left)时同样未返回结果。

2. Delete函数逻辑错误 #

依赖search找到节点后直接修改，无法维护父节点与子节点的指针关联：

• 删除节点时，仅修改了目标节点本身，未更新其父节点的left/right指针，导致树结构断裂，出现野指针或无效引用。

3. Main函数未更新Root指针 #

调用deletenode后，没有用返回值更新root指针，删除根节点时，原root仍然指向已释放的内存，导致遍历异常。

4. Insert函数遗漏重复值处理 #

当插入重复数据时，函数没有返回原节点，可能导致返回随机值。

修正后的完整代码 #

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

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

struct node *insert(struct node *tnode, int data)
{
    if (tnode == NULL)
    {
        struct node *ptr = (struct node *)malloc(sizeof(struct node));
        ptr->data = data;
        ptr->left = NULL;
        ptr->right = NULL;
        return ptr;
    }
    if (data > tnode->data)
    {
        tnode->right = insert(tnode->right, data);
    }
    else if (data < tnode->data)
    {
        tnode->left = insert(tnode->left, data);
    }
    // 处理重复值，直接返回原节点
    return tnode;
}

void in_order(struct node *tnode)
{
    if (tnode == NULL)
        return;
    in_order(tnode->left);
    printf("%d\t", tnode->data);
    in_order(tnode->right);
}

struct node *search(struct node *tnode, int data)
{
    if (tnode == NULL)
    {
        return NULL;
    }
    if (data == tnode->data)
    {
        return tnode;
    }
    else if (data > tnode->data)
    {
        return search(tnode->right, data); // 添加return
    }
    else
    {
        return search(tnode->left, data);  // 添加return
    }
}

struct node *minimum(struct node *tnode)
{
    if (tnode == NULL)
    {
        printf("No node present\n");
        return NULL;
    }
    if (tnode->left == NULL)
    {
        return tnode;
    }
    else
    {
        return minimum(tnode->left); // 添加return
    }
}

struct node *deletenode(struct node *tnode, int data)
{
    if (tnode == NULL)
    {
        printf("Value not found\n");
        return NULL;
    }

    // 递归查找目标节点，同时维护父节点指针
    if (data < tnode->data)
    {
        tnode->left = deletenode(tnode->left, data);
    }
    else if (data > tnode->data)
    {
        tnode->right = deletenode(tnode->right, data);
    }
    else
    {
        // 找到目标节点，开始处理删除
        // 无子女或单子女情况
        if (tnode->left == NULL)
        {
            struct node *temp = tnode->right;
            free(tnode);
            return temp;
        }
        else if (tnode->right == NULL)
        {
            struct node *temp = tnode->left;
            free(tnode);
            return temp;
        }

        // 双子女情况，用中序后继替换
        struct node *temp = minimum(tnode->right);
        tnode->data = temp->data;
        // 删除后继节点
        tnode->right = deletenode(tnode->right, temp->data);
    }
    return tnode;
}

int main()
{
    struct node *root = NULL;
    int n, i, data, d;
    printf("Enter how many nodes you have to enter in a tree\n");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        printf("Enter data\n");
        scanf("%d", &data);
        root = insert(root, data);
    }
    printf("\nIN-Order display\n");
    in_order(root);
    printf("\nEnter data to be delete\n");
    scanf("%d", &d);
    // 更新root指针
    root = deletenode(root, d);
    printf("\nIN-Order display\n");
    in_order(root);
    return 0;
}

关键修改说明 #

1. 修复递归返回值：在search和minimum的递归调用处添加return，确保返回正确的节点指针。
2. 重构Delete函数：改为递归遍历树的方式，在遍历过程中更新父节点的left/right指针，确保树结构的完整性。
3. 更新Root指针：Main函数中用deletenode的返回值更新root，处理根节点被删除的情况。
4. 完善Insert函数：添加重复值处理，返回原节点。

内容的提问来源于stack exchange，提问作者Mr. K