为何用数组检查完全二叉搜索树的C代码存在Valgrind内存泄漏

问题背景 #

编写了一段通过数组按BFS顺序填充来检查二叉搜索树（BST）是否为完全二叉树的C代码，已尝试释放所有动态分配内存，但Valgrind检测显示存在240字节的确定丢失内存，需排查问题根源。

原代码 #

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

内存泄漏根源 #

内存泄漏的核心问题出在insert函数的逻辑错误：

• 每次调用insert都会创建新节点，即使该节点最终不会被挂载到树上：在else分支中，无论当前节点是否需要递归向下查找插入位置，都会先调用createNode分配内存。递归调用的insert又会重复创建节点，而那些未被挂载的节点没有被释放，导致内存泄漏。
• 举例：插入数值4时，顶层insert创建了一个值为4的节点，随后递归调用insert处理左子树；递归的insert发现左子树为NULL，又创建了一个值为4的节点并挂载，而顶层创建的节点被直接丢弃，未执行free，造成内存泄漏。每次插入操作都会产生数量等于递归深度的未释放节点，最终累积成Valgrind检测到的240字节泄漏（假设每个node结构体占24字节，对应10个未释放节点）。

修复方案 #

修改insert函数，仅在找到合适的插入位置（当前节点为NULL）时才创建新节点，避免不必要的内存分配：

void insert(node** root, int num) {
    if (*root == NULL) {
        *root = createNode(num);
        return;
    }
    // 仅在需要递归时继续，不提前创建节点
    if ((*root)->value > num) {
        insert(&(*root)->left, num);
    } else if ((*root)->value < num) {
        insert(&(*root)->right, num);
    }
    // 数值已存在时不做任何操作，避免创建无用节点
}

额外优化提示 #

1. BFSinsert函数并非真正的BFS：当前实现是后序遍历逻辑，若需要按广度优先顺序填充数组，应使用队列实现层级遍历，而非递归。
2. isCompleteBTree函数逻辑错误：当前判断的是满二叉树（所有非叶子节点都有左右孩子），而非完全二叉树。完全二叉树的正确判断逻辑应为：遍历数组时，遇到第一个-1后，后续所有元素必须都是-1。
3. main函数中的循环逻辑风险：for循环内修改nodeCount可能导致数组越界访问，建议提前计算数组所需的最大容量（完全二叉树的数组容量为2^h - 1，h为树的高度）。

内容的提问来源于stack exchange，提问作者Nurana