层次遍历法求二叉树第k层的节点数 C语言

层次遍历法，也称为广度优先搜索(Breadth First Search, BFS)，通常用于求解二叉树的深度和节点计数等问题。如果你想计算二叉树的第k层节点数，可以使用队列数据结构配合层次遍历策略。以下是简单的C语言实现步骤：

1. 初始化一个队列，并将根节点入队。
2. 定义一个变量`count`记录当前层数的节点数，初始值设为0。
3. 当队列非空时，执行以下操作：
a. 遍历队列直到为空：
- 弹出队首元素，增加当前层的节点数`count`。
- 如果该节点有左右子节点，将它们依次入队。
4. 当遇到第k层时，`count`就存储了该层的节点数。

下面是C语言伪代码示例：

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

int bfs(TreeNode* root, int k) {
    if (root == NULL || k <= 0) return 0; // 检查根节点和k是否有效

    queue<TreeNode*> q;
    q.enqueue(root); // 根节点入队
    int count = 1; // 第1层有一个节点

    while (!q.isEmpty()) {
        int size = q.size(); // 获取当前层节点数
        for (int i = 0; i < size; ++i) {
            TreeNode* node = q.dequeue(); // 出队并处理节点
            // 如果节点的子节点还没被处理，入队
            if (node->left) q.enqueue(node->left);
            if (node->right) q.enqueue(node->right);

            // 当前层处理完毕，进入下一层
            if (--k == 0) return count; // 如果达到k层，返回节点数
        }
        count += size; // 进入下一层，累加节点数
    }

    return 0; // 如果k大于树的实际层数，说明不存在第k层
}

int main() {
    TreeNode* root = ...; // 创建并初始化二叉树
    int k;
    scanf("%d", &k);
    int result = bfs(root, k);
    printf("第 %d 层的节点数为：%d\n", k, result);
    return 0;
}