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

Question

Я не могу понять, как правильно это выполнить, дает ошибку сегментации. Ниже приведен фрагмент кода. Можешь ли вы смотреть на голове тоже, я не уверен, если это правильный путь инициализации головы до нуля в другом файл, он выполняется следующим образом:

Table tb ; 
tb= initialise_table (table_size); 
tb = insert(text_words,tb); 

//these 3 typedef declarations are in a "some.h" file  
typedef struct node * tree_ptr; 
typedef char* Key_Type; 
typedef struct table* Table; 
struct node { 
    Key_Type element; 
    tree_ptr left; 
    tree_ptr right; 
}; 

struct table { 
    tree_ptr head; 
}; 

Table init_table() { 

    Table head = NULL; 

} 
Table insert(Key_Type key ,Table temp) { 
    tree_ptr t = (tree_ptr)malloc(sizeof(tree_ptr)); 
    t->element = key; 
    // t->left = t->right = NULL; 
    if (temp->head==NULL) { 
     temp = (Table)malloc (sizeof (Table)); 
     temp->head = t; 
     printf("empty tree "); 
    }  
    else {   
     temp = insert(t->element,temp); 
     printf("inserted into "); 
    } 

    return temp; 
    printf("wowo!"); 
} 

Answer 1

Вот одна из основных проблем:

tree_ptr t = (tree_ptr) malloc(sizeof(tree_ptr)); 

должно быть:

tree_ptr t = (tree_ptr) malloc(sizeof(struct node)); 

Ваш код фактически не выполняет двоичный поиск. Действительно, он просто бесконечно рекурсивно создает новые узлы. Попробуйте что-нибудь еще, как это:

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

typedef struct Node 
{ 
    char  *element; 
    struct Node *left; 
    struct Node *right; 

} Node; 

typedef struct 
{ 
    Node *root; 
    size_t size; 

} Tree; 

void Tree_init(Tree *t); 
Node *Tree_insert(Tree *t, const char *key); 
void Tree_insert_r(Node *subtree, Node *n, size_t size); 
void Tree_pre_order_r(Node *subtree); 

void Tree_init(Tree *t) 
{ 
    t->root = NULL; 
    t->size = 0; 
}  

Node *Tree_insert(Tree *t, const char *key) 
{ 
    Node *ret = (Node*) malloc(sizeof(Node)); 

    if (ret) 
    { 
    ret->left = ret->right = NULL; 

    if ((ret->element = strdup(key))) /* make a copy of key */ 
    { 
     if (NULL != t->root) 
     Tree_insert_r(t->root, ret, t->size); 
     else 
     t->root = ret; 

     ++t->size; 
    } 
    else 
    { 
     free(ret); 
     ret = NULL; 
    } 
    } 

    return ret; 
} 

void Tree_insert_r(Node *subtree, Node *n, size_t size) 
{ 
    int cmp = strcmp(n->element, subtree->element); 

    if (cmp < 0 || (cmp == 0 && size % 2 == 0)) 
    { 
    if (NULL != subtree->left) 
     subtree = subtree->left; 
    else 
    { 
     subtree->left = n; 
     return; 
    } 
    } 
    else 
    { 
    if (NULL != subtree->right) 
     subtree = subtree->right; 
    else 
    { 
     subtree->right = n; 
     return; 
    }  
    } 

    Tree_insert_r(subtree, n, size); 
} 

void Tree_pre_order_r(Node *subtree) 
{ 
    if (NULL == subtree) 
    return; 

    fprintf(stdout, "'%s'\n", subtree->element); 

    Tree_pre_order_r(subtree->left); 
    Tree_pre_order_r(subtree->right); 
} 

int main() 
{ 
    Tree t; 

    Tree_init(&t); 
    Tree_insert(&t, "Hello"); 
    Tree_insert(&t, "World!"); 
    Tree_insert(&t, "etc."); 

    Tree_pre_order(t.root); 

    return 0; 
} 

Answer 2

Основная проблема заключается в коде, который вы говорите, используется для вызова функции:

Table tb; 

tb = insert(text_words, tb); 

Вы имеете неинициализированный указатель, tb, который вы передаете к функции. Внутри функции, у вас есть:

Table insert(Key_Type key, Table temp) 
{ 
    tree_ptr t = (tree_ptr)malloc(sizeof(*t)); // Fixed size 
    t->element = key; 
    // t->left = t->right = NULL; 
    if (temp->head==NULL) 
    { 

Вы поэтому доступ (разыменования) неопределенный указатель, и ваша программа рушится.

Вы должны, я полагаю, инициализировать вашу таблицу с помощью table_init(), но эта функция на самом деле не помогает. Он определяет и инициализирует локальную переменную, но ничего не возвращает, хотя обещает это сделать.

См. Is it a good idea to typedef pointers? Короткий ответ: «Нет, это обычно не очень хорошая идея».

У вас еще есть проблемы, даже если вы исправить код вызова, как это (необходимым, но не достаточным шагом):

Table tb = NULL; 
tb = insert(text_words, tb); 

или, может быть:

Table tb = init_table(); 
tb = insert(text_words, tb); 

но вы должны серьезно модернизированную версию из init_table(), таких как:

Table init_table(void) 
{ 
    Table root = malloc(sizeof(*head)); 
    root->head = NULL; 
    return root; 
} 

Ваш код в insert() должен убедиться, что он не разыскивает нулевой указатель (вместо неопределенного указателя).

Table insert(Key_Type key, Table root) 
{ 
    tree_ptr t = (tree_ptr)malloc(sizeof(*t)); // Fixed size 
    t->element = key; 
    t->left = t->right = NULL; 
    if (root == NULL) 
    { 
     root = init_table(); 
     root->head = t; 
    } 
    else 
    { 
     … 
    } 
    return root; 
} 

Учитывая Key_Type в маскировать char *, вам, возможно, придется пересмотреть, как вы сохраните ключи в древовидной структуре; вам может понадобиться использовать strdup() для копирования данных. Невозможно сказать точно, не видя, как вы управляете строками, которые вы передаете функции insert(). Можно просто сохранить указатель, если вызывающий код гарантирует, что новый указатель будет передаваться каждый раз. OTOH, если один и тот же указатель передается каждый раз, вам обязательно нужно скопировать данные, и использование strdup() - разумный способ сделать это. Обратите внимание, что strdup() является стандартным для POSIX; он не является частью стандарта C.