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

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树的层序遍历(四)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 目录

一,层序遍历概念

二,层序遍历的实现

        1,层序遍历的实现思路

        2,创建队列

        Queue.h

        Queue.c

        3,创建二叉树

        BTree.h

        BTree.c

        4,层序遍历的实现


一,层序遍历概念

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

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

【数据结构】二叉树的层序遍历(四),数据结构,算法,开发语言,c语言,排序算法

二,层序遍历的实现

        1,层序遍历的实现思路

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

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

【数据结构】二叉树的层序遍历(四),数据结构,算法,开发语言,c语言,排序算法

算法思路:

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

过程演示: 

(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,结束!

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

【数据结构】二叉树的层序遍历(四),数据结构,算法,开发语言,c语言,排序算法

        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语言,排序算法 确实是一层一层进行遍历的;

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

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

后面博主会陆续更新;

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

完结。文章来源地址https://www.toymoban.com/news/detail-723532.html


到了这里,关于【数据结构】二叉树的层序遍历(四)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】前中后层序遍历 --二叉树的结构特点与遍历方式

      Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。 🌈个人主页:主页链接 🌈算法专栏:专栏链接       我会一直往里填充内容哒! 🌈LeetCode专栏:专栏链接       目前在刷初级算法的LeetBook 。若每日一题当中有力所能

    2023年04月09日
    浏览(84)
  • ★102. 二叉树的层序遍历

    很巧妙的,又学习了一种层次遍历的方法, 就是说根据当前的队列的长度去遍历,遍历的当前队列的长度就是该层次的节点个数。

    2024年02月05日
    浏览(45)
  • 41 二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 提示: 树中节点数目在范围 [0, 2000] 内 -1000 = Node.val = 1000

    2024年02月07日
    浏览(47)
  • 二叉树题目:二叉树的层序遍历 II

    标题:二叉树的层序遍历 II 出处:107. 二叉树的层序遍历 II 4 级 要求 给你二叉树的根结点 root texttt{root} root ,返回其结点值自底向上的层序遍历(即从左到右,按从叶结点所在层到根结点所在层逐层遍历)。 示例 示例 1: 输入: root   =   [3,9,20,null,null,15,7] texttt{root = [3

    2024年02月11日
    浏览(37)
  • 【数据结构】二叉树的前序遍历、中序遍历、后序遍历、层序遍历

    文章目录 1.二叉树的概念 1.1概念 1.2存储方式 1.3特殊的二叉树  1.4规律 2.二叉树的实现 2.1表现方式 2.2遍历     2.2.1前序遍历   思想   代码   详细分析      2.2.2中序遍历     2.2.3后序遍历     2.2.4层序遍历   思想   代码   详细过程         一棵二叉树是结点的一

    2024年04月23日
    浏览(38)
  • 算法进阶——求二叉树的层序遍历

    题目 给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)。 例如: 给定的二叉树是{3,9,20,#,#,15,7}, 该二叉树层序遍历的结果是 [ [3], [9,20], [15,7] ] 提示: 0 = 二叉树的结点数 = 1500 示例1 示例2 思路 利用辅助队列,通过bfs(广度优先)算法遍历二叉树

    2024年01月24日
    浏览(47)
  • 【C++】102.二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例1: 示例 2: 示例 3: 提示: 树中节点数目在范围 [0, 2000] 内 -1000 = Node.val = 1000 这个问题实际上可以只用一个队列就实现,只需要再增加一个变量 levelSize ,用来记录每一层

    2024年03月11日
    浏览(49)
  • 【LeetCode】102.二叉树的层序遍历

    给你二叉树的根节点  root  ,返回其节点值的  层序遍历  。 (即逐层地,从左到右访问所有节点)。 示例 1: 示例 2: 示例 3: 提示: 树中节点数目在范围  [0, 2000]  内 -1000 = Node.val = 1000 之前做的题里深度优先遍历(DFS)用得比较多,主要是回溯算法,这道题的层序遍

    2024年02月15日
    浏览(42)
  • day-20 二叉树的层序遍历

    思路:利用队列进行广度优先遍历即可 注意点:ArrayList执行remove之后,索引i会立即重排,注意可能越界 code:

    2024年03月19日
    浏览(49)
  • 每日一题 102二叉树的层序遍历

    给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1: 输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]] 示例 2: 输入:root = [1] 输出:[[1]] 示例 3: 输入:root = [] 输出:[] 提示: 树中节点数目在范围 [0, 2000] 内 -1000 =

    2024年02月09日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包