精华内容
下载资源
问答
  • 二叉树的层次遍历c
    2022-08-06 16:59:50

             二叉树层次遍历思路就是使用队列进行存储,当出队一个元素,则将其左右子树入队。

    #define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #include<stdlib.h>
    
    
    #define MaxSize 10
    
    
    
    typedef struct Tree {
    
    	int data;					//	存放数据域
    	struct Tree* lchild;			//	遍历左子树指针
    	struct Tree* rchild;			//	遍历右子树指针
    
    }Tree, * BitTree;
    //队的数据结构
    typedef struct sqqueue
    {
    	BitTree data[MaxSize];
    	int front,
    		rear;
    }sqqueue;
    
    //初始化
    void Initqueue(sqqueue* s)
    {
    	s->front = s->rear = 0;
    }
    //判断是否为空
    int queueEmpty(sqqueue s)
    {
    	return s.front == s.rear;
    }
    //入队
    void EnQueue(sqqueue* s, int x)
    {
    	if ((s->rear + 1) % MaxSize == s->front)
    	{
    		printf("队满");
    		return;
    	}
    	s->data[s->rear] = x;
    	s->rear = (s->rear + 1) % MaxSize;
    }
    //出队
    void OutQueue(sqqueue* s)
    {
    	s->front = (s->front + 1) % MaxSize;
    }
    
    
    
    
    
    
    BitTree CreateLink()
    {
    	int data;
    	int temp;
    	BitTree T;
    
    	scanf("%d", &data);		//	输入数据
    	temp = getchar();			//	吸收空格
    
    	if (data == -1) {			//	输入-1 代表此节点下子树不存数据,也就是不继续递归创建
    
    		return NULL;
    
    	}
    	else {
    		T = (BitTree)malloc(sizeof(Tree));			//		分配内存空间
    		T->data = data;								//		把当前输入的数据存入当前节点指针的数据域中
    
    		printf("请输入%d的左子树: ", data);
    		T->lchild = CreateLink();					//		开始递归创建左子树
    		printf("请输入%d的右子树: ", data);
    		T->rchild = CreateLink();					//		开始到上一级节点的右边递归创建左右子树
    		return T;							//		返回根节点
    	}
    
    }
    void levelOrder(BitTree T)
    {
    	sqqueue s;
    	Initqueue(&s);
    	EnQueue(&s,T);
    	BitTree P;
    	while (!queueEmpty(s))
    	{
    		printf("%d\t",s.data[s.front]->data);
    		P = s.data[s.front];
    		OutQueue(&s);
    		if(P->lchild!=NULL)
    			EnQueue(&s, P->lchild);
    		if(P->rchild!=NULL)
    			EnQueue(&s, P->rchild);
    	}
    }
    
    
    int main()
    {
    	BitTree S;
    	printf("请输入第一个节点的数据:\n");
    	S = CreateLink();			//		接受创建二叉树完成的根节点
    	printf("\n层次遍历结果: \n");
    	levelOrder(S);
    	return 0;
    }
    

    更多相关内容
  • C语言实现二叉树层次遍历

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

    什么是层次遍历?

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

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

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

    实现原理:

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

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

    主体代码:

    
    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;
    }
    

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

    展开全文
  • 二叉树层次遍历详解

    2022-06-30 22:01:26
    二叉树层次遍历

    1.层次遍历算法图解

     

     

     

     

     

     

    2.算法代码实现。

    真实环境中二叉树的节点是不确定的,所以应用链式队列来进行存储二叉树的节点。

    //层次遍历二叉树
    bool LevelOrder(BitTree T) {
    	if (!T) {
    		return false;
    	}
    	LinkQueue Q;
    	initLinkQueue(Q);   //初始化链式队列
    	EnLinkQueue(Q, T);   //将树的根节点入队
    	BiTNode* p = NULL;    //用来存储出队的结点
    	while (!isEmpty(Q)) {   //循坏扫描队列是否为空
    		DelinkQueue(Q, p);  //出队列的首元素
    		VisitT(p);          //访问出队列的元素
    		if (p->lchild) {     //如果出队列的结点有左孩子,将其入队
    			EnLinkQueue(Q, p->lchild);
    		}
    		if (p->rchild) {      //如果出队列的结点有有孩子,将其入队
    			EnLinkQueue(Q, p->rchild);
    		}
    	}
    }

     

    展开全文
  • 二叉树层次遍历算法

    千次阅读 多人点赞 2020-08-27 01:23:39
    层次遍历 其实记住以上的输出顺序还是非常简单的。首先要明白,左节点一定先比右节点输出! 那么就很好理解了,那么那些所谓的前序、中序、后序而言是针对根节点的相对位置命名的。 例如前序遍历,则就是根节点是最...

    在二叉树中,我们常见的遍历方式 主要有四种。分别是:

    • 前序遍历(根节点->左节点->右节点)
    • 中序遍历(左节点->根节点->右节点)
    • 后序遍历(左节点->右节点->根节点)
    • 层次遍历

    其实记住以上的输出顺序还是非常简单的。首先要明白,左节点一定先比右节点输出
    那么就很好理解了,那么那些所谓的前序、中序、后序而言是针对根节点的相对位置命名的。
    例如前序遍历,则就是根节点是最前面输出的,所以我们不难得到,前序遍历的顺序为:根节点->左节点->右节点。其他同理。

    那么今天介绍下一种不同的方式—层次遍历。注意层次队列不能使用递归来完成,并且需要借助一个队列来帮我们完成整个过程的遍历!

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    #define  ElemType char
    #define maxSize 100
    typedef struct Tree{
    	ElemType data;
    	struct Tree * rchild;
    	struct Tree * lchild;
    }Tree,*Treep;
    
    /*
    	采用前序遍历的思想创建二叉树 
    */ 
    void createTree(Tree * &p){
    	char c;
    	scanf("%c",&c);
    	if(c == ' '){
    		return;
    	}
    	p = (Tree *)malloc(sizeof(Tree));
    	p->data = c;
    	p->lchild = NULL;
    	p->rchild = NULL;
    	createTree(p->lchild);
    	createTree(p->rchild);
    	
    }
    /*
    	该算法的主要思想是
    		1. 输出根节点的值
    		2. 把该节点的左孩子添加到队列
    		3. 把该节点的右孩子添加到队列
    		4. 从队列一一取出 重复上述步骤。
    		 
    		在遍历当前层次的时候,输出当前节点,并把下一层次
    		的节点按左右节点顺序存入队列。
    		队列的特点是:先进先出 那么这就很好的利用了队列的特点
    		达到了层次遍历的效果。 
    */ 
    void levelPrint(Tree * p){
    	//初始化一个非循环队列
    	Treep stack[maxSize];
    	int front,real;
    	front = real = 0;
    	Tree *curr ,*pre;
    	pre = p;
    	while(pre != NULL){
    		// 输出当前节点的值 
    		cout<<pre->data;
    		// 拿到当前节点的左孩子指针 
    		curr = pre->lchild;
    		//如果左孩子不为空 入队!
    		if(curr != NULL){
    			stack[real++] = curr;
    		}
    		// 如果右孩子不为空 入队! 
    		curr = pre->rchild;
    		if(curr != NULL){
    			stack[real++] = curr;
    			
    		}
    		// 如果队列不为空则从队列取出元素 
    		if( front != real) 
    			pre = stack[front++];
    		else //否则直接置空指针 
    			pre = NULL;
    		
    	}
    }
    
    int main(int argc, char** argv) {
    	Tree *root;
    	// 前序创建二叉树 
    	createTree(root);
    	// 层次遍历二叉树 
    	levelPrint(root);
    	return 0;
    }
    
    展开全文
  • 一、二叉树的概念以及结构 二叉树是n(n>=0)个节点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组。...层次遍历 ...
  • 二叉树层次遍历 提示:以下是本篇文章正文内容,下面案例可供参考 一、代码实现 代码如下(示例): #include <stdio.h> #include <stdlib.h> //二叉树 typedef struct BiTNode { BiTNode* ...
  • 前两篇解释了二叉树的有关逻辑概念及前中后序输出递归代码的实现,这篇将讲述二叉树层次遍历输出如何实现以及二叉树前序遍历输入的两种情况。
  • 二叉树层次遍历算法——C/C++

    万次阅读 多人点赞 2019-06-16 00:32:47
    二叉树层序遍历 1、算法思想 用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。 在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点...此过程不断进行,当队列为空时,二叉树层次遍历结束...
  • C语言实现二叉树层次遍历

    千次阅读 多人点赞 2020-07-27 21:29:07
    进行层次遍历时构建一个辅助队列,先将二叉树根节点入队,然后出队,访问出队结点,若它有左子树,将左子树根节点入队,然后出队,访问出队结点…,右子树也同样如此,循环往复直到队列为空。 2.代码 #include<...
  • 二叉树层次遍历C语言实现)

    万次阅读 多人点赞 2019-05-10 21:53:21
    非递归实现二叉树层次遍历: 想了大半个小时终于写出来了,通过自己思考出来的还是有很大成就感。学数据结构就是通过自己思考和参考而学得更深。 思路:层次遍历就是一层一层遍历,这棵二叉树层次遍历序列...
  • 二叉树层次遍历也称广度优先遍历,是一种按照逐层遍历的二叉树遍历方式。广度优先遍历需要借助辅助队列来存取各个节点。实现方法如下: //层次遍历 void LevelOrder(BiTree T) { LinkQueue Q;//辅助队列 ...
  • 二叉树层次遍历详解(C语言版)

    千次阅读 2021-05-15 18:17:20
    非递归版的层次遍历,简单易懂!!!
  • 主要介绍了C语言排序方法,包含10种排序,数据结构课程设计实例二叉树建立遍历冒泡排序快速排序_二叉排序树_二叉树层次遍历_二叉树非递归遍历_二叉树建立括号匹配直接插入选择代码大学生本科毕业设计期末作业排序...
  • 7-1 二叉树层次遍历 (25 分) 编写程序,要求实现(1)按先序遍历序列建立二叉树的二叉链表;(2)按层次遍历二叉树。 C++: 构成二叉链表的结点类代码如下: typedef struct BiNode { char data; //结点数据域 ...
  • 这是用c语言编写的二叉树层次遍历程序,使用非递归的方法实现。欢迎使用。
  • 数据结构-二叉树层次遍历

    万次阅读 多人点赞 2018-10-23 14:57:49
    首先介绍下二叉树层次遍历即按照顺序对树节点依次访问,如下图: 顺序遍历的结果为:ABCDEFGHIJK 我们可以借助一个队列来实现二叉树层次遍历;思路如下: 先将二叉树根节点入队,然后出队,访问该节点,...
  • 层次遍历二叉树是大家再熟悉不过的二叉树操作了,看到这个算法通常会联想到队列,没错,叨叨Chen设计的层次遍历算法也是用到了队列(先进先出),下面一起进入算法游乐场吧。It's show time!Punchline--------------...
  • 2、层次遍历二叉树。输入二叉树头节点的指针。先将头节点入队,将结点指针交给P,后出队。然后再将P左右孩子入队。循环至全部遍历。 注意递归创建过程: 因为先序创建二叉树是左右递归创建,所以一个结束符是结束了...
  • 二叉树层次遍历

    2022-05-11 21:26:56
    目的:使用C++模板设计并逐步完善二叉树的抽象数据类型(ADT)。 内容:(1)请参照链表的ADT模板,设计二叉树并逐步完善的抽象...(2)基本操作5:在二叉树的二叉链表存储形式建立的基础上,设计二叉树层次遍历算
  • 二叉树层次遍历--C语言

    万次阅读 多人点赞 2018-12-21 17:54:22
    今天写一下二叉树层次遍历层次遍历用到的数据结构是队列。   层次遍历算法中增加了三个int型数据,其中levelcount用于记录现在处理的是树的第几层;curlevel用于记录当前层还有几个节点没有被访问过;next...
  • 层次遍历的原理很简单,总结为一句话就是“从上到下,从左到右”,就是从树根开始逐层访问二叉树的结点,每一层按照从左到右的次序进行访问。 为了方便实现层次遍历,可以引入队列来缓存二叉树上的所有结点,出队列...
  • 二叉树层次遍历

    千次阅读 2021-02-03 20:51:19
    层次遍历即为从上到下,从左到右依次访问二叉树的每个结点。 二、层次遍历实现 1、实现思路 (1)我们定义一个队列,先将根结点入队; (2)当前结点是队头结点,将其出队并访问; (3)若当前结点的左结点不为空将...
  • 二叉树遍历(C语言)

    2022-06-07 20:45:37
    二叉树遍历大全
  • 层次遍历算法: void _PrintTree_f5(BiTree a) { LinkQueue b; b=InItQueue(); EnQueue(&b,a); while(!QueueEmpty(b)) { BiTree d; d=getFront(b); printf("%c\n",d->data); if(d->lchild)...
  • 二叉树的各种遍历方法
  • 故知道该题主要考察二叉树基本的层次遍历方法,需要打印出每层节点的关键字。 二叉树层次遍历实现思路是用一个队列记录每层节点,当记录第一层节点时,弹出第一层节点进行访问,访问的同时需要遍历对应节点的左右...
  • 二叉树层次遍历算法

    千次阅读 2021-10-15 08:03:10
    层次遍历是把树看成从上到下的若干层:根结点在第一层,根结点的孩子在第二层,根结点的孩子的孩子在第三层,然后依次类推,从上到下一层一层来访问,每一层从左到右依次访问,每个结点只访问一次 如何实现?...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,459
精华内容 10,183
关键字:

二叉树的层次遍历c