【数据结构】二叉树的层序遍历(四)

简介: 【数据结构】二叉树的层序遍历(四)

一,层序遍历概念

层序遍历:除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历;

设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根结点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历。

二,层序遍历的实现

       1,层序遍历的实现思路

层序遍历:按照每一行从左到右对二叉树的各个结点进行访问

但是呢,对一层访问结束了该如何访问下一层呢?就拿上图举例,访问完(4)结点后该如何访问(3)结点呢?(4)结点中并没有(3)结点的信息;

算法思路:

可以借助一个队列,首先将二叉树的根结点入队,然后访问出队结点并出队,如果有左孩子结点,左孩子结点也入队;如果有右孩子结点,右孩子结点也入队。然后访问出队结点并出队,直到队列为空为止

过程演示:


(1)入队列,访问队头结点(1),然后(1)出队列,此时(1)的左子树(2)右子树(4)相继入队列;此时队列: 头<---- (2)(4)    <---尾


访问队头结点(2),然后(2)出队列,此时(2)的左子树(3)入队列,此时队列:(4)(3)


访问队头结点(4),然后(4)出队列,此时(4)的左子树(5)右子树(6)相继入队列;


此时队列:(3)(5)(6)


访问队头结点(3),然后(3)出队列,因为(3)没有左右子树,此时没有数据入队列,此时队列:(5)(6)


访问头结点(5),然后(5)出队列,此时队列:(6)


访问头结点(6),然后(6)出队列,此时队列:NULL,结束!


下面是另一棵二叉树的遍历来帮助我们理解;


       2,创建队列

首先我们得创建一个队列,队列具体细节就不过多解释了,之前博客有专门的详细介绍过;

队列的性质:先进先出,也就是尾插,头删的单链表;

     Queue.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"BTree.h"
typedef BTNode* QDataType;
//结点
typedef struct QListNode
{
  struct QListNode* next;
  QDataType data;
}QNode;
// 队列
typedef struct Queue
{
  QNode* front; // 队头
  QNode* rear; //队尾
  int size;
}Queue;
// 初始化队列 
void QueueInit(Queue* q);
// 队头入队列 
void QueuePush(Queue* q, QDataType data);
// 队尾出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 判空
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

   Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
// 初始化队列 
void QueueInit(Queue* q)
{
  assert(q);
  q->front = q->rear = NULL;
  q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  newnode->next = NULL;
  newnode->data = data;
  if (q->front /*= q->rear*/ == NULL)//谨记判断不要用此等格式
  {
    q->front = q->rear = newnode;
  }
  else
  {
    q->rear->next = newnode;
    q->rear = newnode;
  }
  q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  if (q->front->next == NULL)
  {
    free(q->front);
    q->front = q->rear = NULL;
  }
  else
  {
    QNode* next = q->front->next;
    free(q->front);
    q->front = next;
  }
  q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q)
{
  assert(q);
  return q->size == 0;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  QNode* next = NULL;
  while (cur)
  {
    next = cur->next;
    free(cur);
    cur = next;
  }
  cur = NULL;
  q->rear = NULL;
}

这队列已经构造完成了,我们还需要一棵二叉树;

       3,创建二叉树

二叉树之前我们也创建过,现在也不过多介绍了,直接上硬菜!

       BTree.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int BTDataType;
//二叉链
typedef struct BinaryTreeNode
{
  BTDataType data; // 当前结点值域  
  struct BinaryTreeNode* left; // 指向当前节点左孩子
  struct BinaryTreeNode* right; // 指向当前节点右孩子
}BTNode;
//动态创立新结点
BTNode* BuyNode(BTDataType x);
//创建二叉树
BTNode* GreatBTree();

   BTree.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"BTree.h"
#include"Queue.h"
//动态创立新结点
BTNode* BuyNode(BTDataType x)
{
  BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
  assert(newnode);
  newnode->data = x;
  newnode->left = NULL;
  newnode->right = NULL;
  return newnode;
}
//创建二叉树
BTNode* GreatBTree()
{
  BTNode* node1 = BuyNode(1);
  BTNode* node2 = BuyNode(2);
  BTNode* node3 = BuyNode(3);
  BTNode* node4 = BuyNode(4);
  BTNode* node5 = BuyNode(5);
  BTNode* node6 = BuyNode(6);
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  return node1;
}

这个队列和二叉树的 .c文件都要包含彼此的头文件,将他们链接起来;

       4,层序遍历的实现

按照之前的分析思路,以此构建代码;

//层序遍历
void LevelOrder(BTNode* root)
{
  Queue q;
  // 初始化队列 
  QueueInit(&q);
  // 队尾入队列 
  if (root)
  {
    QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
    printf("%d ", QueueFront(&q)->data);
    BTNode* cur = QueueFront(&q);
    // 队头出队列
    QueuePop(&q);
    if (cur->left)
    {
      QueuePush(&q, cur->left);
    }
    if (cur->right)
    {
      QueuePush(&q, cur->right);
    }
  }
}
int main()
{
  BTNode* root = GreatBTree();
  //层序遍历
  LevelOrder(root);
  return 0;
}

确实是一层一层进行遍历的;

之前的遍历都是递归实习的,而层序遍历是循环实现的,目前用c语言来实现的话因为没有队列的库,实现起来特别的繁琐,不过好理解,本身并不难,这就是层序遍历的实现;

第四阶段带大家了实现了层序遍历,后序会带大家刷一会经典题目来进行巩固;

后面博主会陆续更新;

如有不足之处欢迎来补充交流!

完结。

目录
相关文章
|
21天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
76 8
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
24 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
1月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
26 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
1月前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
28 1
|
1月前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
25 1
|
1月前
|
存储
【数据结构】二叉树链式结构——感受递归的暴力美学
【数据结构】二叉树链式结构——感受递归的暴力美学
|
1月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
1月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
27 0
|
1月前
|
存储 算法
【数据结构】二叉树——顺序结构——堆及其实现
【数据结构】二叉树——顺序结构——堆及其实现
|
1月前
|
存储
【数据结构】二叉树零基础无压力上手,超详解
【数据结构】二叉树零基础无压力上手,超详解
28 0