向多路二叉树父节点子数组添加节点时出现段错误的原因排查

问题场景与代码 #

尝试通过父数组构建多路二叉树，相关代码定义如下：

节点结构 #

typedef struct x{
    int id;
    struct x* son[MAX];
    int index;
}nodeR2;

内存分配函数 #

nodeR2* allocMem(int id)
{
    nodeR2* n = new nodeR2;
    if(n)
    {
        n->id = id;
        n->index = 0;
        for(int i = 0 ; i < MAX ; i++)
            n->son[i] = NULL;
        return n;
    }
    else
        return NULL;
}

节点创建函数 #

void createNode(int v[], int id, nodeR2** createdNodes, nodeR2* root)
{
    if(createdNodes[id-1] != NULL) // 节点已创建则直接返回
        return;
    
    createdNodes[id-1] = allocMem(id); // 创建当前节点
    if(v[id-1] == -1) // 父节点为-1，标记为根节点
    {
        root = createdNodes[id-1]; 
        return;
    }

    if(createdNodes[v[id-1]] == NULL) // 父节点未创建，递归创建父节点
        createNode(v, v[id-1], createdNodes, root);
    
    // 将当前节点挂载到父节点的子节点列表
    nodeR2* n = createdNodes[v[id-1]];

    addToSons(n, createdNodes[id-1]);    
}

子节点添加函数 #

void addToSons(nodeR2* source, nodeR2* son)
{
    source->son[source->index++] = son;
}

问题现象 #

运行触发segmentation fault错误，调试发现首次执行addToSons(n, createdNodes[id-1]);时，n为0x0空指针，直接导致段错误。且存在递归返回后n值异常变化的情况。

核心原因分析 #

1. 数组索引越界导致内存破坏
   代码中父节点索引计算完全错误：createdNodes数组的索引规则是节点ID减1（比如ID为k的节点对应索引k-1），但代码里直接用父节点IDv[id-1]作为数组索引，这会触发严重的数组越界访问。
   越界操作会破坏createdNodes数组本身或相邻内存区域的内容，递归创建父节点返回后，原本正确的父节点指针被覆盖为空，最终导致n成为空指针。

2. 根节点传参方式错误（次要）
   createNode函数中root是按值传递的，内部对root的赋值无法同步到外部变量，但这不是当前段错误的直接原因，不过会导致根节点无法正确初始化。

修复方案 #

1. 修正父节点索引计算 #

将所有访问父节点的索引位置改为v[id-1] - 1，确保索引与节点ID匹配：

void createNode(int v[], int id, nodeR2** createdNodes, nodeR2* root)
{
    // ... 其他代码 ...
    if(createdNodes[v[id-1] - 1] == NULL) 
        createNode(v, v[id-1], createdNodes, root);
    
    nodeR2* n = createdNodes[v[id-1] - 1];
    // ... 其他代码 ...
}

2. 修复根节点传参问题 #

将root参数改为指针的指针，让内部修改能同步到外部：

void createNode(int v[], int id, nodeR2** createdNodes, nodeR2** root)
{
    // ... 其他代码 ...
    if(v[id-1] == -1)
    {
        *root = createdNodes[id-1]; 
        return;
    }
    // ... 其他代码 ...
}

调用时传入根节点的地址：createNode(v, target_id, createdNodes, &root);

3. 补充合法性检查（可选） #

添加对父节点ID的范围校验，避免非法索引访问：

int parent_id = v[id-1];
if(parent_id != -1)
{
    if(parent_id < 1 || parent_id > MAX_NODES) // MAX_NODES为节点总数
    {
        // 处理非法父节点ID的情况，比如报错返回
        return;
    }
    // ... 后续父节点创建逻辑 ...
}

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