普通多叉树广度优先搜索（BFS）算法实现疑难求助：二维数组存储丢失父子关系且编译通过无输出

先帮你搞定最紧急的运行无输出问题，再聊怎么保留父子关系～

问题2：运行无输出的原因与修复 #

你的get()函数逻辑有几个关键bug，导致遍历不完整甚至死循环：

• 兄弟节点遍历死循环：在else分支里，你写了bro = node->rightBro;然后循环里又赋值bro = node->rightBro;——这会让bro永远指向同一个节点，根本不会往后遍历兄弟，直接卡死循环。应该改成bro = bro->rightBro;。
• 遗漏有子节点的节点的兄弟：你只在节点没有子节点的时候才处理右兄弟，但实际上不管节点有没有子节点，处理完子节点后都要遍历它的右兄弟！比如根节点有子节点的话，你处理完子节点就直接返回了，根本没处理根节点的右兄弟。
• 打印逻辑的问题：直接printf("%s", arr[i][j])会访问未赋值的NULL指针，导致未定义行为（可能崩溃或者乱码），而且预期是空格分隔的输出，得判断非空再打印。

修复后的get()函数 #

我调整了逻辑，改成迭代遍历当前层级的兄弟，再递归处理子节点，更符合BFS的层级遍历逻辑：

void get(struct node *node, int row, int col, char ***arr) {
    struct node *current = node;
    // 先遍历当前层级的所有兄弟节点
    while (current != NULL) {
        // 存储当前节点的token
        arr[row][col] = current->token;
        // 递归处理子节点，行号+1，列号从0开始
        if (current->firstKid != NULL) {
            get(current->firstKid, row + 1, 0, arr);
        }
        // 移动到下一个右兄弟，列号+1
        current = current->rightBro;
        col++;
    }
}

修复后的打印代码 #

for(int i=0;i<10;i++){
    for(int j=0;j<10;j++){
        if(arr[i][j] != NULL){ // 只打印有值的节点
            printf("%s ", arr[i][j]);
        }
    }
    // 可选：按层级换行，更直观看到结构
    // printf("\n");
}
printf("\n");

这样只要你的树结构创建正确（比如根A，子节点B、C；B的子节点D、E；C的子节点F、G），就能输出预期的A B C D E F G 了。

问题1：保留父子节点关系的方案 #

二维数组只存token确实会丢失父子关联，有两种实用方案：

方案1：用结构体存储节点完整信息 #

定义一个包含父节点位置的结构体，把节点的token和父节点的行/列索引存在一起：

// 定义存储节点信息的结构体
struct NodeRecord {
    char *token;
    int parent_row; // 父节点所在行
    int parent_col; // 父节点所在列
};

// 初始化结构体类型的二维数组
struct NodeRecord ***arr = (struct NodeRecord ***)malloc(n*sizeof(struct NodeRecord **));
for(int i=0;i<n;i++)
    arr[i] = (struct NodeRecord **)malloc(m*sizeof(struct NodeRecord *));

然后修改get()函数，传递父节点的位置信息：

void get(struct node *node, int row, int col, struct NodeRecord ***arr, int parent_row, int parent_col) {
    struct node *current = node;
    while (current != NULL) {
        // 分配内存存储当前节点的记录
        arr[row][col] = (struct NodeRecord *)malloc(sizeof(struct NodeRecord));
        arr[row][col]->token = current->token;
        arr[row][col]->parent_row = parent_row;
        arr[row][col]->parent_col = parent_col;
        
        // 处理子节点，父节点就是当前节点的位置
        if (current->firstKid != NULL) {
            get(current->firstKid, row + 1, 0, arr, row, col);
        }
        
        current = current->rightBro;
        col++;
    }
}

调用时，根节点的父节点位置设为-1（表示无父节点）：

get(head, 0, 0, arr, -1, -1);

之后要找某个节点的父节点，直接通过parent_row和parent_col去数组里取就行。

方案2：利用层级数组的特性推断关系 #

因为你的row代表节点的层级（根节点row=0，子节点row=1，以此类推），同层级的col是兄弟节点的顺序。只要你的遍历逻辑保证：一个节点的所有子节点，在它的下一行从某个col开始连续排列，那么父子关系可以直接推断：

• 比如row=1的col=0的节点，父节点是row=0的col=0的节点；
• row=2的col=0、1的节点，父节点是row=1的col=0的节点；
• row=2的col=2、3的节点，父节点是row=1的col=1的节点。

这种方式不需要额外存储信息，但要求你的遍历逻辑严格遵循层级顺序，适合结构固定的树。

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