层次遍历二叉树算法c语言

二叉树的层次遍历可以使用队列来实现，具体算法如下：

1. 首先将根节点入队。

2. 循环执行以下步骤，直到队列为空：

a. 取出队头元素并输出。

b. 如果该元素有左孩子，则将左孩子入队。

c. 如果该元素有右孩子，则将右孩子入队。

下面是C语言的代码实现：

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

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

// 队列结点的定义
typedef struct QueueNode {
    TreeNode *data;
    struct QueueNode *next;
} QueueNode;

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

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

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

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

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

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

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

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

    free(temp);
    return data;
}

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

    Queue q;
    initQueue(&q);
    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() {
    // 创建二叉树
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;

    TreeNode *node1 = (TreeNode*)malloc(sizeof(TreeNode));
    node1->val = 2;
    root->left = node1;

    TreeNode *node2 = (TreeNode*)malloc(sizeof(TreeNode));
    node2->val = 3;
    root->right = node2;

    TreeNode *node3 = (TreeNode*)malloc(sizeof(TreeNode));
    node3->val = 4;
    node1->left = node3;

    TreeNode *node4 = (TreeNode*)malloc(sizeof(TreeNode));
    node4->val = 5;
    node1->right = node4;

    TreeNode *node5 = (TreeNode*)malloc(sizeof(TreeNode));
    node5->val = 6;
    node2->left = node5;

    TreeNode *node6 = (TreeNode*)malloc(sizeof(TreeNode));
    node6->val = 7;
    node2->right = node6;

    // 层次遍历二叉树
    levelOrder(root);

    return 0;
}