109.【C语言】数据结构之二叉树层序遍历

ops/2024/12/12 19:04:03/

1.知识回顾

2.代码实现

准备工作

LevelOrder函数

代码框架

关键代码

3.执行结果

1.知识回顾

层序遍历参见106.【C语言】数据结构之二叉树的三种递归遍历方式文章

截取的部分内容

定义:按层的方式遍历(,设n为树的深度,h==1-->h==2-->h==3-->...-->h==n)

以下面这张图为例子

遍历顺序:1-->2-->4-->3-->5-->6

h==1为第一层,只有1;h==2为第二层,有2和4;h==3为第三层,有3,5和6;

2.代码实现

这里用的是队列,画图分析上方二叉树的层序遍历

会发现出队的顺序恰好是层序遍历的结果! (注意空节点不入队)

核心思想:先出队一个根节点,后将根的左右非空节点入队

准备工作

直接借用98.【C语言】数据结构之队列文章的队列代码,将其载入到VS的解决方案

这里需要对原代码左一点修改

Queue.h修改为

typedef struct QueueNode* QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;

队列的每个节点是一个结构体,既存储了树的节点的地址又存储了下一个节点的地址(这样做方便操作)

LevelOrder函数

代码框架

养成良好的习惯先写初始化和销毁

void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);//......QueueDestroy(&q);
}

关键代码

非空节点才能入队

以"知识回顾"的二叉树画图分析if (root) {QueuePush(&q,root);}后的图

	if (root)QueuePush(&q,root);while (!QueueEmpty(&q)){//先出队一个根节点BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ", front->data);//后将根的左右非空节点入队if (front->left)QueuePush(&q, front->left);if (front->right)QueuePush(&q, front->right);}

QueuePop是将data和next都销毁(记得销毁前先保留data数据备用打印)

可以看到QueuePop的free(pq->head);

void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);QNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL)pq->tail = NULL;pq->size--;
}