用C语言写二叉树的层次遍历用递归写

在C语言中，使用递归来实现二叉树的层次遍历（广度优先搜索，BFS）通常会结合队列数据结构来存储每一层的节点。这里是一个简单的示例：

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

// 定义二叉树结点
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 用于存储节点并进行层次遍历
void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return; // 如果根节点为空，则直接返回

    // 使用队列辅助存储节点
    struct QueueNode {
        TreeNode* node;
        struct QueueNode* next;
    }* queue = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    queue->node = root;
    queue->next = NULL;

    // 队列头指针
    struct QueueNode* front = queue;

    while (front != NULL) {
        // 弹出当前层的所有节点
        TreeNode* node = front->node;
        printf("%d ", node->val); // 打印节点值
        front = front->next;

        // 将当前节点的左右子节点入队（如果存在）
        if (node->left != NULL) {
            struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
            newNode->node = node->left;
            newNode->next = queue->next;
            queue->next = newNode;
        }
        if (node->right != NULL) {
            struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
            newNode->node = node->right;
            newNode->next = queue->next;
            queue->next = newNode;
        }

        // 更新队列头指向下一个非空节点
        while (queue->next != NULL && queue->next->node == NULL) {
            queue = queue->next;
        }
    }

    free(queue);
}

// 示例用法
int main() {
    // 构建一个简单的二叉树...
    // 省略构建二叉树的代码...

    levelOrderTraversal(root); // 调用层次遍历函数
    return 0;
}