如何实现字符串版二叉搜索树？C代码显示崩溃求排查

你的程序崩溃核心原因是把字符串当成单个字符处理，加上内存操作的错误，导致访问非法内存。下面我把关键问题和修复步骤逐一拆解：

核心错误点 #

• 节点数据类型不匹配：你的struct node里data是char类型，只能存单个字符，但你要存储的是字符串（比如名字），必须改成char*。
• 变量a的scanf使用错误：scanf("%s",&a)是错的——a已经是指向malloc内存的指针，直接传a就行，&a是取指针本身的地址，会导致写入错误的内存区域，破坏程序结构。
• 字符串比较错误：直接用<或==比较字符串是在比较指针地址，不是字符串内容，必须用strcmp函数。
• 节点内存分配错误：创建节点时，要给data单独分配内存存储字符串，不能直接赋值指针（否则所有节点都会指向a的内存，a被覆盖后所有节点数据都会变）。
• display函数的格式符错误：原来用%s打印char类型的data，会导致非法内存访问崩溃，改成char*后才能用%s。

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <conio.h> // 若使用getch需要此头文件，也可替换为getchar

struct node {
    char *data; // 修改为char*存储字符串
    struct node *left;
    struct node *right;
};

struct node *root;
struct node *newnode(char *name);
struct node *find(char *key);
struct node *insert(char *name);
void display(struct node *ptr);
bool rm(char *key);
struct node *find_left_most(struct node *rt);
struct node *find_right_most(struct node *rt);

int main(void) {
    char ch;
    char *a = malloc(100 * sizeof(char));
    if (!a) { // 检查内存分配是否成功
        puts("Memory allocation failed");
        exit(1);
    }
    struct node *new_node;
    root = NULL;

    while (1) {
        printf("\n0->EXIT 1->Add name : 2->Search name : ");
        printf("3->Delete name : 4->BST display :\n");
        ch = getch();
        printf("\n"); // 换行优化输入显示

        switch(ch) {
            case '0': 
                free(a); // 先释放a的内存
                exit(0);
            case '1': 
                printf("Enter name: "); 
                scanf("%s", a); // 直接传指针a，无需取地址
                new_node = insert(a);
                if (root == NULL) root = new_node;
                if (new_node == NULL) puts("No memory available"); 
                break;
            case '2': 
                printf("Enter name to search: "); 
                scanf("%s", a);
                new_node = find(a);
                if (new_node != NULL) printf("Found: %s\n", new_node->data);
                else printf("Name not found\n"); 
                break;
            case '3': 
                printf("Enter name to delete: "); 
                scanf("%s", a);
                if (rm(a)) printf("Deleted successfully\n");
                else printf("Name not found\n");
                break;
            case '4': 
                printf("BST in-order display: ");
                display(root); 
                puts(""); 
                break;
            default: puts("Invalid input, try again"); break;
        }
        // 清空输入缓冲区，避免getch读取到残留的换行符
        while (getchar() != '\n');
    }

    return 0;
}

struct node *newnode(char *name) {
    struct node *neos = malloc(sizeof(struct node));
    if (!neos) return NULL;

    // 为字符串分配独立内存并拷贝内容，strdup等价于malloc+strcpy
    neos->data = strdup(name);
    if (!neos->data) {
        free(neos); // 字符串分配失败时，释放已分配的节点内存
        return NULL;
    }
    neos->left = NULL;
    neos->right = NULL;
    return neos;
}

void display(struct node *ptr) {
    if (ptr == NULL) return;
    display(ptr->left);
    printf("%s ", ptr->data); // 现在data是char*，可正常用%s打印
    display(ptr->right);
}

struct node *find(char *key) {
    struct node *current = root;
    while (current != NULL) {
        int cmp = strcmp(key, current->data);
        if (cmp == 0) {
            return current; // 找到匹配节点
        } else if (cmp < 0) {
            current = current->left; // 目标更小，遍历左子树
        } else {
            current = current->right; // 目标更大，遍历右子树
        }
    }
    return NULL; // 未找到目标
}

struct node *insert(char *name) {
    struct node *current = root;
    struct node *parent = NULL;
    struct node *ptr = newnode(name);
    if (!ptr) return NULL;

    if (root == NULL) {
        return ptr;
    }

    while (1) {
        parent = current;
        int cmp = strcmp(name, current->data);
        if (cmp < 0) { // 插入左子树
            current = current->left;
            if (current == NULL) {
                parent->left = ptr;
                return ptr;
            }
        } else { // 插入右子树（相等时默认放右侧，可按需调整）
            current = current->right;
            if (current == NULL) {
                parent->right = ptr;
                return ptr;
            }
        }
    }
}

bool rm(char *key) {
    struct node *current = root;
    struct node *parent = root;
    bool isLeftChild = true;

    // 定位要删除的节点
    while (current != NULL) {
        int cmp = strcmp(key, current->data);
        if (cmp == 0) {
            break; // 找到目标节点
        }
        parent = current;
        if (cmp < 0) {
            isLeftChild = true;
            current = current->left;
        } else {
            isLeftChild = false;
            current = current->right;
        }
    }
    if (current == NULL) return false; // 未找到目标

    // 情况1：叶子节点
    if (current->left == NULL && current->right == NULL) {
        if (current == root) root = NULL;
        else if (isLeftChild) parent->left = NULL;
        else parent->right = NULL;
    }
    // 情况2：仅左子树存在
    else if (current->right == NULL) {
        if (current == root) root = current->left;
        else if (isLeftChild) parent->left = current->left;
        else parent->right = current->left;
    }
    // 情况3：仅右子树存在
    else if (current->left == NULL) {
        if (current == root) root = current->right;
        else if (isLeftChild) parent->left = current->right;
        else parent->right = current->right;
    }
    // 情况4：左右子树都存在
    else {
        struct node *successor = find_left_most(current->right);
        struct node *succ_right = successor->right;
        struct node *current_left = current->left;

        // 将后继节点从原位置移除
        struct node *succ_parent = current->right;
        if (succ_parent == successor) {
            succ_parent->left = succ_right;
        } else {
            while (succ_parent->left != successor) {
                succ_parent = succ_parent->left;
            }
            succ_parent->left = succ_right;
        }

        // 用后继节点替换当前节点
        successor->left = current_left;
        successor->right = current->right;

        if (current == root) root = successor;
        else if (isLeftChild) parent->left = successor;
        else parent->right = successor;
    }

    // 先释放节点存储的字符串内存，再释放节点本身
    free(current->data);
    free(current);
    return true;
}

struct node *find_left_most(struct node *rt) {
    if (rt == NULL) return NULL;
    while (rt->left != NULL) {
        rt = rt->left;
    }
    return rt;
}

struct node *find_right_most(struct node *rt) {
    if (rt == NULL) return NULL;
    while (rt->right != NULL) {
        rt = rt->right;
    }
    return rt;
}

额外说明 #

1. 内存管理：使用strdup为节点的字符串分配独立内存，删除节点时先释放data再释放节点，避免内存泄漏。
2. 输入处理：添加了输入缓冲区清空逻辑，避免getch读取到scanf残留的换行符，导致菜单选择异常。
3. 错误检查：增加了内存分配的失败判断，提升程序健壮性。
4. 字符串比较：全部替换为strcmp函数，确保比较的是字符串内容而非指针地址。

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