C语言实现二叉树层次遍历介绍

目录
  • 什么是层次遍历？
  • 那我们如何来实现这个算法呢？
  • 主体代码：
  • 总结

什么是层次遍历？

对于一颗二叉树来说，从根节点开始，按从上到下、从左到右的顺序访问每一个结点。

注：每一个结点有且访问一次。

那我们如何来实现这个算法呢？

实现原理：

对于二叉树来说，它是一个递归的定义，我们要实现层次遍历必然要满足从上到下、从左到右这个要求，从根结点出发，我们可以将所有意义上的根结点都存储在队列之中，那我们可以使用队列先进先出的特点来实现要求的遍历。

这里我们需要引用队列来实现。

主体代码：

BiTree InitTree()//二叉树的创建
{
	BiTree T =(BiTree) malloc(sizeof(Tree));
	char data;
	scanf("%c", &data);
	getchar();
	if (data == '#')//如果data为#则该子树为空值
		return NULL;
	else {
		T->data = data;
		printf("请输入%c的左子树:\n", data);
		T->lchild = InitTree();
		printf("请输入%c的右子树:\n", data);
		T->rchild = InitTree();
	}
	return T;
}
void ShowCengci(BiTree T)
{
	LinkQueue qu;
	InitQueue(&qu);//初始化队列
	enQueue(&qu, T);//根结点入队
	while (QueueEmpty(qu))//判断队列中是否为空
	{
		BiTree S = deQueue(&qu);//根节点出队
		printf("%c ", S->data);
		if (S->lchild != NULL)//判断左右子树是否为空，不为空则入队
		{
			enQueue(&qu, S->lchild);
		}
		if (S->rchild != NULL)
		{
			enQueue(&qu, S->rchild);
		}
	}

队列的链式实现：

typedef struct BTree
{
	char data;
	struct BTree* lchild;
	struct BTree* rchild;
}Tree,*BiTree;
typedef struct Queue
{
	BiTree data;
	struct Queue* next;
}Qnode,*Queueptr;
typedef struct point
{
	Queueptr front;//头指针
	Queueptr rear;//尾指针
}LinkQueue;

void InitQueue(LinkQueue* qu)
{
	qu->front = qu->rear = (Queueptr)malloc(sizeof(Qnode));
	if (qu->front == NULL)
		return;
}
void enQueue(LinkQueue* qu, BiTree S)
{
	Queueptr p = (Queueptr)malloc(sizeof(Qnode));
	if (p == NULL) {
		return;
	}
	if (S == NULL)
		return;
	p->data = S;
	p->next = NULL;
	qu->rear->next = p;
	qu->rear = p;
}
int QueueEmpty(LinkQueue qu)
{
	if (qu.front != qu.rear)
		return 1;
	else
		return 0;
}
BiTree deQueue(LinkQueue* qu)
{
	if (qu->front == qu->rear)
		return;
	Queueptr p = qu->front->next;
	BiTree q = p->data;
	qu->front->next = p->next;
	if (qu->rear == p)
		qu->rear = qu->front;
	free(p);
	return q;
}

通关上述代码可以实现对二叉树的层次遍历。

总结

到此这篇关于C语言实现二叉树层次遍历介绍的文章就介绍到这了,更多相关C语言二叉树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言平衡二叉树详解

    C语言平衡二叉树详解

    目录 调整措施: 一.单旋转 二.双旋转 AVL树的删除操作: 删除分为以下几种情况: 1.要删除的节点是当前根节点T. 2.要删除的节点元素值小于当前根节点T值,在左子树中进行删除. 3.要删除的节点元素值大于当前根节点T值,在右子树中进行删除. 总结 平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树.这个方案很好的解决了二叉查找树退化成链表的

  • C语言二叉树与堆的概念与实现

    C语言二叉树与堆的概念与实现

    目录 引言-树的故事 树的基本性质和描述 树的基本特点 树的关键字解析 树的表示方法 二叉树的概念结构 特殊二叉树 二叉树的性质 二叉树的存储结构 二叉树与堆 堆的实现 堆排序 堆的功能实现 TOPK问题 二叉树的结构以及实现 二叉树的遍历 总结 引言-树的故事 在自然界中有很多树 它们是这样的 但是在我们的眼中 他是这样的 显而易见 树的特点就是一对多 ,我们利用这个一对多的特点,可以让我们更好的解决编程中的问题,在树中 ,最基础的二叉树是我们的重点研究对象. 在看一眼神奇的堆排序的动态图 做

  • C语言 链式二叉树结构详解原理

    C语言 链式二叉树结构详解原理

    目录 前言 二叉树节点声明 二叉树的遍历 构建二叉树 1.前序遍历 2.中序遍历 3.后序遍历 二叉树节点的个数 二叉树叶子节点的个数 二叉树第K层节点个数 二叉树的高度/深度 二叉树查找值为x的节点 整体代码 前言 二叉树不同于顺序表,一颗普通的二叉树是没有增删改查的意义.普通的二叉树用来存储数据是不方便的.但是二叉树的一些基本实现结构,例如前序遍历,中序遍历...等等都是对我们学习更深层次的二叉树打下夯实的基础. 二叉树节点声明 typedef char BTDataType; typede

  • 详细了解C语言二叉树的建立与遍历

    详细了解C语言二叉树的建立与遍历

    目录 这里给一个样例树: 总结 这里给一个样例树: 代码: #include <stdio.h> #include <string.h> #include <stdlib.h> /* 二叉树的二叉链表结点结构定义 */ typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree T=NULL; /* 先序遍历建立一个二叉树 */ void Cre

  • C语言二叉树的遍历示例介绍

    C语言二叉树的遍历示例介绍

    在本算法中先利用先序遍历创建了树,利用了递归的算法使得算法简单,操作容易,本来无printf("%c的左/右子树:", ch);的语句,但由于计算机需要输入空格字符来判断左右子树,为了减少人为输入的失误,特地加入这条语句,以此保证准确率. #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW 3 typedef int Status; typedef

  • C语言实现二叉树层次遍历介绍

    目录 什么是层次遍历? 那我们如何来实现这个算法呢? 主体代码: 总结 什么是层次遍历? 对于一颗二叉树来说,从根节点开始,按从上到下.从左到右的顺序访问每一个结点. 注:每一个结点有且访问一次. 那我们如何来实现这个算法呢? 实现原理: 对于二叉树来说,它是一个递归的定义,我们要实现层次遍历必然要满足从上到下.从左到右这个要求,从根结点出发,我们可以将所有意义上的根结点都存储在队列之中,那我们可以使用队列先进先出的特点来实现要求的遍历. 这里我们需要引用队列来实现. 主体代码: BiTree

  • C语言实现二叉树的基本操作

    二叉树是一种非常重要的数据结构.本文总结了二叉树的常见操作:二叉树的构建,查找,删除,二叉树的遍历(包括前序遍历.中序遍历.后序遍历.层次遍历),二叉搜索树的构造等. 1. 二叉树的构建 二叉树的基本构建方式为:添加一个节点,如果这是一棵空树,则将该节点作为根节点:否则按照从左到右.先左子树后右子树的顺序逐个添加节点.比如依次添加节点:1,6,10,2,7,11,则得到的二叉树为: 在这里,我们需要借助一个链表来保存节点,以实现二叉树的顺序插入,具体做法如下: 1.0 初始化一个用来保存二叉树节

  • C语言数据结构二叉树先序、中序、后序及层次四种遍历

    C语言数据结构二叉树先序、中序、后序及层次四种遍历

    目录 一.图示展示 (1)先序遍历 (2)中序遍历 (3)后序遍历 (4)层次遍历 (5)口诀 二.代码展示 一.图示展示 (1)先序遍历 先序遍历可以想象为,一个小人从一棵二叉树根节点为起点,沿着二叉树外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果 先序遍历结果为:A B D H I E J C F K G 动画演示: 记住小人沿着外围跑一圈(直到跑回根节点),多看几次动图便能理解 (2)中序遍历 中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最

  • C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】

    本文实例讲述了C语言二叉树常见操作.分享给大家供大家参考,具体如下: 一.基本概念 每个结点最多有两棵子树,左子树和右子树,次序不可以颠倒. 性质: 1.非空二叉树的第n层上至多有2^(n-1)个元素. 2.深度为h的二叉树至多有2^h-1个结点. 满二叉树:所有终端都在同一层次,且非终端结点的度数为2. 在满二叉树中若其深度为h,则其所包含的结点数必为2^h-1. 完全二叉树:除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐,即集中在左面的位置上,不能有空位置. 对于完全二叉

  • PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解

    本文实例讲述了PHP实现二叉树深度优先遍历(前序.中序.后序)和广度优先遍历(层次).分享给大家供大家参考,具体如下: 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 前序遍历:根节点->左子树->右子树 中序遍历:左子树->根节点->右子树 后序遍历:左子树->右子树->根节点 广度优先遍历:又叫层次遍历,从上往下对每一层依

  • C语言数据结构系列篇二叉树的遍历

    C语言数据结构系列篇二叉树的遍历

    目录 前言: Ⅰ. 定义二叉树 0x00二叉树的概念(回顾) 0x00定义二叉树 0x01 手动创建二叉树 Ⅱ. 二叉树的遍历 0x00关于遍历 0x01二叉树前序遍历 0x02二叉树中序遍历 0x03二叉树后序遍历 0x04层序遍历 前言: 学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建一颗简单的二叉树,用来方便大家学习.等二叉树结构了解的差不多后,后期我们会带大家研究二叉树地真正的创建方式.

  • C语言二叉树层序遍历

    C语言二叉树层序遍历

    实现下面图中的二叉树层序遍历 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <unistd.h> typedef struct node { char data; struct node *lchild; struct node *rchild; }NODE, *PNODE; typedef struct qnode { PNODE pnode; struct qno

  • C语言详解实现链式二叉树的遍历与相关接口

    C语言详解实现链式二叉树的遍历与相关接口

    目录 前言 一.二叉树的链式结构 二.二叉树的遍历方式 1.1 遍历方式的规则 1.2 前序遍历 1.3 中序遍历 1.4 后序遍历 1.5 层序遍历 三.二叉树的相关接口实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第 k 层节点个数 3.4 二叉树的深度(高度) 3.5 二叉树查找值为 x 的节点 3.6 总结 & 注意 四.二叉树的创建和销毁 4.1 通过前序遍历的字符串来构建二叉树 4.2 二叉树销毁 4.3 判断二叉树是否是完全二叉树 前言 二叉树的顺序结构就

  • C语言进阶二叉树的基础与销毁及层序遍历详解

    C语言进阶二叉树的基础与销毁及层序遍历详解

    单值二叉树 难度简单 如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树. 只有给定的树是单值二叉树时,才返回true:否则返回false. 示例 1: 输入:[1,1,1,1,1,null,1]输出:true 示例 2: 输入:[2,2,2,5,2]输出:false 提示: 给定树的节点数范围是[1, 100]. 每个节点的值都是整数,范围为[0, 99]. 解1: 最简单易懂的解法,先序遍历一遍,把每个节点都和那个根节点的val值相比.最后判断flag是否为真,若为假,则表明树中有

随机推荐