Поиск функции элемента BST в C - PullRequest
Новая
       9

Поиск функции элемента BST в C

0 голосов
/ 16 октября 2018

я думаю, что это должно быть простой проблемой, но я не знаю, что не так ..

GDB говорит 

Program received signal SIGSEGV, Segmentation fault.
0x000055555555543e in searchNode (root=0x0, X=1) at problem1.c:40
40      while(cursor->value != X || cursor != NULL)

функция вставки и поиска 

typedef struct TreeNode
{
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
}   tree;

tree *insert(tree *root, int X)
{
    tree *cursor = root;
    tree *parent;

    while(cursor != NULL)
    {
        parent = cursor;
        if(X >= cursor->value)
            cursor = cursor->right;
        else
            cursor = cursor->left;
    }
    cursor = (tree *)malloc(sizeof(tree));
    cursor->value = X;
    cursor->left = cursor->right = NULL;
    cursor->parent = parent;
        return cursor;  
}

tree *searchNode(tree *root, int X)
{
    tree *cursor = root;

    while(cursor->value != X || cursor != NULL)
    {
        if(X >= cursor->value)
            cursor = cursor->right;
        else
            cursor = cursor->left;
    }

    if(cursor == NULL)
        return NULL;

    else if(cursor->value == X)
        return cursor;
}

main function 

int main()
{
    tree *root = (tree *)malloc(sizeof(tree));
    root = NULL;

    insert(root, 10);
    insert(root ,20);
    insert(root, 5);
    insert(root, 1);
    insert(root, 15);
    insert(root, 20);
    insert(root, 30);
    insert(root, 100);
    insert(root, 40);
    insert(root, 50);

    node = searchNode(root, 1);
}

Насколько я знаю, ошибка сегментации чаще всего возникает, когда я ссылаюсь на NULL-указатель, но я не думаю, что функция поиска неправильная.Я думаю, что я сделал ошибки в функции вставки или инициализации корня дерева, но я не знаю, что не так ..

Ответы [ 2 ]

0 голосов
/ 16 октября 2018

Проблема с вашей функцией insert заключается в том, что у нее нет средств для обновления значения root.Вы возвращаете новый конечный узел, но это не очень полезно для отслеживания того, каким может быть root.

Чтобы иметь возможность изменить root, вы должны передать указатель на него,как например: 

insert(&root, 10);

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

tree *insert(tree **root, int X)
{
    if(*root == NULL)
    {
        *root = (tree *)malloc(sizeof(tree));
        (*root)->value = X;
        (*root)->left = (*root)->right = (*root)->parent = NULL;
        return(*root);
    }
    else
    {
        tree *ret;
        if(X >= (*root)->value)
        {
            ret=insert(&(*root)->right, X);
            (*root)->right->parent=*root;
        }
        else
        {
            ret=insert(&(*root)->left, X);
            (*root)->left->parent=*root;
        }
        return ret;
    }
}

Итак, в первый разВы называете это, это заполнит root для вас.Во второй раз он передаст указатель на root->right, который станет новым root в вашей функции insert, и, поскольку это NULL, он будет создан.А затем для полноты картины он обновляет связь parent.

0 голосов
/ 16 октября 2018

Из любопытства я заглянул в код.

Не думаю, что функция поиска неправильная

Я не согласен!

Посмотрите на эту строку кода: 

while(cursor->value != X || cursor != NULL)

Что произойдет, если cursor будет NULL?Доступ к cursor->value, который является Неопределенное поведение (потому что доступ к NULL не разрешен).Это стоит Segmentation fault.

Лучше было бы: 

while (cursor != NULL && cursor->value != X)

или короче: 

while (cursor && cursor->value != X)

Отзыв фрагмента OP из gdb 

Program received signal SIGSEGV, Segmentation fault.
0x000055555555543e in searchNode (root=0x0, X=1) at problem1.c:40
40      while(cursor->value != X || cursor != NULL)

(что я не осознал с первого взгляда) для меня это звучит очень разумно.

Согласно (root = 0x0), searchNode(), кажется, призван к пустому дереву (root is NULL).Следовательно, tree *cursor = root; инициализирует cursor с указателем NULL (и остальным выше).

...