C语言使用child-nextSibling结构的通用树插入子节点问题求助

问题根本原因 #

你的所有修改操作都作用在指针的本地副本上，没有实际修改原树节点里的hijo/hno（兄弟节点指针）成员：

• GTree copia = arbol->hijo 只是把arbol的子节点指针值拷贝给了本地变量copia，后续给copia赋值新节点，完全不会修改arbol->hijo本身的指向
• 你遍历到copia==NULL才停止，此时没有持有最后一个有效兄弟节点的指针，没法把新节点挂到原树的对应位置
• else分支的递归逻辑完全错误，循环里每次把返回值赋值给本地遍历变量arbol_copia，同样不会修改原树的指针

修复方案 #

1. 修复父节点匹配后的插入逻辑 #

你需要定位到最后一个非空的子节点，再把新节点挂到它的兄弟指针上：

else if (comp(datoPadre, arbol->dato) == 0){
    // 父节点没有子节点时直接挂到hijo
    if (arbol->hijo == NULL) {
        arbol->hijo = gtree_agregar(NULL, datoPadre, dato, copiar, comp);
    } else {
        // 遍历到最后一个子节点
        GTree last_child = arbol->hijo;
        while (last_child->hno != NULL) {
            last_child = last_child->hno;
        }
        // 新节点挂到最后一个子节点的hno位置
        last_child->hno = gtree_agregar(NULL, datoPadre, dato, copiar, comp);
    }
}

2. 修复else分支的递归遍历逻辑 #

不需要循环遍历，直接递归处理兄弟节点和子节点，把返回值赋值给原节点的对应成员即可：

else {
    // 递归遍历兄弟节点
    arbol->hno = gtree_agregar(arbol->hno, datoPadre, dato, copiar, comp);
    // 递归遍历子节点
    arbol->hijo = gtree_agregar(arbol->hijo, datoPadre, dato, copiar, comp);
}

完整修复后的函数 #

GTree gtree_agregar(GTree arbol, void *datoPadre, void *dato, FuncionCopiadora copiar, FuncionComparadora comp){
    if(arbol == NULL){
        // 注意和你定义的结构体名保持一致，你最初定义的是struct Node，不要用不匹配的结构体名
        arbol = malloc(sizeof(struct Node));
        arbol->dato = copiar(dato);
        arbol->hijo = NULL;
        arbol->hno = NULL;
        return arbol;
    }
    if (comp(datoPadre, arbol->dato) == 0){
        if (arbol->hijo == NULL) {
            arbol->hijo = gtree_agregar(NULL, datoPadre, dato, copiar, comp);
        } else {
            GTree last_child = arbol->hijo;
            while (last_child->hno != NULL) {
                last_child = last_child->hno;
            }
            last_child->hno = gtree_agregar(NULL, datoPadre, dato, copiar, comp);
        }
        return arbol;
    }
    arbol->hno = gtree_agregar(arbol->hno, datoPadre, dato, copiar, comp);
    arbol->hijo = gtree_agregar(arbol->hijo, datoPadre, dato, copiar, comp);
    return arbol;
}

额外注意 #

调用函数时注意接收返回值，比如根节点为NULL时插入根节点，要写root = gtree_agregar(root, NULL, 根节点数据, copiar, comp)，否则根节点的修改不会生效。

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