树:二叉树的层序遍历算法(超简洁实现及详细分析)

树:二叉树的层序遍历算法(超简洁实现及详细分析)实现思路我们来看看下图的二叉链表如何实现层序遍历。层序遍历顺序:ABECDGA为B、E的双亲结点,遍历顺序是根->左->右是不是。而且每个结点都是这样的遍历顺序有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队,出队时将其左右孩子入队,循环队列进行出队,每次出队将其左右孩子入队。当队列为空时,整棵树层序遍历完毕。还没明白请看下面过程。A-&g…

大家好,又见面了,我是你们的朋友全栈君。

实现思路

我们来看看下图的二叉链表 如何实现层序遍历

树:二叉树的层序遍历算法(超简洁实现及详细分析)

层序遍历顺序:ABECDG
A为B、E的双亲结点,遍历顺序是 根->左->右 是不是。
而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队,出队时将其左右孩子入队,循环队列进行出队,每次出队将其左右孩子入队。当队列为空时,整棵树层序遍历完毕。还没明白请看下面过程。
A->出队
队列:E、B
B->出队
队列:D、C、E
E->出队
队列:G、D、C
C->出队
队列:G、D
D->出队
队列:G
G->出队
队列为空,层序遍历完毕

二叉树层序遍历算法代码

层序遍历函数

层序遍历核心代码,利用了一个自己底层封装的顺序队列如果想知道怎么实现的呢,请看线性表:顺序队列算法实现

//一排一排的遍历 利用队列的特性哟,将根结点入队列 然后然后出入队列,出队列后将其左右孩子结点入队列
//直到队列为空
void SeqTraverse(BiTree tree)
{
	SeqQueue queue = Init_SeqQueue();
	Push_SeqQueue(queue, tree);
	while (!IsEmpty_SeqQueue(queue))
	{
		BiTree root = Pop_SeqQueue(queue);
		printf("%c ", root->data);
		if (root->lchild)
			Push_SeqQueue(queue, root->lchild);
		if(root->rchild)
			Push_SeqQueue(queue, root->rchild);
	}
	printf("\n");
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include "SeqQueue.h"
typedef char ElemType;
typedef struct BiNode
{
	ElemType data;
	struct BiNode* lchild;
	struct BiNode* rchild;
}BiNode, *BiTree;

//创建二叉链表
void CreateBiTree(BiTree* tree) 
{
	char c;
	scanf("%c", &c);
	if (c == ' ')
	{
		*tree = NULL;
		return;
	}
	*tree = malloc(sizeof(BiNode));
	(*tree)->data = c;
	CreateBiTree(&(*tree)->lchild);
	CreateBiTree(&(*tree)->rchild);
	return;
}
//二叉链表 递归前序遍历
void PreTraverse(BiTree tree)
{
	if (tree == NULL)
	{
		return;
	}
	printf("%c ", tree->data);
	PreTraverse(tree->lchild);
	PreTraverse(tree->rchild);
}

//一排一排的遍历 利用队列的特性哟,将根结点入队列 然后然后出入队列,出队列后将其左右孩子结点入队列
//直到队列为空
void SeqTraverse(BiTree tree)
{
	SeqQueue queue = Init_SeqQueue();
	Push_SeqQueue(queue, tree);
	while (!IsEmpty_SeqQueue(queue))
	{
		BiTree root = Pop_SeqQueue(queue);
		printf("%c ", root->data);
		if (root->lchild)
			Push_SeqQueue(queue, root->lchild);
		if(root->rchild)
			Push_SeqQueue(queue, root->rchild);
	}
	printf("\n");
}

int main(int argc, char *argv[])
{
	BiTree tree = NULL;
	printf("请前序遍历输入结点:");
	CreateBiTree(&tree);
	printf("前序遍历:");
	PreTraverse(tree);
	printf("\n层序遍历:");
	SeqTraverse(tree);
	
	return 0;
}

代码运行检测

我们构建如下图的二叉树,注意创建二叉树输入序列为:ABC__D__E_G__,_代表一个空格哟。

树:二叉树的层序遍历算法(超简洁实现及详细分析)

运行结果

树:二叉树的层序遍历算法(超简洁实现及详细分析)

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/143355.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • createprocess error=2_CreateProcess

    createprocess error=2_CreateProcessOpenProcess函数声明如下,失败则返回NULL(0,也就是false)#include<Windows.h>HANDLEOpenProcess(DWORDdesiredAccess,//读取权限BOOLblnheritHandle,//是否继承DWORDprocessId//想要读取的PID)代码示例,注意下面的代码可能运行失败,请按照如下设置VS右键项目名(例如ConsoleApplication123)->属性->配置属性(注意左上角是活动D

  • c++容器类_类的容器

    c++容器类_类的容器什么是容器首先,我们必须理解一下什么是容器,在C++中容器被定义为:在数据存储上,有一种对象类型,它可以持有其它对象或指向其它对像的指针,这种对象类型就叫做容器。很简单,容器就是保存其它对象的对象,当然这是一个朴素的理解,这种“对象”还包含了一系列处理“其它对象”的方法,因为这些方法在程序的设计上会经常被用到,所以容器也体现了一个好处,就是“容器类是一种对特定代码重用问题的良好的解决方案”

  • Java中JDK和JRE的区别是什么?它们的作用分别是什么?「建议收藏」

    Java中JDK和JRE的区别是什么?它们的作用分别是什么?「建议收藏」DearAll:首先请允许我为大家介绍下什么是Jre?什么是jdk?JRE:首先请允许我为大家介绍下什么是Jre?什么是jdk?JRE:首先请允许我为大家介绍下什么是Jre?什么是jdk?

  • Mysql的两种引擎的区别

    Mysql的两种引擎的区别

  • 一天入门51单片机教程

    一天入门51单片机教程本套教程共3节课程,熟悉这3节课程的话,你已经入门51单片机了。下面是内容正文单片机学习的第一步,什么是单片机最小系统?我来打个比喻吧.我们都知道,人的大脑是可以控制眼耳口鼻,手脚,全身等等,这就说明,大脑是我们人体的控制中心,人体能控制的地方,都是由大脑管理的..而单片机就像我们的大脑,作为一个控制中心,去控制我们想要控制的东西...为什么要控制呢?好像一成不变枯燥的工作,如果是人处理的话,做的时间长一点,他会说累,说无聊,而单片机则不会,只要你给它编写好程序,它会默默无闻地重复

  • mysql 在命令行和navicat 查出来的数据不一致,你遇到过吗?[通俗易懂]

    mysql 在命令行和navicat 查出来的数据不一致,你遇到过吗?

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号