2023年6月22日发(作者：)

二叉树层次遍历c语言

二叉树是一种常见的数据结构，在计算机程序设计中经常使用。层次遍历是二叉树遍历的一种方法，也叫广度优先遍历。

层次遍历从二叉树的根节点开始，依次遍历每一层节点。在每一层中，从左到右遍历节点。具体实现时，可以使用队列数据结构来辅助层次遍历。

在c语言中，可以使用指针来表示二叉树节点，使用结构体来定义二叉树。下面是一个简单的二叉树结构体定义：

```

struct TreeNode {

int val;

struct TreeNode *left;

struct TreeNode *right;

};

```

其中，val表示节点的值，left和right分别表示左右子树。

以下是二叉树层次遍历的c语言实现：

```

void levelOrder(struct TreeNode* root) {

if (!root) return; // 边界情况，如果根节点为空则直接返回

// 创建一个队列，并将根节点入队

- 1 - struct TreeNode* queue[10000];

int front = 0, rear = 0;

queue[rear++] = root;

// 循环遍历队列中的节点，直到队列为空

while (front < rear) {

int size = rear - front; // 当前层的节点数

for (int i = 0; i < size; i++) {

struct TreeNode* node = queue[front++];

printf('%d ', node->val); // 输出当前节点的值

if (node->left) queue[rear++] = node->left; // 如果有左子树则将左子树入队

if (node->right) queue[rear++] = node->right; // 如果有右子树则将右子树入队

}

}

}

```

该函数的时间复杂度为O(n)，其中n为二叉树节点数。实际上，层次遍历也是二叉树的一种深度优先遍历方法，但是由于使用了队列，因此也可以看作广度优先遍历。

- 2 -