1

I'm trying to implement a binary search tree in C by using minheap. I've got the basic code down but I cannot get it to work properly. My main problem, according to the build messages, seem to be that I compare pointers and integers. As this code is based off of various explanations that I found in my textbooks and online, I'm not sure how to avoid that.

Here is the complete code (final and working - see edit history for original):

#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();
}

Here is the output (final and working - see edit history for original):

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.

It looks like I need to exclude the connection from "nothing" to the root of the tree still.

printTree I added for debugging purposes but there seem to be problems with it as well.

4

2 回答 2

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);
}
于 2015-04-12T12:52:24.117 回答
-1

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 程序，并为您节省大量时间。

于 2015-04-12T12:59:31.973 回答