Ошибка сегментации в реализации двоичного дерева

Question

Я заранее извиняюсь за то, как долго исходный код на этом. Я не совсем уверен, где я ошибаюсь. Я написал реализацию двоичного дерева и некоторые функции для обхода дерева. Добавление одного элемента в дерево работает, но при добавлении нескольких причин возникает ошибка сегментации. DDD перечисляет несколько функций в backtrace: named, addToTree и isEmpty.

Программа охватывает три исходных файла (извините).

/*----------------------------------Tree.h----------------------------------*/ 

#ifndef TREE 
#define TREE 

#define MAXHEIGHT 4 

typedef struct cat{ 
    char *name; 
    int age; 
}Item; 

typedef struct node{ 
    Item thing; 
}Node; 

typedef struct tree{ 
    Node *root; 
    struct tree *left, *right; 
    int leafcount; 
}Tree; 

void initializeTree(Tree *); 
void closeTree(Tree *); 
int isEmpty(const Tree *); 
int isFull(const Tree*); 
Tree *searchTree(Item *thing, Tree *t, int (*)(const Item *, const Item *)); 
int addToTree(Item *, Tree *, int (*)(const Item *, const Item *)); 
int removeFromTree(Item *, Tree *); 

int itemComp(const Item *, const Item *); 

#endif 

/*----------------------------------Tree.c----------------------------------*/ 

#include "Tree.h" 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 

Node *copyToNode(Item *); 

/*Definition: Tree 
    Node *root; 
    int leafcount; */ 

Node *copyToNode(Item *thing){ 
    Node *tmp = malloc(sizeof(Node)); 
    if(tmp == NULL) 
     return tmp; 
    tmp->thing = *thing; 
    return tmp; 
} 

void initializeTree(Tree *t){ 
    t->root = NULL; 
    t->right = t->left = NULL; 
    t->leafcount = 0; 
} 

int isEmpty(const Tree *t){ 
    return t->root == NULL; 
} 

int isFull(const Tree *t){ 
    return t->leafcount == (int)pow(2,MAXHEIGHT) - 1; 
} 

int addToTree(Item *thing, Tree *t, int (*fp)(const Item *, const Item *)){ 
    if(isFull(t)) 
     return 0; 

    if(isEmpty(t)){ 
     Node *current = copyToNode(thing); 
     if(current == NULL){ 
      puts("Couldn't copy to tree!"); 
      return 0; 
     } 
     t->root = current; 
     t->leafcount++; 
     return 1; 
    } 

    if(fp(thing, &t->root->thing) <= 0) 
     return addToTree(thing, t->left, fp); 
    else 
     return addToTree(thing, t->right, fp); 
} 

Tree *searchTree(Item *thing, Tree *t, int (*fp)(const Item *, const Item *)){ 
    int temp; 

    if(t->root == NULL) 
     return NULL; 
    else if((temp = fp(&t->root->thing, thing)) == 0) 
     return t; 
    else if(temp = -1) 
     return searchTree(thing, t->left, fp); 
    else 
     return searchTree(thing, t->right, fp); 
} 


int removeFromTree(Item *thing, Tree *t){ 
    /*Tree *tmp = searchTree(thing, t); 
    Not finished*/ 
} 

void closeTree(Tree *t){ 
    return; 
} 

    /*------------------------------TreeDriver.c-------------------------------*/ 
#include "Tree.h" 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define MAXNAME 30 
int promptUser(void); 
int itemComp(const Item *, const Item *); 
Item * createUserItem(); 

int main(){ 
    int userChoice; 
    Item * userItem = NULL; 
    Tree userTree; 

    initializeTree(&userTree); 

    do{ 
     userChoice = promptUser(); 
     switch(userChoice){ 
      case 1: 
       puts("Enter cat information to add"); 
       userItem = createUserItem(); 
       if(addToTree(userItem, &userTree, itemComp)) 
        puts("Cat successfully added!"); 
       else 
        puts("Could not add cat!"); 
       break; 
      case 2: 
       puts("Enter cat information to search for"); 
       userItem = createUserItem(); 
       if(searchTree(userItem, &userTree, itemComp)) 
        puts("Cat found!"); 
       else 
        puts("Cat not found!"); 
       break; 
      case 3: 
       if(isEmpty(&userTree)) 
        puts("Tree is empty!"); 
       else 
        puts("Tree is not empty!"); 
       break; 
      case 4: 
       if(isFull(&userTree)) 
        puts("Tree is full!"); 
       else 
        puts("Tree is not full!"); 
       break; 
      case 0: 
       break; 
      default: 
       puts("Not an option!"); 
       break; 
     } 

    }while(userChoice); 

} 

int itemComp(const Item *thing_one, const Item *thing_two){ 
    int comparison; 

    if(comparison = strcmp(thing_one->name, thing_two->name)) 
     return comparison; 

    return !(thing_one->age == thing_two->age); 
} 

int promptUser(){ 
    int tmp; 

    puts("--------MENU---------"); 
    puts("1. Create cat"); 
    puts("2. Search for cat"); 
    puts("3. Check empty"); 
    puts("4. Check full"); 
    puts("0. Quit"); 

    scanf("%d", &tmp); 
    while(getchar() != '\n') 
     ; 

    return tmp; 
} 

Item * createUserItem(){ 
    Item *tmp = malloc(sizeof(Item)); 
    static char namebuf[MAXNAME]; 

    printf("Enter cat name: "); 
    if(fgets(namebuf, MAXNAME, stdin) == NULL) 
     return NULL; 

    tmp->name = malloc(strlen(namebuf)); 
    strcpy(tmp->name, namebuf); 

    printf("Enter cat age:\t"); 
    scanf("%d", &tmp->age); 

    while(getchar() != '\n') 
     ; 

    return tmp; 
} 

Я не совсем уверен, как интерпретировать обратную трассировку отладчика в любом случае. Где я неправ? Может ли это иметь какое-то отношение к тому, как я обработал создание фиктивного элемента для ввода пользователя в файл драйвера? Я не думаю, что я справился с этим (или остальной частью этой программы в этом отношении) очень хорошо.

Благодаря

Answer 1

Отказ от ответственности: Поскольку вы указали, что вы думаете, что ошибка лежит в пределах вашей addToTree функции я не смотрел нигде на наличие ошибок (кроме ваших определений структуры).

---

У вас есть две ошибки в вашей функции addToTree. Первое, что вы неправильно обрабатываете leafcount. Вы обнаружите, что это неверно, когда вы нажимаете узлы на свое дерево (мое решение ниже не исправляет это). Во-вторых, вам нужно передать двойной указатель на struct tree (или Tree), прохождение одного указателя не позволит вам вставлять в пустое дерево, так как вы проходите NULL.

Единственная причина, по которой не работает первая вставка, а также исходящие, состоит в том, что вы уже создали узел (тогда как если вы использовали структуру обертки, это должно быть NULL).

Чтобы исправить вторую ошибку, выполните следующие действия:

int addToTree(Item *thing, Tree **t, int (*fp)(const Item *, const Item *)) { 
    if(isFull(*t) == true) return 0; 

    if(isEmpty(*t) == true) { 
     Node *current = copyToNode(thing); 

     if(current == NULL) { 
      puts("Couldn't copy to tree!"); 

      return 0; 
     } 

     (*t) = current; 

     return 1; 
    } 

    if(fp(thing, t->root->thing) <= 0) 
     return addToTree(thing, &((*t)->left), fp); 
    else 
     return addToTree(thing, &((*t)->right), fp); 
} 

Помимо: Я бы также рассмотреть вопрос о именовании структуры по-разному. Структура Node и Tree вводят в заблуждение, Node должны стать Item и Tree должны стать BstNode (или какой-либо схемы именования вы считаете нужным по линии этого), то есть структура обертку под названием BstTree, которая определяется следующим образом:

struct BstTree { 
    struct Tree *root; 
    int height; 
}; 

... где root указывает на корень Node и height - это высота двоичного дерева поиска. Это не только улучшит ваши намерения, но и упростит вашу реализацию.