如何用C语言实现指定N叉树的层级节点求和并打印？

你的错误实现问题分析 #

• 用深度优先递归的方式没法区分节点所在层级，求和结果是子树的总和而非同层节点的总和，完全不符合需求
• 逻辑遗漏：直接从t->child->sibling开始遍历，漏掉了当前节点的第一个子节点（比如测试用例里根节点的第一个子节点5就没被统计）
• 函数返回值不完整：else分支没有返回语句，会触发未定义行为
• 输出时机错误，无法按层级顺序输出结果

正确实现思路：广度优先遍历（BFS） #

按层处理节点的需求天然适合用BFS，核心是用队列保存每一层的所有节点，逐层处理：

• 初始化队列，将根节点入队
• 从层级0开始，循环处理队列中的节点：
  1. 统计当前队列的节点数量（即当前层的节点总数）
  2. 遍历当前层的所有节点，累加它们的key得到当前层的总和
  3. 遍历每个节点的所有子节点（从child开始，依次遍历sibling直到NULL），将这些子节点加入队列（作为下一层的节点）
  4. 打印当前层的层级和总和，然后进入下一层
• 直到队列为空，结束循环

具体代码实现 #

因为C标准库没有现成的队列，我们可以用简单的链表模拟队列：

#include <stdio.h>
#include <stdlib.h>

// 题目给定的N叉树结构
struct kTreeVertex {
    int                  key;
    struct kTreeVertex*  child;
    struct kTreeVertex*  sibling;
};
typedef struct kTreeVertex* kTree;

// 队列节点结构，用来存储N叉树节点指针
struct QueueNode {
    kTree treeNode;
    struct QueueNode* next;
};

// 队列结构，保存头尾指针
struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
};

// 创建新的队列节点
struct QueueNode* createQueueNode(kTree t) {
    struct QueueNode* node = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    node->treeNode = t;
    node->next = NULL;
    return node;
}

// 初始化空队列
struct Queue* createQueue() {
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}

// 入队操作
void enqueue(struct Queue* q, kTree t) {
    struct QueueNode* node = createQueueNode(t);
    if (q->rear == NULL) {
        q->front = q->rear = node;
        return;
    }
    q->rear->next = node;
    q->rear = node;
}

// 出队操作，返回队列头的树节点
kTree dequeue(struct Queue* q) {
    if (q->front == NULL) return NULL;
    struct QueueNode* temp = q->front;
    kTree t = temp->treeNode;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
    return t;
}

// 判断队列是否为空
int isQueueEmpty(struct Queue* q) {
    return q->front == NULL;
}

// 题目要求的sumLevels函数
void sumLevels(kTree t) {
    if (t == NULL) return; // 前置条件说非空，这里做个兜底

    struct Queue* q = createQueue();
    enqueue(q, t);
    int level = 0;

    while (!isQueueEmpty(q)) {
        // 获取当前层的节点数量
        int levelSize = 0;
        struct QueueNode* temp = q->front;
        while (temp != NULL) {
            levelSize++;
            temp = temp->next;
        }

        int currentSum = 0;
        // 遍历当前层所有节点
        for (int i = 0; i < levelSize; i++) {
            kTree current = dequeue(q);
            currentSum += current->key;

            // 将当前节点的所有子节点加入队列
            kTree child = current->child;
            while (child != NULL) {
                enqueue(q, child);
                child = child->sibling;
            }
        }

        // 打印当前层的结果
        printf("level %d: %d\n", level, currentSum);
        level++;
    }

    free(q);
}

// 测试用例构建代码（供参考）
kTree createTreeNode(int key) {
    kTree node = (kTree)malloc(sizeof(struct kTreeVertex));
    node->key = key;
    node->child = NULL;
    node->sibling = NULL;
    return node;
}

int main() {
    // 构建测试用例树
    kTree root = createTreeNode(10);
    kTree node5 = createTreeNode(5);
    kTree node3 = createTreeNode(3);
    kTree node2 = createTreeNode(2);
    kTree node7 = createTreeNode(7);
    kTree node8 = createTreeNode(8);
    kTree node1 = createTreeNode(1);

    root->child = node5;
    node5->sibling = node3;
    node3->sibling = node2;
    node2->sibling = node7;

    node5->child = node8;
    node2->child = node1;

    sumLevels(root);

    // 释放内存（省略，实际使用需要处理）
    return 0;
}

这段代码运行后，会输出：

level 0: 10
level 1: 17
level 2: 9

完全符合测试用例的期望结果。

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