实现红黑树前置二叉树时触发Segmentation Fault (core dumped)求助

我正在尝试实现红黑树，打算先做一个叶子节点不存储内容的简单二叉树，再逐步添加红黑树的特性。但目前程序一直抛出**Segmentation Fault (core dumped)**错误，实在搞不清原因。

我的操作流程是：打开存储整数的文件，统计行数后创建对应大小的数组，把文件里的整数存入数组；接着创建根节点和它的两个叶子节点，结果在插入数组剩余元素的时候触发了段错误，我怀疑问题出在函数实现里。

程序代码 #

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
#include <string.h> 
#include <stdbool.h> 

typedef struct node { 
    unsigned long int val; 
    bool black; 
    struct node* parent; 
    struct node* lchild; 
    struct node* rchild; 
}mynode; 

mynode* createNode(unsigned long int ival, mynode* father); 
mynode* createLeaf(unsigned long int ival, mynode* father); 
mynode* search (unsigned long int ival, mynode *root); 
void insert ( unsigned long int ival, mynode *root); 

int main() { 
    mynode root; 
    mynode *rootptr; 
    mynode *leafptr; 
    FILE *fp; 
    int ch; 
    unsigned long long lines=0, i=0; 
    unsigned long *myArr; 
    unsigned long int ival; 

    fp = fopen("integers.txt","r"); 
    if(fp == NULL) { 
        printf("Error in opening file."); 
        return(-1); 
    } 

    while(!feof(fp)) { 
        ch = fgetc(fp); 
        if(ch == '\n') { 
            lines++; 
        } 
    } 
    lines++; 
    printf("lines = %lu", lines); 

    myArr = (unsigned long*)calloc(lines, sizeof(unsigned long)); 
    fseek(fp, 0, SEEK_SET); 

    while(!feof(fp)) { 
        fscanf(fp, "%lu,", &myArr[i] ); // des ta pos k giati tou input. 
        i++; 
    } 
    fclose(fp); 

    root.val = myArr[0]; 
    root.parent = NULL; 
    root.lchild = NULL; 
    root.rchild = NULL; 
    root.black = true; 
    rootptr = &root; 

    leafptr = createLeaf(rootptr->val, rootptr); 
    rootptr->lchild = leafptr; 
    leafptr = createLeaf(rootptr->val, rootptr); 
    rootptr->rchild = leafptr; 

    for(i=1; i<lines; i++) { 
        ival = myArr[i]; 
        insert(ival, rootptr); 
    } 

    return 0; 
} 

mynode* createNode(unsigned long int ival, mynode* father) { 
    mynode* nodeptr; 
    mynode node; 
    nodeptr = &node; 
    nodeptr->val = ival; 
    nodeptr->lchild = NULL; 
    nodeptr->rchild = NULL; 
    nodeptr->parent = father; 
    nodeptr->black = true; 
    return nodeptr; 
} 

mynode* createLeaf(unsigned long int ival, mynode* father) { 
    mynode* nodeptr; 
    mynode leaf; 
    nodeptr = &leaf; 
    nodeptr->val = ival; 
    nodeptr->lchild = NULL; 
    nodeptr->rchild = NULL; 
    nodeptr->parent = father; 
    nodeptr->black = true; 
    return nodeptr; 
} 

mynode* search (unsigned long int ival, mynode *rootptr) { 
    mynode* myptr; 
    myptr = rootptr; 
    while ( ( (myptr->lchild) != NULL) && ( (myptr->rchild) != NULL)) { 
        if ( ival < myptr->val) { 
            myptr = myptr->lchild; 
        } else { 
            myptr = myptr->rchild; 
        } 
    } 
    return myptr; 
} 

void insert (unsigned long int ival, mynode *root) { 
    mynode * current; 
    mynode * leafptr; 
    mynode * father; 
    unsigned long int max, min; 
    unsigned long int num; 

    current = search(ival, root); 
    num = current->val; 

    if((current->val) == ival) { 
        return ; 
    } else { 
        if(ival>(current->val)) { 
            max = ival; 
            min = current->val; 
        } else { 
            max = current->val; 
            min = ival; 
        } 

        father = current->parent; 
        current = createNode(min, father); 

        if(num == (father->lchild)->val) { 
            father->lchild = current; 
        } else { 
            father->rchild = current; 
        } 

        leafptr = createLeaf(min, current); 
        current->lchild = leafptr; 
        leafptr = createLeaf(max, current); 
        current->rchild = leafptr; 

        return ; 
    } 
} 

问题根源分析 #

最致命的错误出在createNode和createLeaf函数里：你在这两个函数中创建了栈上的局部变量（比如mynode node;和mynode leaf;），然后返回了它们的地址。栈上的变量会在函数执行完毕后被系统回收，后续再访问这些返回的指针，就变成了访问野指针，这必然会触发段错误。

除此之外，还有几个小问题可能会导致异常：

1. 使用while(!feof(fp))读取文件的方式有问题，会导致最后一行被多读一次，建议改成通过fscanf的返回值判断是否读取成功；
2. search函数的循环条件(myptr->lchild != NULL) && (myptr->rchild != NULL)可能不符合你的逻辑预期，比如如果某个节点只有一个子节点，循环会提前终止；
3. insert函数中if(num == (father->lchild)->val)的判断方式有风险，如果father->lchild是NULL，会直接触发段错误。

修复方案 #

首先优先修复最核心的野指针问题，把createNode和createLeaf改成用malloc动态分配内存：

mynode* createNode(unsigned long int ival, mynode* father) { 
    mynode* nodeptr = (mynode*)malloc(sizeof(mynode));
    if (nodeptr == NULL) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    nodeptr->val = ival; 
    nodeptr->lchild = NULL; 
    nodeptr->rchild = NULL; 
    nodeptr->parent = father; 
    nodeptr->black = true; 
    return nodeptr; 
} 

mynode* createLeaf(unsigned long int ival, mynode* father) { 
    mynode* leafptr = (mynode*)malloc(sizeof(mynode));
    if (leafptr == NULL) {
        perror("malloc failed");
        exit(EXIT_FAILURE);
    }
    leafptr->val = ival; 
    leafptr->lchild = NULL; 
    leafptr->rchild = NULL; 
    leafptr->parent = father; 
    leafptr->black = true; 
    return leafptr; 
}

然后再处理其他小问题：

• 修改文件读取逻辑，比如统计行数可以改成：

lines = 0;
char buf[1024];
while (fgets(buf, sizeof(buf), fp) != NULL) {
    lines++;
}

读取数组时改成：

i = 0;
while (fscanf(fp, "%lu,", &myArr[i]) == 1) {
    i++;
}

• 调整search函数的循环条件，确保能正确找到插入位置；
• 在insert函数中增加指针非空判断，避免访问NULL指针。

内容的提问来源于stack exchange，提问作者Βαγγέλης Μαργέτης