c语言二叉树的层次遍历

使用队列实现C语言中二叉树的层次遍历。下面是一个简单的例子：

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

// 定义二叉树节点
struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 定义队列节点
struct QueueNode {
    struct TreeNode* data;
    struct QueueNode* next;
};

// 定义队列
struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
};

// 初始化队列
void initializeQueue(struct Queue* q) {
    q->front = q->rear = NULL;
}

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

// 入队列
void enqueue(struct Queue* q, struct TreeNode* node) {
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->data = node;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 出队列
struct TreeNode* dequeue(struct Queue* q) {
    if (isQueueEmpty(q)) {
        return NULL;
    }

    struct QueueNode* temp = q->front;
    struct TreeNode* node = temp->data;

    q->front = q->front->next;
    free(temp);

    if (q->front == NULL) {
        q->rear = NULL;
    }

    return node;
}

// 层次遍历二叉树
void levelOrderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }

    struct Queue q;
    initializeQueue(&q);
    enqueue(&q, root);

    while (!isQueueEmpty(&q)) {
        struct TreeNode* current = dequeue(&q);
        printf("%d ", current->data);

        if (current->left != NULL) {
            enqueue(&q, current->left);
        }

        if (current->right != NULL) {
            enqueue(&q, current->right);
        }
    }
}

// 测试
int main() {
    // 构建一个简单的二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->data = 1;
    root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->left->data = 2;
    root->left->left = root->left->right = NULL;
    root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->right->data = 3;
    root->right->left = root->right->right = NULL;

    // 进行层次遍历
    printf("层次遍历结果: ");
    levelOrderTraversal(root);

    // 释放内存
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}