从二叉搜索树（BST）中删除根节点的异常问题排查

问题根源 #

你遇到的问题确实和二叉树的head指针未更新有关，同时removeNode函数存在一处逻辑漏洞，导致删除根节点后树的结构无法正确维护。

具体问题点 #

1. head指针未同步更新：
   删除根节点时，removeNode会返回新的根节点，但你没有把这个返回值赋值给binarySearchTree结构体里的head成员。原来的head指向的内存已经被释放，继续使用会触发野指针，遍历结果自然错误。

2. removeNode双节点处理逻辑缺失：
   在处理既有左子树又有右子树的节点时，你只替换了当前节点的值，但调用removeNode(minNode->val, root->right)后，没有将返回值赋值给root->right，导致右子树的结构没有正确更新。

修复后的完整代码 #

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

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

struct binarySearchTree{
    struct node * head; 
};

// 补全你移除的hasLeft函数
bool hasLeft(struct node *v) {
    return v != NULL && v->left != NULL;
}

// 补全你移除的hasRight函数
bool hasRight(struct node *v) {
    return v != NULL && v->right != NULL;
}

struct node* treeSearch(int k, struct node * v){
    if(v == NULL) return NULL; // 新增空指针保护，避免崩溃
    if(k < v->val){
        return treeSearch(k, v->left);
    }else if( k > v->val){
        return treeSearch(k, v->right);
    }else{
        return v; 
    }
}

struct node * insert(int k, struct node * v){
    if(v == NULL){
        struct node * newnode = malloc(sizeof(struct node));
        if(!newnode){
            return NULL; // 内存分配失败
        }
        newnode->val = k;
        newnode->left = NULL;
        newnode->right = NULL; 
        return newnode;
    }
    if(k < v->val){
        v->left = insert(k, v->left); 
    }else if(k > v->val){
        v->right = insert(k, v->right);
    }
    return v; 
}

struct node * findMin(struct node * root){
    if(root == NULL) return NULL; // 新增空指针保护
    struct node * cur = root;
    while (cur->left != NULL){
        cur = cur->left;
    }
    return cur;
}

struct node * removeNode(int k, struct node * root){
    struct node * temp;
    if(root == NULL){
        return NULL; 
    }
    if(k < root->val){
        root->left = removeNode(k, root->left);
    }else if(k > root->val){
        root->right = removeNode(k, root->right);
    }else{
        // 叶子节点
        if(root->left == NULL && root->right == NULL){
            free(root);
            return NULL; 
        }
        // 只有右子树
        else if(root->left == NULL){
            temp = root->right; 
            free(root);
            return temp; 
        }
        // 只有左子树
        else if(root->right == NULL){
            temp = root->left; 
            free(root);
            return temp; 
        }
        // 左右子树都存在
        else{
            struct node * minNode = findMin(root->right);
            root->val = minNode->val; 
            // 修复：将删除后的右子树重新赋值，维护结构
            root->right = removeNode(minNode->val, root->right);
            return root; 
        }
    }
    return root; // 新增返回，避免路径缺失导致的未定义行为
}

struct binarySearchTree * createBinaryTree(){
    struct binarySearchTree * tree = malloc(sizeof(struct binarySearchTree));
    if(!tree){
        printf("failed\n");
        return NULL;
    }
    tree->head = NULL; 
    return tree; 
}

void inorder(struct node * v){
    if(v == NULL) return; // 新增空指针保护
    if(hasLeft(v)){
        inorder(v->left);
    }
    printf("%d ", v->val);
    if(hasRight(v)){
        inorder(v->right);
    }
}

// 补全你提到的前序遍历函数
void preorder(struct node *v) {
    if(v == NULL) return;
    printf("%d ", v->val);
    if(hasLeft(v)) preorder(v->left);
    if(hasRight(v)) preorder(v->right);
}

// 测试用main函数
int main() {
    struct binarySearchTree *tree = createBinaryTree();
    // 插入1-15构建二叉搜索树
    for(int i=1; i<=15; i++){
        tree->head = insert(i, tree->head);
    }
    printf("原树前序遍历：");
    preorder(tree->head);
    printf("\n");
    
    // 删除根节点1，必须更新head指针
    tree->head = removeNode(1, tree->head);
    
    printf("删除根节点后前序遍历：");
    preorder(tree->head);
    printf("\n");
    
    return 0;
}

关键修复说明 #

• 更新head指针：删除根节点时，一定要把removeNode的返回值赋值给tree->head，比如tree->head = removeNode(1, tree->head);，这样新的根节点才能被正确引用。
• 修复removeNode的双节点逻辑：将removeNode(minNode->val, root->right)的返回值赋值给root->right，确保右子树中被删除的最小节点的父节点指针正确更新。
• 添加空指针保护：在多个函数中新增空指针检查，避免因访问空指针导致程序崩溃。

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