二叉搜索树(BST)删除含孙节点的祖父节点时程序崩溃问题排查

我一眼就定位到导致崩溃的核心问题了——你的代码里存在严重的返回值类型不匹配问题，尤其是FindMin和FindMax函数，这直接导致删除带双子女的节点（比如80）时出现非法内存访问，触发崩溃。下面是具体问题和修复步骤：

核心错误点 #

• FindMin/FindMax返回值类型完全错配：这两个函数声明返回struct node*（节点指针），但你实际返回的是int类型的值（比如return root->data;或者空树时返回-1）。当delete函数执行struct node *tmp=FindMin(root->right);时，程序会把一个整数当成内存地址来使用，访问这个非法地址必然导致崩溃。
• delete函数空树返回错误：函数声明返回struct node*，但空树时你返回了-1（整数），这会导致调用者拿到错误的指针值。
• inorder函数返回值冗余：它声明返回struct node*，但函数内部没有任何return语句，属于未定义行为，虽然暂时没触发崩溃，但必须修正。

修复后的完整代码 #

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

struct node { 
    int data; 
    struct node *left, *right; 
}; 
struct node *root=NULL; 

// 修正返回类型为void，因为只是遍历打印
void inorder(struct node *root) { 
    if(root!=NULL) { 
        inorder(root->left); 
        printf("%d ", root->data); 
        inorder(root->right); 
    } 
} 

// 修正返回类型为struct node*，返回最小节点的指针
struct node *FindMin(struct node *root) { 
    if(root==NULL) { 
        printf("Tree is empty!\n"); 
        return NULL; 
    } 
    while(root->left!=NULL) { 
        root=root->left; 
    } 
    return root; 
} 

// 修正返回类型为struct node*，返回最大节点的指针
struct node *FindMax(struct node *root) { 
    if(root==NULL) { 
        printf("Tree is empty!\n"); 
        return NULL; 
    } 
    while(root->right!=NULL) { 
        root=root->right; 
    } 
    return root; 
} 

struct node *newnode(int data) { 
    struct node *tmp=(struct node*)malloc(sizeof(struct node)); 
    tmp->data=data; 
    tmp->left=tmp->right=NULL; 
    return tmp; 
} 

struct node *insert(struct node *node, int data) { 
    if(node==NULL) { 
        return newnode(data); 
    } else if(data < node->data) { 
        node->left=insert(node->left, data); 
    } else if(data > node->data) { 
        node->right=insert(node->right,data); 
    } 
    return node; 
} 

struct node *delete(struct node *root, int data) { 
    if(root==NULL) { 
        printf("Data not found in tree!\n"); 
        return NULL; // 修正返回NULL，而非-1
    } else if(data < root->data) { 
        root->left=delete(root->left, data); 
    } else if(data > root->data) { 
        root->right=delete(root->right, data); 
    } else { 
        // 叶子节点
        if(root->left==NULL && root->right==NULL) { 
            free(root); 
            root=NULL; 
        } 
        // 只有右子树
        else if(root->left==NULL) { 
            struct node *tmp=root; 
            root=root->right; 
            free(tmp); 
        } 
        // 只有左子树
        else if(root->right==NULL) { 
            struct node *tmp=root; 
            root=root->left; 
            free(tmp); 
        } 
        // 有两个子节点
        else { 
            // 现在拿到的是正确的节点指针，而非整数
            struct node *tmp=FindMin(root->right); 
            root->data=tmp->data; 
            root->right=delete(root->right,tmp->data); 
        } 
    } 
    return root; 
} 

int main() { 
    root=insert(root,100); 
    insert(root,80); 
    insert(root,10); 
    insert(root,40); 
    insert(root,90); 
    insert(root,30); 
    insert(root,120); 
    insert(root,140); 
    
    printf("Inorder traversal before deletion: ");
    inorder(root); 
    printf("\n");
    
    // 这里要注意：FindMin/FindMax现在返回指针，所以要取data字段
    struct node *minNode = FindMin(root);
    struct node *maxNode = FindMax(root);
    if(minNode && maxNode) {
        printf("Min: %d Max: %d\n", minNode->data, maxNode->data);
    }
    
    // 注意：delete函数返回新的根节点，要赋值给root
    root = delete(root,80); 
    
    printf("After deletion:\n");
    printf("Inorder traversal: ");
    inorder(root); 
    printf("\n");
    
    return 0; 
}

额外说明 #

1. 修复后FindMin返回右子树的最小节点指针，delete函数可以正确获取这个节点的值来替换要删除的节点，再递归删除右子树中的这个最小节点，整个过程不会再出现非法内存访问。
2. 主函数里调用delete时，要把返回值重新赋值给root——虽然你的原代码里删除非根节点时不影响，但如果删除的是根节点，必须更新root指针。
3. FindMin/FindMax现在返回指针，所以主函数里要先判断指针不为空，再访问data字段，避免空指针访问。

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