C语言二叉树代码的指针使用是否存在内存浪费？

我学习C语言时特别关注内存分配问题，学校教学里给了一段构建二叉树的代码。这段代码在for循环里每次都会创建指针，再把这些指针对应的节点地址分配给树的对应节点，前后创建了10多个指针。我想知道能不能只使用一个指针，持续更新它，就像递归实现里只更新主指针并返回的方式？如果我对内存的理解有错误，麻烦指正。

typedef struct tr {
    int data;
    struct tr *left, *right;
} btree, *btreeptr;

btree *createtree(int data) {
    btree *newtree;
    newtree = (btree *)malloc(sizeof(btree));
    newtree->left = NULL;
    newtree->right = NULL;
    newtree->data = data;// Is the same as : (*p).data, 
    return newtree;
}

int main() {
    btree *test[10];
    btreeptr baum;
    int i;

    for (i = 0; i < 10; i++) {
        test[i] = createtree(i);
    }

    baum = test[0]; 
    test[0]->left = test[1];
    test[0]->right = test[2];
    test[1]->left = test[3];
    test[1]->right = test[4];
    test[2]->right = test[5];
    test[4]->left = test[6];
    test[5]->left = test[7];
    test[5]->right = test[8];
    test[7]->left = test[9];

    printf("Size: %d\n", size(baum));
    printf("Leaves: %d\n", numberOfLeaves(baum));
    printf("Height: %d\n", height(baum));

    return 0;
}

首先要明确：你混淆了「指针变量」和「动态分配的节点内存」。代码里的test[10]是一个指针数组，里面的每个元素都是指针变量，这些变量本身存储的是createtree里malloc出来的节点内存的地址。

核心区别 #

• 动态分配的节点：createtree里用malloc创建的是二叉树的实际节点，每个节点占用一块堆内存，这部分是必须的——因为你需要10个节点来构建这棵树，堆内存的分配数量和节点数一致，没法减少。
• 指针变量：test数组里的指针只是用来临时存储这些节点的地址，方便后续把它们连接成树结构。这部分是可以优化的，不需要用一个数组来存所有节点的指针。

用单个指针变量构建树的可行方案 #

你确实可以只用一个指针变量，每次创建节点后直接把它连接到树的对应位置，不需要把所有节点地址都存在数组里。比如可以这样改写main函数：

int main() {
    btreeptr baum;
    btreeptr temp; // 单个临时指针变量

    // 创建根节点
    baum = createtree(0);
    // 连接左子节点
    baum->left = createtree(1);
    // 连接右子节点
    baum->right = createtree(2);

    // 操作左子树的子节点，用temp临时指向baum->left
    temp = baum->left;
    temp->left = createtree(3);
    temp->right = createtree(4);

    // 操作左子树右节点的子节点
    temp = temp->right;
    temp->left = createtree(6);

    // 操作根节点右子节点
    temp = baum->right;
    temp->right = createtree(5);

    // 操作节点5的子节点
    temp = temp->right;
    temp->left = createtree(7);
    temp->right = createtree(8);

    // 操作节点7的子节点
    temp = temp->left;
    temp->left = createtree(9);

    printf("Size: %d\n", size(baum));
    printf("Leaves: %d\n", numberOfLeaves(baum));
    printf("Height: %d\n", height(baum));

    return 0;
}

为什么递归可以只用主指针？ #

递归构建时，每次递归调用会返回新节点的地址，我们直接把这个地址赋值给父节点的left或right即可，不需要额外存储所有节点的指针——因为递归过程中，父节点的指针已经能让我们访问到对应的位置，不需要临时数组来存所有节点地址。

关键误区纠正 #

你以为代码里创建了10多个指针是「浪费内存」，但实际上这些指针变量是存在栈上的，每个指针变量在32位系统占4字节、64位占8字节，10个指针最多也就80字节，内存开销可以忽略。真正的内存开销是malloc出来的10个节点，这部分是构建树必须的，没法减少。

所以你的核心需求是减少临时指针变量的数量，而不是减少动态分配的节点内存，这一点是可以做到的，就像上面的代码示例那样，用单个临时指针变量就能完成树的连接。

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