用C语言实现通过队列来实现层次遍历构建二叉树

以下是用C语言实现通过队列来实现层次遍历构建二叉树的示例代码：

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

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

// 定义队列结构体
typedef struct Queue {
    TreeNode** data;
    int front;
    int rear;
    int maxSize;
} Queue;

// 初始化队列
Queue* initQueue(int maxSize) {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->data = (TreeNode**)malloc(sizeof(TreeNode*) * maxSize);
    q->front = q->rear = 0;
    q->maxSize = maxSize;
    return q;
}

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

// 判断队列是否已满
int isFull(Queue* q) {
    return (q->rear + 1) % q->maxSize == q->front;
}

// 入队
void enqueue(Queue* q, TreeNode* node) {
    if (isFull(q)) {
        printf("queue is full\n");
        return;
    }
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % q->maxSize;
}

// 出队
TreeNode* dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("queue is empty\n");
        return NULL;
    }
    TreeNode* node = q->data[q->front];
    q->front = (q->front + 1) % q->maxSize;
    return node;
}

// 创建二叉树
TreeNode* createBinaryTree(int* arr, int len) {
    if (len == 0) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = arr[0];
    root->left = root->right = NULL;
    Queue* q = initQueue(len);
    enqueue(q, root);
    int i = 1;
    while (i < len) {
        TreeNode* parent = dequeue(q);
        if (i < len && arr[i] != -1) {
            TreeNode* left = (TreeNode*)malloc(sizeof(TreeNode));
            left->val = arr[i];
            left->left = left->right = NULL;
            parent->left = left;
            enqueue(q, left);
        }
        i++;
        if (i < len && arr[i] != -1) {
            TreeNode* right = (TreeNode*)malloc(sizeof(TreeNode));
            right->val = arr[i];
            right->left = right->right = NULL;
            parent->right = right;
            enqueue(q, right);
        }
        i++;
    }
    return root;
}

// 层次遍历
void levelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Queue* q = initQueue(100);
    enqueue(q, root);
    while (!isEmpty(q)) {
        TreeNode* node = dequeue(q);
        printf("%d ", node->val);
        if (node->left != NULL) {
            enqueue(q, node->left);
        }
        if (node->right != NULL) {
            enqueue(q, node->right);
        }
    }
}

int main() {
    int arr[] = { 1, 2, 3, 4, -1, 5, 6, -1, -1, 7 };
    int len = sizeof(arr) / sizeof(arr[0]);
    TreeNode* root = createBinaryTree(arr, len);
    levelOrder(root);
    return 0;
}

以上代码中，我们定义了一个二叉树结构体 `TreeNode` 和一个队列结构体 `Queue`，并实现了队列的入队、出队等操作。通过层次遍历的方式，将数组中的元素一个一个按照顺序插入到二叉树中，最终构建出一棵二叉树，并输出层次遍历结果。

示例输出结果为：1 2 3 4 5 6 7