编写按层次顺序(同一层从左至右)遍历二叉树算法的c语言代码
时间: 2024-02-03 10:02:00 浏览: 31
以下是按层次顺序遍历二叉树的C语言代码:
```
#include<stdio.h>
#include<stdlib.h>
// 二叉树定义
struct Node {
int data;
struct Node* left;
struct Node* right;
};
// 利用队列实现层次遍历
void levelOrder(struct Node* root) {
if (root == NULL) return;
// 创建队列
struct Node** queue = (struct Node**)malloc(sizeof(struct Node*));
int front = 0, rear = 0;
// 先将根节点入队
queue[rear++] = root;
while (front != rear) {
// 取出队首元素
struct Node* current = queue[front++];
// 访问该节点
printf("%d ", current->data);
// 若该节点有左子节点,将其入队
if (current->left != NULL) {
queue = (struct Node**)realloc(queue, (rear + 1) * sizeof(struct Node*));
queue[rear++] = current->left;
}
// 若该节点有右子节点,将其入队
if (current->right != NULL) {
queue = (struct Node**)realloc(queue, (rear + 1) * sizeof(struct Node*));
queue[rear++] = current->right;
}
}
}
// 新建节点
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
// 主函数
int main() {
// 新建二叉树
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
// 层次遍历二叉树
printf("层次遍历二叉树: ");
levelOrder(root);
return 0;
}
```
在上述代码中,我们定义了一个 `Node` 结构体表示二叉树的节点,其中包含了数据、左子节点和右子节点三个成员。`newNode` 函数用于新建一个节点,将其数据和左右子节点设为NULL。利用 `levelOrder` 函数实现二叉树的层次遍历,核心部分是使用队列来保存每一层的节点,首先将根节点入队,然后对队列进行循环,每次将队首元素出队,并输出其数据。对该节点的左右子节点进行判断,若不为空则入队。本算法的时间复杂度为 O(n),n 为二叉树节点数量。