c - 释放了 BST 但仍然出现内存泄漏 C

Question

我知道有很多人问这个问题，我已经浏览了这些帖子上的所有答案，但仍然没有解决我的问题。 我正在尝试释放 C 中的二叉搜索树。我编写了用于释放内存的代码。以下是 Insert、createNode 和 freeNode 的代码:

插入

    Node *insertNode(Node *root, int value) {
    /*
        Insertion of node in Binary Search Tree. The new node must be added in the correct subtree (either left or right).
        If the value is less than the root value then it should be insert in the left subtree. If it's bigger then it should be
        on the right.
    */
    if (root == NULL) {
        //if this is the first node then return its value.
        root = createNode(value);
        return root;
    }
    //on the left subtree
    if (value < root->data) {
        //recurse down the left subtree
        root->left = insertNode(root->left, value);
    } else if (value > root->data) {
        //recurse down the right subtree otherwise.
        root->right = insertNode(root->right, value);
    }

    return root;
}

免费树

void freeSubtree(Node *N) {
   if(N == NULL) {
       return;
   } else{
       freeSubtree(N->right);

       freeSubtree(N->left);
       N->right = NULL;
       N->left = NULL;
   }
       free(N);

}

创建新节点

Node *createNode(int value) {
    //allocate space for the node.
    Node *newNode = (Node *) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

我不知道为什么仍然存在内存泄漏，因为我已经释放了所有节点。我看不出我哪里错了。

任何帮助将不胜感激!

编辑 以下是 valgrind 报告的内存泄漏 Valgrind memory leak error

Answer 1

我根据问题中的内容组装了这段代码。我已经清理了您的三个函数，添加了类型定义、标题、树打印函数和 main() 程序。我在 Valgrind 下运行了它很多次，在 main() 程序中使用了不同的配置 - 乘法、加法和模运算中的不同数字，以及树构建的不同顺序，并构建一棵树而不是三个等等。这些都不会引起内存泄漏。

/* SO 5495-1700 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node Node;

struct Node
{
    int data;
    Node *left;
    Node *right;
};

static Node *createNode(int value);
static void freeSubtree(Node *node);
static Node *insertNode(Node *root, int value);

Node *insertNode(Node *root, int value)
{
    if (root == NULL)
        root = createNode(value);
    else if (value < root->data)
        root->left = insertNode(root->left, value);
    else if (value > root->data)
        root->right = insertNode(root->right, value);
    return root;
}

void freeSubtree(Node *N)
{
    if (N == NULL)
        return;
    freeSubtree(N->right);
    freeSubtree(N->left);
    N->right = NULL;
    N->left = NULL;
    free(N);
}

Node *createNode(int value)
{
    Node *newNode = (Node *) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

static void printValueIndented(int level, int value)
{
    for (int i = 0; i < level; i++)
        fputs("    ", stdout);
    printf("%d\n", value);
}

static void printTree(const char *tag, Node *root, int level)
{
    if (root == NULL)
        return;
    if (level == 0 && tag != NULL)
        printf("%s\n", tag);
    printValueIndented(level, root->data);
    printTree(tag, root->left, level + 1);
    printTree(tag, root->right, level + 1);
}

int main(void)
{
    Node *root = 0;
    srand(time(0));
    for (int i = 0; i < 20; i++)
        root = insertNode(root, i);
    printTree("Sequence", root, 0);
    freeSubtree(root);
    root = 0;
    for (int i = 0; i < 20; i++)
        root = insertNode(root, rand() % 53);
    printTree("Random", root, 0);
    freeSubtree(root);
    root = 0;
    for (int i = 0; i < 20; i++)
        root = insertNode(root, (13 * i + 7) % 47);
    printTree("Computed", root, 0);
    freeSubtree(root);
    return 0;
}

一个运行示例:

Sequence
0
    1
        2
            3
                4
                    5
                        6
                            7
                                8
                                    9
                                        10
                                            11
                                                12
                                                    13
                                                        14
                                                            15
                                                                16
                                                                    17
                                                                        18
                                                                            19
Random
4
    51
        24
            17
                16
                    7
            30
                32
                    31
                    41
                        34
                            36
                                39
                        45
                            43
Computed
7
    4
        1
        6
    20
        12
            9
            17
                14
                19
        33
            25
                22
                30
                    27
            46
                38
                    35
                    43
                        40

因此，尚不清楚您的代码如何触发内存泄漏。如果您仍然遇到泄漏，那么您需要显示生成它的确切代码(创建 MCVE - Minimal, Complete, Verifiable Example )并在您的(更新的)问题中显示 Valgrind 输出。