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

层次遍历二叉树可以使用队列进行实现，不需要使用递归。 具体算法如下： 1. 创建一个空队列，将根节点入队。 2. 循环执行以下步骤，直到队列为空： a. 取出队首元素，并输出该元素的值。 b. 如果该元素有左子节点，将左子节点入队。 c. 如果该元素有右子节点，将右子节点入队。 下面是使用C语言实现的层次遍历二叉树示例代码： ```c #include <stdio.h> #include <stdlib.h> typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; typedef struct Queue { TreeNode **data; int front; int rear; int capacity; } Queue; Queue* createQueue(int capacity) { Queue *queue = (Queue *)malloc(sizeof(Queue)); queue->data = (TreeNode **)malloc(sizeof(TreeNode *) * capacity); queue->front = 0; queue->rear = -1; queue->capacity = capacity; return queue; } int isFull(Queue *queue) { return (queue->rear == queue->capacity - 1); } int isEmpty(Queue *queue) { return (queue->front > queue->rear); } void enqueue(Queue *queue, TreeNode *node) { if (isFull(queue)) { printf("Queue is full.\n"); return; } queue->rear++; queue->data[queue->rear] = node; } TreeNode* dequeue(Queue *queue) { if (isEmpty(queue)) { printf("Queue is empty.\n"); return NULL; } TreeNode *node = queue->data[queue->front]; queue->front++; return node; } void levelOrder(TreeNode *root) { if (root == NULL) { printf("Tree is empty.\n"); return; } Queue *queue = createQueue(100); enqueue(queue, root); while (!isEmpty(queue)) { TreeNode *node = dequeue(queue); printf("%d ", node->val); if (node->left != NULL) { enqueue(queue, node->left); } if (node->right != NULL) { enqueue(queue, node->right); } } printf("\n"); } int main() { TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode)); root->val = 1; root->left = (TreeNode *)malloc(sizeof(TreeNode)); root->left->val = 2; root->left->left = NULL; root->left->right = NULL; root->right = (TreeNode *)malloc(sizeof(TreeNode)); root->right->val = 3; root->right->left = (TreeNode *)malloc(sizeof(TreeNode)); root->right->left->val = 4; root->right->left->left = NULL; root->right->left->right = NULL; root->right->right = (TreeNode *)malloc(sizeof(TreeNode)); root->right->right->val = 5; root->right->right->left = NULL; root->right->right->right = NULL; printf("Level order traversal of binary tree: "); levelOrder(root); return 0; } ``` 输出结果： ``` Level order traversal of binary tree: 1 2 3 4 5 ```