【数据结构】链式二叉树的层序遍历

简介: 【数据结构】链式二叉树的层序遍历

前言

  二叉树除了有前序遍历,中序遍历,后序遍历外,还有一个层序遍历,二叉树的层序遍历相比较于前三个稍微复杂一点,我们将在本篇文章详细分析一下层序遍历是怎么实现的。

一、层序遍历的概念

  二叉树的层序遍历就跟它的名字一样,一层一层遍历。先遍历第一层的根结点,再从左往右遍历第二层,接着是第三层,直到遍历完整个二叉树为止。

  emmmm,看起来层序遍历也不是很难嘛,但感觉…嘶,不知道咋实现啊哈哈🤣🤣🤣。那接下来我们就好好分析分析。

二、层序遍历的思想

  其实有一个比较好想到的一点:先遍历根结点,然后再 准备 遍历根结点的孩子,每遍历到一个结点,就准备遍历其孩子,意思就是,我得找一个空间或者一个结构,能够保存我准备遍历的结点的顺序。那么什么结构可以呢,先准备遍历的要先遍历,后准备遍历的要后遍历。啊,有了,使用队列!

  队列有个特点,数据都是先进先出的,非常符合我们层序遍历的思想。我们可以先让根结点入队列,队列每出一个数据,就让其左右孩子结点入队列,那么就能完美解决了。

三、代码实现

1.引入库函数头文件及函数声明

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 宏定义数据类型
typedef char BTDataType;
// 链式二叉树结构体
typedef struct BinaryTreeNode
{
    // 数据域
  BTDataType data;
  // 指向左孩子的指针域
  struct BinaryTreeNode* left;
  // 指向右孩子的指针域
  struct BinaryTreeNode* right;
}BTNode;
// 通过前序遍历构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi);
// 二叉树销毁
void BinaryTreeDestroy(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 队列的数据类型,存的是 二叉树结构体指针 类型
typedef struct BinaryTreeNode* QDataType;
// 队列的结构体
typedef struct QueueNode
{
  // 队列的数据域
  QDataType val;
  // 队列的指针域
  struct QueueNode* next;
}QNode;
// 传参结构体
typedef struct Queue
{
  // 有一个指向队列的头结点(队头)的指针
  QNode* phead;
  // 有一个指向队列的尾节点(队尾)的指针
  QNode* ptail;
  // 队列的元素个数
  int size;
}Queue;
// 初始化队列
void QueueInit(Queue* pq);
// 销毁队列
void QueueDestroy(Queue* pq);
// 在队尾插入
void QueuePush(Queue* pq, QDataType x);
// 在队头弹出
void QueuePop(Queue* pq);
// 查询队头元素
QDataType QueueFront(Queue* pq);
// 判断队列是否为空
bool QueueEmpty(Queue* pq);

2.其他函数实现

// 通过前序遍历构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi)
{
    // 如果数组第*pi的值为‘#’,说明遇到了空结点,说明该结点不存在
  if (a[*pi] == '#')
  {
      // 准备查看数组的下一个元素
    ++(*pi);
    // 返回空
    return NULL;
  }
    // 如果当前值不为空
    // 为当前结点开辟一个新的二叉树结构体大小的空间
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  // 开辟空间失败
  if (!root)
  {
      // 弹出反馈
    perror("malloc fail");
    // 退出程序
    exit(-1);
  }
    // 开辟空间成功
    // 将当前的数组的值赋值给该结点的数据域,并让*pi增加1,准备查看下一个数组元素
  root->data = a[(*pi)++];
  // 递归传回该结点的左孩子的地址
  root->left = BinaryTreeCreate(a, pi);
  // 递归传回该结点的右孩子的地址
  root->right = BinaryTreeCreate(a, pi);
  // 返回当前结点的地址
  return root;
// 二叉树销毁
void BinaryTreeDestroy(BTNode* root)
{
    // 空结点直接返回
  if (!root)
    return;
  
  // 递归左孩子
  BinaryTreeDestroy(root->left);
  // 递归右孩子
  BinaryTreeDestroy(root->right);
  // 销毁根结点
  free(root);
}
// 队列接口函数
// 队列初始化
// 传入传参结构体成员的地址
void QueueInit(Queue* pq)
{
  // pq是指向传参结构体的指针,只要结构体创建了,那pq就不可能为空,为空说明传参错误或者结构体没创建
  assert(pq);
  
  // 让指向首元结点的头指针和指向尾结点的尾指针置空,说明队列为空
  pq->phead = pq->ptail = NULL;
  // 队列目前有效数据为0
  pq->size = 0;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{
    // pq不可能为空,可以断言一下以免出现小差错
  assert(pq);
    // 如果pq指向的结构体里面的phead不为空,即存在结点
  while (pq->phead)
  {
      // 创建一个临时指针变量指向首元结点
    QNode* tmp = pq->phead;
    // 让phead指向第二个结点
    pq->phead = pq->phead->next;
    // 释放首元结点空间
    free(tmp);
    // 释放空间后指针置空是好习惯
    tmp = NULL;
  }
  // 最后没有结点的时候,把尾结点置空
  pq->ptail = NULL;
  // 让有效数据大小为0
  pq->size = 0;
}
// 入队列
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  // 为新结点开辟空间
  QNode* newNode = (QNode*)malloc(sizeof(QNode));
  // 开辟失败时
  if (newNode == NULL)
  {
      // 弹出反馈
    perror("malloc fail");
    // 终止程序
    exit(-1);
  }
  // 为新结点赋值
  newNode->val = x;
  newNode->next = NULL;
  // 当队列为空时
  if (pq->ptail == NULL)
  {
      // 头指针指向新结点
    pq->phead = pq->ptail = newNode;
  }
  // 当队列非空时
  else
  {
      // 原尾结点的指针域指向新结点
    pq->ptail->next = newNode;
    // 尾指针指向新结点
    pq->ptail = newNode;
  }
  // 队列的有效个数+1
  ++pq->size;
}
// 出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  // 队列为空不能删除
  assert(pq->phead);
    // 临时指针指向首元结点
  QNode* tmp = pq->phead;
  // 当队列中只有一个结点时
  if (pq->phead == pq->ptail)
  {
      // 将两个指针置空
    pq->phead = pq->ptail = NULL;
  }
  // 当队列中不止一个结点时
  else
  {
      // 让头结点指向第二个结点
    pq->phead = pq->phead->next;
  }
  // 有效数据个数-1
  --pq->size;
  // 释放原首元结点的空间
  free(tmp);
  // 释放空间后指针置空
  tmp = NULL;
}
// 查询队头数据
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  // 队列不为空才有队头数据
  assert(pq->phead);
    
    // 根据头指针找到队头数据
  return pq->phead->val;
}
// 判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
    // 返回队列有效数据的个数是否等于0来判断队列是否为空
  return pq->size == 0;
}

  这里需要注意的是,队列内存放的是指向链式二叉树结构体的指针,所以在宏定义队列的数据类型的时候,要将链式二叉树的结构体名称宏定义为 QDataType 。

3.层序遍历函数

void BinaryTreeLevelOrder(BTNode* root)
{
  // 创建一个队列
  Queue q;
  // 初始化队列
  QueueInit(&q);
  // 如果根结点存在,则将根结点入队
  if (root)
    QueuePush(&q, root);
  // 如果队列非空
  while (!QueueEmpty(&q))
  {
    // 获取队头元素
    BTNode* front = QueueFront(&q);
    // 打印队头元素
    printf("%c", front->data);
    // 如果左孩子非空
    if (front->left)
      // 左孩子入队
      QueuePush(&q, front->left);
    // 如果右孩子非空
    if (front->right)
      // 右孩子入队
      QueuePush(&q, front->right);
    // 弹出队头元素
    QueuePop(&q);
  }
  // 队列已经空了,说明遍历结束,销毁队列
  QueueDestroy(&q);
}

  该函数的主要思想就是,每次让队头元素出队列的时候,让其左右孩子入队列,由于左孩子先比右孩子入队列,所以左孩子就比右孩子出队列,左孩子的孩子就会先入队列。但是一旦父结点出了队列,就会被销毁,就无法借其找到其左孩子和右孩子,所以在出队列前需要先入队列,再将队头元素出队列。

4.主函数

int main()
{
    // 创造二叉树数据
  char a[] = "ABD##E#H##CF##G##";
  int b = 0;
  // 通过前序遍历的方式读取数组数据建立二叉树
  BTNode* root = BinaryTreeCreate(a, &b);
  printf("二叉树的层序遍历:");
  // 层序遍历
  BinaryTreeLevelOrder(root);
  printf("\n");
  // 销毁二叉树
  BinaryTreeDestroy(root);
  // 销毁空间后指针置空
  root = NULL;
  return 0;
}

5.结果演示

  我们通过数组构建的链式二叉树长这样:

  根据层序遍历的性质,我们可以求出,层序遍历的结果应该是:ABCDEFGH 。来看看结果:

  完美。

总结

  层序遍历主要就是利用队列结构,通过有序的入队列和出队列来达成层序遍历的效果,虽然相比较于二叉树的前,中,后序遍历来说有点不一样,但是在理解了队列的结构和实现,搭配一下构建二叉树,就能轻松写出层序遍历。

  博主水品有限,若是发现文章中出现错误,还请大家不吝赐教。谢谢。

目录
相关文章
|
1天前
|
数据库
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
|
1月前
|
机器学习/深度学习 存储 算法
数据结构实验之二叉树实验基础
本实验旨在掌握二叉树的基本特性和遍历算法,包括先序、中序、后序的递归与非递归遍历方法。通过编程实践,加深对二叉树结构的理解,学习如何计算二叉树的深度、叶子节点数等属性。实验内容涉及创建二叉树、实现各种遍历算法及求解特定节点数量。
85 4
|
1月前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
132 8
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
32 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
37 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
33 1
|
2月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
30 1
|
2月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
2月前
|
存储 编译器 C++
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
【初阶数据结构】掌握二叉树遍历技巧与信息求解:深入解析四种遍历方法及树的结构与统计分析
|
2月前
|
存储 算法 调度
数据结构--二叉树的顺序实现(堆实现)
数据结构--二叉树的顺序实现(堆实现)

热门文章

最新文章