c语言实现二叉树按层遍历
时间: 2024-08-13 21:03:01 浏览: 44
在 C 语言中实现二叉树的按层遍历,通常采用队列(Queue)数据结构,因为队列的特性正好适合这种逐层访问的顺序。这里提供一个基于广度优先搜索(BFS)的简单实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建一个新的二叉树节点
TreeNode* newNode(int val) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 按层遍历函数
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) return;
// 初始化队列并添加根节点
Queue queue;
enqueue(&queue, root);
while (!isQueueEmpty(&queue)) {
// 弹出队首元素
TreeNode* temp = dequeue(&queue);
// 输出当前节点值
printf("%d ", temp->val);
// 如果有左、右子节点,添加到队列中
if (temp->left != NULL) enqueue(&queue, temp->left);
if (temp->right != NULL) enqueue(&queue, temp->right);
}
}
// 队列操作,这里假设已经定义了enqueue和dequeue函数
void enqueue(Queue* queue, TreeNode* node) {
// ...
}
int isQueueEmpty(Queue* queue) {
// ...
}
// 主函数示例
int main() {
// 构建二叉树(例如:创建一个简单的二叉树)
TreeNode* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Level order traversal of the binary tree: ");
levelOrderTraversal(root);
return 0;
}
阅读全文