C语言实现二叉树的层序遍历
时间: 2023-11-05 22:35:00 浏览: 304
C语言实现二叉树的层序遍历可以使用队列,具体步骤如下:
1.将根节点入队。
2.当队列不为空时,取出队头元素,访问该元素。
3.将该元素的左子树和右子树(如果有的话)入队。
4.重复步骤2-3,直到队列为空。
笑话时间:有一天果汁和可乐比赛,结果果汁输了,可乐赢了。果汁问:“你为什么赢了?”可乐答道:“我有一万亿个Fans!”
相关问题
c语言二叉树层序遍历代码
下面是使用C语言实现二叉树层序遍历的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
/* 二叉树节点结构体 */
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
/**
* 创建新的二叉树节点
* @param val 节点值
* @return 新的二叉树节点
*/
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
/**
* 层序遍历二叉树
* @param root 二叉树根节点
*/
void levelOrder(struct TreeNode* root) {
if (root == NULL) {
return;
}
/* 创建队列 */
int front = 0, rear = 0;
struct TreeNode* queue[10000];
queue[rear++] = root;
/* 层序遍历 */
while (front < rear) {
/* 取出队列头部节点 */
struct TreeNode* node = queue[front++];
/* 输出节点值 */
printf("%d ", node->val);
/* 将左右子节点加入队列 */
if (node->left != NULL) {
queue[rear++] = node->left;
}
if (node->right != NULL) {
queue[rear++] = node->right;
}
}
}
int main() {
/* 创建二叉树 */
struct TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
/* 层序遍历二叉树 */
printf("Level order traversal: ");
levelOrder(root);
return 0;
}
```
以上代码中,使用队列实现层序遍历二叉树,时间复杂度为 O(n),其中 n 为二叉树节点数。
c语言二叉树层序遍历
二叉树的层序遍历是一种广度优先搜索算法,它按照层的顺序遍历二叉树的节点。下面是C语言实现二叉树层序遍历的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树的结构体
typedef struct BTnode {
char element;
struct BTnode *left;
struct BTnode *right;
} *BTnodePtr;
// 队列的结构体
typedef struct Queue {
BTnodePtr *data;
int front, rear;
int maxSize;
} *QueuePtr;
// 初始化队列
QueuePtr initQueue(int maxSize) {
QueuePtr q = (QueuePtr)malloc(sizeof(struct Queue));
q->data = (BTnodePtr*)malloc(sizeof(BTnodePtr) * maxSize);
q->front = q->rear = 0;
q->maxSize = maxSize;
return q;
}
// 判断队列是否为空
int isEmpty(QueuePtr q) {
return q->front == q->rear;
}
// 添加元素
void enqueue(QueuePtr q, BTnodePtr x) {
if ((q->rear + 1) % q->maxSize == q->front) {
printf("Queue is full.\n");
return;
}
q->data[q->rear] = x;
q->rear = (q->rear + 1) % q->maxSize;
}
// 删除元素
BTnodePtr dequeue(QueuePtr q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return NULL;
}
BTnodePtr x = q->data[q->front];
q->front = (q->front + 1) % q->maxSize;
return x;
}
// 创建结点
BTnodePtr createNode(char element) {
BTnodePtr node = (BTnodePtr)malloc(sizeof(struct BTnode));
node->element = element;
node->left = node->right = NULL;
return node;
}
// 创建二叉树
BTnodePtr createTree() {
BTnodePtr root = createNode('A');
root->left = createNode('B');
root->right = createNode('C');
root->left->left = createNode('D');
root->left->right = createNode('E');
root->right->left = createNode('F');
root->right->right = createNode('G');
return root;
}
// 层次遍历
void levelOrder(BTnodePtr root) {
QueuePtr q = initQueue(100);
enqueue(q, root);
while (!isEmpty(q)) {
BTnodePtr node = dequeue(q);
printf("%c ", node->element);
if (node->left != NULL) {
enqueue(q, node->left);
}
if (node->right != NULL) {
enqueue(q, node->right);
}
}
}
// 主函数
int main() {
BTnodePtr root = createTree();
printf("Level order traversal of binary tree is: ");
levelOrder(root);
printf("\n");
return 0;
}
```