为什么我的c代码检查二叉搜索树是否完整（使用数组进行检查）根据valgrind检查会导致内存泄漏问题

Question

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

typedef struct node {
    int value;
    struct node* left;
    struct node* right;
}node;


node* createNode(int n) {
    node* new = (node*)malloc(sizeof(node));
    new->value = n;
    new->left = NULL;
    new->right = NULL;

    return new;
}


void insert(node** root, int num) {
    if (*root == NULL) {
        node* newNode = createNode(num);
        *root = newNode;
    }
    else {
        node* newNode = createNode(num);
        if (newNode) {
            if ((*root)->value > num) {
                insert(&(*root)->left, num);
            }
            else if ((*root)->value < num) {
                insert(&(*root)->right, num);
            }
        }
    }
}


void BFSinsert(node* currentNode, int* array, int i) {
    if (!currentNode) {
        array[i] = -1;  // to indicate that it's empty
        return;
    }
    BFSinsert(currentNode->left, array, 2*i+1);
    BFSinsert(currentNode->right, array, 2*i+2);
    array[i] = currentNode->value;
}


int isCompleteBTree(int arr[], int n) {
    for (int i = 0; i <= n / 2 - 1; i++) {
        if (arr[i] == -1) return 0;  // Found a NULL node
        if (2 * i + 1 >= n || arr[2 * i + 1] == -1) return 0;  
        if (2 * i + 2 >= n || arr[2 * i + 2] == -1) return 0;
    }
    return 1;
}


int countNodes(node* root) {
    if (root == NULL) return 0;
    else return 1 + countNodes(root->left) + countNodes(root->right);
}


void freeTree(node* node) {
    if (!node) return;
    if (node->left) freeTree(node->left);
    if (node->right) freeTree(node->right);
    free(node);
}


int main (void) {
    node* root = NULL;
    insert(&root, 6);
    insert(&root, 4);
    insert(&root, 8);
    insert(&root, 3);
    insert(&root, 5);
    insert(&root, 7);
    insert(&root, 9);


    int nodeCount = countNodes(root);
    int* array = (int*)malloc(100 * sizeof(int));

    BFSinsert(root, array, 0);

    printf("Array contents: ");
    for (int i = 0; i < nodeCount; i++) {
        if (array[i] == -1) nodeCount ++;  // nodeCount doesn't count NULL nodes, but array put -1 for empty nodes in the lowest level
        printf("%d ", array[i]);
    }
    printf("\n");

    if (isCompleteBTree(array, nodeCount)) printf("The tree is complete.\n");
    else printf("The tree is incomplete.\n");

    freeTree(root);
    free(array);

    return 0;
}

我知道有更好的方法来检查二叉搜索树是否完整，但这就是我要求使用的方式（像广度优先搜索类型的顺序填充的数组）我认为代码应该释放所有分配的内存。但是当使用 valgrind 检查它时，它显示有 240 字节的明确丢失。

我试图找到我动态分配内存的问题，是否存在任何逻辑问题。我想没有。

Answer 1

您的

insert

功能是：

void insert(node** root, int num) {
    if (*root == NULL) {
        node* newNode = createNode(num);
        *root = newNode;
    }
    else {
        node* newNode = createNode(num);    <---- LOOK HERE
        if (newNode) {
            if ((*root)->value > num) {
                insert(&(*root)->left, num);
            }
            else if ((*root)->value < num) {
                insert(&(*root)->right, num);
            }
        }
    }
}

请注意，我在

<---- LOOK HERE

 行添加了 

node* newNode = createNode(num);

现在的问题是：

你如何处理这个新的

malloc

节点？

好的，您将其保存在

newNode

中，但是您如何处理

newNode

呢？

什么都没有！！就这样丢了。

所以你泄漏了内存。

要修复它，似乎您只想删除该行（以及以下

if

）

Answer 2

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

typedef struct node {
    int value;
    struct node* left;
    struct node* right;
}node;


node* createNode(int n) {
    node* new = (node*)malloc(sizeof(node));
    new->value = n;
    new->left = NULL;
    new->right = NULL;

    return new;
}


void insert(node** root, int num) {
    if (*root == NULL) {
        node* newNode = createNode(num);
        *root = newNode;
    }
    else {
        if ((*root)->value > num) {
            insert(&(*root)->left, num);
        }
        else if ((*root)->value < num) {
            insert(&(*root)->right, num);
        }
    }
}


void BFSinsert(node* currentNode, int* array, int i) {
    if (!currentNode) {
        array[i] = -1;  // to indicate that it's empty
        return;
    }
    BFSinsert(currentNode->left, array, 2*i+1);
    BFSinsert(currentNode->right, array, 2*i+2);
    array[i] = currentNode->value;
}


int isCompleteBTree(int arr[], int n) {
    for (int i = 0; i <= n / 2 - 1; i++) {
        if (arr[i] == -1) return 0;  // Found a NULL node
        if (2 * i + 1 >= n || arr[2 * i + 1] == -1) return 0;  // Left child out of bounds or NULL
        if (2 * i + 2 >= n || arr[2 * i + 2] == -1) return 0;  // Right child out of bounds or NULL
    }
    return 1;
}


int countNodes(node* root) {
    if (root == NULL) return 0;
    else return 1 + countNodes(root->left) + countNodes(root->right);
}


void freeTree(node* node) {
    if (!node) return;
    if (node->left) freeTree(node->left);
    if (node->right) freeTree(node->right);
    free(node);
}


int main (void) {
    node* root = NULL;
    insert(&root, 6);
    insert(&root, 4);
    insert(&root, 8);
    insert(&root, 3);
    insert(&root, 5);
    insert(&root, 7);
    insert(&root, 9);


    int nodeCount = countNodes(root);
    int* array = (int*)malloc(100 * sizeof(int));

    BFSinsert(root, array, 0);

    printf("Array contents: ");
    for (int i = 0; i < nodeCount; i++) {
        if (array[i] == -1) nodeCount ++;  // nodeCount doesn't count NULL nodes, but array puts -1 for empty nodes in the lowest level
        printf("%d ", array[i]);
    }
    printf("\n");

    if (isCompleteBTree(array, nodeCount)) printf("The tree is complete.\n");
    else printf("The tree is incomplete.\n");

    freeTree(root);
    free(array);

    return 0;
}