c语言层序遍历

前言

层序遍历是二叉树的一种遍历方式，它按照从上到下、从左到右的顺序遍历二叉树的每个节点。在C语言中，我们可以使用队列来实现二叉树的层序遍历。下面我们将介绍如何实现层序遍历的代码。

层序遍历代码实现

#include 
#include 

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

// 定义队列节点结构
typedef struct QueueNode {
    TreeNode* node;
    struct QueueNode* next;
} QueueNode;

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

// 创建队列
Queue* createQueue() {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

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

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

// 出队列
TreeNode* dequeue(Queue* queue) {
    if (queue->front == NULL) {
        return NULL;
    }

    TreeNode* node = queue->front->node;
    QueueNode* temp = queue->front;
    queue->front = queue->front->next;

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

    free(temp);
    return node;
}

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

    Queue* queue = createQueue();
    enqueue(queue, root);

    while (queue->front != NULL) {
        TreeNode* node = dequeue(queue);
        printf("%d ", node->val);

        if (node->left != NULL) {
            enqueue(queue, node->left);
        }

        if (node->right != NULL) {
            enqueue(queue, node->right);
        }
    }

    free(queue);
}

代码解释

1. 定义了二叉树节点结构和队列节点结构，分别用来表示二叉树的节点和队列中的节点。
2. 创建队列使用 createQueue() 函数，该函数动态分配内存空间，并初始化队列的 front 和 rear 为 NULL。
3. 入队列使用 enqueue() 函数，该函数将节点添加到队列尾部。若队列为空，则队列的 front 和 rear 都指向该节点；否则，队列的 rear 指向该节点。
4. 出队列使用 dequeue() 函数，该函数从队列头部删除节点，并返回该节点。若队列为空，返回 NULL；否则，返回队列的 front 指向的节点，并更新队列的 front 和 rear。
5. 层序遍历二叉树使用 levelOrderTraversal() 函数，该函数先将根节点入队列，然后循环执行以下操作：
    - 出队列并打印节点的值。
    - 若节点的左子节点不为空，将左子节点入队列。
    - 若节点的右子节点不为空，将右子节点入队列。
6. 完成遍历后释放队列的内存空间。

总结

通过以上代码实现，我们可以使用层序遍历的方式访问二叉树的每个节点，并按照顺序输出节点的值。层序遍历是一种广度优先搜索的算法，它可以用于解决许多与树相关的问题，如查找二叉树的最大深度、判断二叉树是否对称等。