用c写个二叉树层序遍历

这是一个非常经典的问题，即使用队列实现二叉树的层序遍历。以下是使用C语言的示例代码：

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

// 树节点结构体定义
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

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

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

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

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

// 入队
void enqueue(struct Queue *q, struct TreeNode *t) {
    struct QueueNode *newNode = (struct QueueNode *)malloc(sizeof(struct QueueNode));
    if (newNode == NULL) {
        printf("Memory allocation failed.\n");
        exit(-1);
    }

    newNode->data = t;
    newNode->next = NULL;

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

// 出队
struct TreeNode *dequeue(struct Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return NULL;
    }
    struct TreeNode *result = q->front->data;
    q->front = q->front->next;
    return result;
}

// 创建二叉树
struct TreeNode *createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1)  // 输入-1表示该节点为空
        return NULL;

    struct TreeNode *t = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    if (t == NULL) {
        printf("Memory allocation failed.\n");
        exit(-1);
    }

    t->val = val;
    t->left = createTree();
    t->right = createTree();
    return t;
}

// 层序遍历
void levelOrderTraversal(struct TreeNode *root) {
    if (root == NULL)
        return;

    struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
    if (q == NULL) {
        printf("Memory allocation failed.\n");
        exit(-1);
    }

    initQueue(q);
    enqueue(q, root);

    while (!isEmpty(q)) {
        struct TreeNode *cur = dequeue(q);
        printf("%d ", cur->val);

        if (cur->left != NULL)
            enqueue(q, cur->left);
        if (cur->right != NULL)
            enqueue(q, cur->right);
    }
}

// 主函数
int main() {
    printf("Please enter the number of the root node: ");
    struct TreeNode *root = createTree();

    printf("Level order traversal: ");
    levelOrderTraversal(root);
    printf("\n");

    return 0;
}

这里我们使用队列来辅助层序遍历，首先将根节点入队，然后每次出队一个节点，将其访问输出并将其左右子节点入队，直到队列为空即可。