Segfault при доступе к узлам дерева двоичного поиска - PullRequest
Новая
       12

Segfault при доступе к узлам дерева двоичного поиска

0 голосов
/ 28 октября 2019

Я реализую простое двоичное дерево поиска в C со следующими структурами: 

typedef struct bstNode{
    double val;
    struct bstNode* left;
    struct bstNode* right; 
} Node;

typedef struct bsTree{
    Node* root;
    size_t size;
} BST;

, где BST* createTree(double val) возвращает структуру двоичного дерева поиска со следующей подпрограммой: 

BST* createTree(double val){
    Node* root = (Node*) malloc(sizeof(Node));
    root->val = val;
    root->right = NULL;
    root->left = NULL;
    BST* t = malloc(sizeof(BST));
    if(t == NULL){
        free(root);
        free(t);
        return NULL;
    }
    t->root = root;
    t->size = 1;
    return t;
}

Кроме того, я реализовал int insert(BST* tree, double in), который вставляет данное значение как узел в дерево двоичного поиска: 

int insert(BST* tree, double in){
    if(tree->root == NULL)  return -1;
    Node* curr = tree->root;

    while(curr!=NULL){
        if(curr->val<=in){
            curr = curr->right;
        }else{
            curr = curr->left;
        }
    }

    curr = (Node*) malloc(sizeof(Node));
    if(curr == NULL){
        printf("Could not create new node");
    }
    curr->val = in;
    curr->right = NULL;
    curr->left = NULL;
    tree->size = tree->size + 1;
    return 0;
}

Теперь, если я протестирую реализацию со следующим кодом: 

int main(){
    BST* tree = createTree(1.0);
    if(tree==NULL){
        printf("Tree could not be created");
        return -1;
    }

    insert(tree, 2.0);
    printf("%lf\n", tree->root->right->val);
    destroyTree(tree);

    return 0;
}

Я получаю ошибку сегментации, хотя я успешно создал curr внутри функции insert(). Я пробовал разные вещи, например, уже malloc'ing правый и левый узлы root заранее (в методе createTree()), но это тоже не сработало. Что я здесь не так делаю?

1 Ответ

1 голос
/ 29 октября 2019

Недавно созданный Node внутри insert не привязан к вашему дереву.

curr является локальной переменной, и когда вы изменяете ее с помощью curr = (Node*)malloc(sizeof(Node)), она просто изменяет значение этого указателя, но ни один из узлов в дереве не будет указывать на это значение.

ЛегкоЧтобы исправить это, создайте временный указатель, который указывает «родительский» узел, и добавьте одну переменную bool, которая указывает, какому узлу (левому или правому) родительского нового дочернего указателя следует назначить. 

int insert(BST* tree, double in){
    if(tree->root == NULL)  return -1;
    Node* curr = tree->root;

    Node* parent = NULL;      // added
    bool addToRight = false;  // added
    while(curr!=NULL){
        parent = curr;
        if(curr->val<=in){
            curr = curr->right;
            addToRight = true; // added
        }else{
            curr = curr->left;
            addToRight = false; // added 
        }
    }

    curr = (Node*) malloc(sizeof(Node));
    if(curr == NULL){
        printf("Could not create new node");
    }
    curr->val = in;
    curr->right = NULL;
    curr->left = NULL;

    if (addToRight)             // added
        parent->right = curr;
    else 
        parent->left = curr;

    tree->size = tree->size + 1;
    return 0;
}

Другое решение заключается в использовании Node**. Таким образом, вы можете сохранить адрес листа (влево или вправо) и установить для него значение указателя, возвращаемое из malloc. 

Node** t = NULL; // added
while(curr!=NULL){
    if(curr->val<=in){
        curr = curr->right;
        t = &(curr->right); // added
    }else{
        curr = curr->left;
        t = &(curr->left); // added
    }
}

curr = (Node*) malloc(sizeof(Node));
if(curr == NULL){
    printf("Could not create new node");
}
*t = curr; // added
curr->val = in;
curr->right = NULL;
curr->left = NULL;
...