Различные проблемы с реализацией minheap двоичного дерева в C

Я пытаюсь реализовать двоичное дерево поиска в C с помощью minheap. У меня есть основной код, но я не могу заставить его работать должным образом. Моя основная проблема, согласно сообщениям о сборке, заключается в том, что я сравниваю указатели и целые числа. Поскольку этот код основан на различных объяснениях, которые я нашел в своих учебниках и в Интернете, я не уверен, как этого избежать.

Вот полный код (окончательный и рабочий - см. Историю редактирования оригинала):

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

typedef struct TreeNode {
    int key;
    struct TreeNode* lChild;
    struct TreeNode* rChild;
} node;

node *createTree(int key) {

    node *root = malloc(sizeof(node));

    root->key = key;
    root->lChild = NULL;
    root->rChild = NULL;

    return(root);

}

void insert(node *root, int key) {

    if (root->key == -1)
        root->key = key;

    else if (key < root->key) {

        if (root->lChild != NULL)
            insert(root->lChild, key);

        else {
            root->lChild = malloc(sizeof(node));
            root->lChild->key = key;
            root->lChild->lChild = NULL;
            root->lChild->rChild = NULL;
        }
    }

    else if (key > root->key) {

        if (root->rChild != NULL)
            insert(root->rChild, key);

        else {
            root->rChild = malloc(sizeof(node));
            root->rChild->key = key;
            root->rChild->lChild = NULL;
            root->rChild->rChild = NULL;
        }
    }

}

void deleteTree(node *root) {

    if (root != NULL) {

        if (root->lChild != NULL)
            deleteTree(root->lChild);

        if (root->rChild != NULL)
            deleteTree(root->rChild);

        free(root);
    }

}

void printNode(node *root) {

    if (root->lChild != NULL) {

        printf("%d -- %d\n", root->key, root->lChild->key);

        if (root->rChild != NULL)
            printf("%d -- %d\n", root->key, root->rChild->key);

        printNode(root->lChild);
    }

    if (root->rChild != NULL) {

        if (root->lChild == NULL)
            printf("%d -- %d\n", root->key, root->rChild->key);

        printNode(root->rChild);
    }
}

void printTree(node *root) {

    printf("graph g {\n");

    printNode(root);

    printf("}\n");
}

void test() {

    // 1.
    node *root1 = createTree(-1);

    insert(root1, 4);
    insert(root1, 2);
    insert(root1, 3);
    insert(root1, 8);
    insert(root1, 6);
    insert(root1, 7);
    insert(root1, 9);
    insert(root1, 12);
    insert(root1, 1);
    printTree(root1);

    // 2.
    node *root2 = createTree(-1);

    insert(root2, 3);
    insert(root2, 8);
    insert(root2, 10);
    insert(root2, 1);
    insert(root2, 7);
    printTree(root2);

    // 3.
    deleteTree(root1);

    // 4.
    deleteTree(root2);

}

int main() {
    test();
}

Вот результат (окончательный и рабочий - см. Историю редактирования оригинала):

graph g {
4 -- 2
4 -- 8
2 -- 1
2 -- 3
8 -- 6
8 -- 9
6 -- 7
9 -- 12
}
graph g {
3 -- 1
3 -- 8
8 -- 7
8 -- 10
}

Process returned 1 (0x1)   execution time : 0.712 s
Press any key to continue.

Похоже, мне нужно исключить соединение из "ничего" с корнем дерева.

printTree Я добавил для целей отладки, но, похоже, с этим тоже есть проблемы.

Источник

2 ответа

Решение

Во-первых, когда у вас есть такие сообщения с предупреждением компилятора, не пытайтесь выполнить. Это означает, что у вас, очевидно, где-то утечка памяти

И ваша проблема заключается в том, что вы делаете сравнение между целым числом и указателем здесь:

(root->key == NULL)

Согласно вашей структуре, root->key является целым числом, выглядит как данные вашего узла. Но NULL используется для ссылки в качестве неназначенного указателя.

Вам не нужно использовать свой ключ в качестве "проверки", чтобы узнать, свободен ли ваш узел или нет. Каждый узел в дереве уже имеет назначенное значение. Вам лучше путешествовать по своему дереву, пока не достигнете NULL-узла, а затем выделить этот узел из его родительского. И это именно то, что вы делаете в своем heapify функция.

На самом деле, единственное, что вы должны сделать, это удалить insert функция, вызывающая напрямую heapify вместо.

У вас есть другая проблема здесь:

printf("key: %d, lChild key: %d, rChild key: %d\n", root->key, root->lChild->key, root->rChild->key);

if (root->lChild != NULL)
[...]

Вы печатаете данные в дочерних узлах, прежде чем проверять, есть ли дочерний объект вообще. Это большой потенциальный источник основных дампов.

Я рекомендую использовать рекурсивный алгоритм для вашего printNode что касается других ваших функций:

void printNode(node *root) {
    if (root->lChild != NULL) {
        printf("Left child: ");
        printf("%d -- %d\n", root->key, root->lChild->key);
        printNode(root->rChild);
    }
    if (root->rChild != NULL) {
        printf("Right child: ");
        printf("%d -- %d\n", root->key, root->rChild->key);
        printNode(root->rChild);
    }
}

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

node *createTree(int rootKey) {
    node *root;

    root = malloc(sizeof(node));
    if (root == NULL) return NULL; // Don't forget to check your malloc's return !
    root->key = rootKey;
    root->lChild = NULL;
    root->rChild = NULL;

    return (root);
}
Источник

В функции printTree есть проблема:

printf("key: %d, lChild key: %d, rChild key: %d\n", root->key, root->lChild->key, root->rChild->key);

Вы не проверяете, имеют ли root->lChild или root->rChild значение NULL. Это приводит к ошибке сегментации. Если вы используете Linux, я бы порекомендовал использовать valgrind. Это поможет вам отладить программы на C и сэкономит вам много времени.

Источник
Другие вопросы по тегам