C - 使用递归创建二叉树时出现分段错误

Question

我试图在 C 中编写一个使用指针创建二叉树的简单程序，但我无法找到此代码的问题。我在第二次插入时收到分段错误。

程序输入五个数字，然后使用数组 input.Sample 运行 :

创建一个二叉树

这是程序的输出

Enter 5 elements :

45 78 89 32 46

In generateBST

In insert Going to right sub tree

In insert

Segmentation fault

请帮我解决这个错误。谢谢。

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

typedef struct node {
    int value;
    struct node * lst;
    struct node * rst;
}Node;

void printBST(Node *root){
    puts("In printBST");
    if(root == NULL){
        return;
    }
    printBST(root->lst);
    printf(" %d ", root->value);
    printBST(root->rst);
}

void insert(Node **root, int element){
    puts("In insert");
    if((*root)->value > element){
        puts("Going to left sub tree");
        insert(&(*root)->lst ,element);
    } else if ((*root)->value < element) {
        puts("Going to right sub tree");
        insert(&(*root)->rst ,element);
    } else {
        puts("Creating a new node to insert");
        Node * newNode = (Node*)malloc(sizeof(Node));
        newNode->value = element;
        newNode->lst = NULL;
        newNode->rst = NULL;
        (*root) = newNode;
    }
}

Node* generateBST(int *elements, int n){
    puts("In generateBST");
    int i =0;
    Node * root = NULL;
    root = (Node*)malloc(sizeof(Node));
    root->value = *(elements);
    root->lst = NULL;
    root->rst = NULL;
    for(i=1; i < n; i++){
        insert(&root, *(elements+i));
    }
    return root;
}

int main(){
    Node * root = NULL;
    int i = 0, element, *elements ;
    elements = (int*)malloc(sizeof(int)*5);
    puts("Enter 5 elements : ");
    fflush(stdin);
    for(i = 0; i < 5; i++){
        scanf("%d",&element);
        elements[i] = element;
    }
    root = generateBST(elements,5);
    printBST(root);
    //deallocBST(root);
    return 0;
}

Answer 1

在插入中，如果 *root 为空，则在取消引用 (*root)->value 时会出现分段错误。你需要处理这种情况：

void insert(Node **root, int element){
    puts("In insert");
    if (*root == null || (*root)->value == element) {
        puts("Creating a new node to insert");
        Node * newNode = malloc(sizeof(Node));
        newNode->value = element;
        newNode->lst = NULL;
        newNode->rst = NULL;
        (*root) = newNode;
    } else if((*root)->value > element){
        puts("Going to left sub tree");
        insert(&(*root)->lst ,element);
    } else {  /* (*root)->value < element */
        puts("Going to right sub tree");
        insert(&(*root)->rst ,element);
    }
}

Answer 2

刚刚在使用 gdb 时发现了您的问题。第 22 行有错误。问题是你没有检查 root 是否为空，这是插入第一个元素的问题。

通过 gdb 运行您的程序只需编译并运行使用：

g++ -g YourPorgram.cpp
gdb a.out
run

当程序停止时（段错误或其他问题）键入：

bt

C - 使用递归创建二叉树时出现分段错误

C - Segmentation Fault while Creating Binary Tree Using recursion

c

pointers

segmentation-fault

binary-search-tree