C中二叉树minheap实现的各种问题

Question

我正在尝试使用 minheap 在 C 中实现二叉搜索树。我已经记下了基本代码，但我无法让它正常工作。根据构建消息，我的主要问题似乎是我比较指针和整数。由于此代码基于我在教科书和网上找到的各种解释，我不确定如何避免这种情况。

这是完整的代码（最终代码和工作代码 - 查看原始代码的编辑历史）：

#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.

看来我仍然需要排除从 "nothing" 到树根的连接。

printTree 我添加是为了调试目的，但似乎也有问题。

Answer 1

首先，当你有这样的编译器警告消息时，不要尝试执行。这意味着你显然会在某处发生内存泄漏。

你的问题实际上是你在这里对整数和指针进行比较：

(root->key == NULL)

根据你的结构，root->key是一个整数，看起来像你的节点数据。但是 NULL 正在用作未分配指针的引用。

您不必将密钥用作 "check" 即可知道您的节点是否空闲。树中的每个节点都已经分配了值。您最好遍历树直到到达 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);
}

Answer 2

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

C中二叉树minheap实现的各种问题

Various issues with binary tree minheap implementation in C

c

binary-search-tree

min-heap