设计无限制子节点类二叉树时，如何避免指针数组的重分配？

针对你遇到的内存分配问题，有两种实用的解决思路，既能避开频繁realloc导致的内存碎片，也不会出现静态数组的容量限制和内存浪费问题：

一、预分配扩容策略（优化数组式存储） #

核心思路是减少realloc的调用次数：给每个节点新增一个capacity字段，记录当前已分配的子节点指针数组容量。初始时分配一个较小的固定容量（比如2），当实际子节点数num_children等于capacity时，一次性将容量扩容为原来的2倍（或1.5倍这类合理倍数），而非每次新增一个节点就调用realloc。

这种方式把realloc的调用次数从O(n)降到O(logn)，大幅减少内存碎片产生，同时保留数组随机访问子节点的优势。

修改后的结构体：

struct node {
  int id;
  int num_children;
  int capacity; // 记录当前分配的子节点指针容量
  struct node **child;
};

添加子节点的逻辑示例：

void add_child(struct node *parent, struct node *new_child) {
    if (parent->num_children == parent->capacity) {
        // 扩容逻辑：初始容量为0则先分配2个，否则翻倍
        int new_capacity = parent->capacity == 0 ? 2 : parent->capacity * 2;
        struct node **new_child_arr = realloc(parent->child, new_capacity * sizeof(struct node*));
        if (!new_child_arr) {
            // 处理内存分配失败
            return;
        }
        parent->child = new_child_arr;
        parent->capacity = new_capacity;
    }
    parent->child[parent->num_children++] = new_child;
}

二、链表式存储子节点 #

如果完全不想用数组和realloc，可以把每个节点的子节点改成单链表存储：每个节点只保存子节点链表的头指针，新增子节点时直接分配一个链表节点挂到链表上，删除子节点时只需调整链表指针。

这种方式彻底规避了realloc，没有容量限制，且只有当节点有子节点时才会分配链表节点，不会浪费内存。

修改后的结构体：

// 子节点链表节点
struct child_link {
    struct node *child;
    struct child_link *next;
};

// 树节点
struct node {
    int id;
    struct child_link *child_head; // 子节点链表的头指针
};

添加子节点的逻辑示例：

void add_child(struct node *parent, struct node *new_child) {
    struct child_link *new_link = malloc(sizeof(struct child_link));
    if (!new_link) {
        // 处理内存分配失败
        return;
    }
    new_link->child = new_child;
    new_link->next = parent->child_head; // 头插法，也可改用尾插法
    parent->child_head = new_link;
}

两种方案对比 #

• 预分配扩容：保留数组的随机访问优势（O(1)访问第k个子节点），内存碎片少，适合需要频繁随机访问子节点的场景。
• 链表存储：内存利用率更高，添加/删除子节点更灵活，但随机访问需要遍历链表（O(n)时间），适合子节点数量波动大、随机访问需求少的场景。

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