首页 > 其他分享 >二叉树的层次遍历

二叉树的层次遍历

时间:2023-08-14 10:36:19浏览次数:36  
标签:遍历 TreeNode 层次 Queue 二叉树 front return data rear

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 100

typedef struct TreeNode{
	int data;
	struct TreeNode *lchild,*rchild;
}TreeNode,*Tree;

typedef struct{
	TreeNode* data[MaxSize];
	int front;
	int rear;
}Queue;

void InitQueue(Queue &Q)
{
	Q.front=Q.rear=0;
}

bool isEmpty(Queue Q)
{
	if(Q.front==Q.rear)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool isFull(Queue Q)
{
	if((Q.rear+1)%MaxSize==Q.front)
	{
		return true;
	}
	else
	{
		return false;
	}
}

bool EnQueue(Queue &Q,TreeNode* p)
{
	if(isFull(Q))
	{
		return false;
	}
	Q.data[Q.rear]=p;
	Q.rear=(Q.rear+1)%MaxSize;
	return true;
}

bool DeQueue(Queue &Q,TreeNode* &p)
{
	if(isEmpty(Q))
	{
		return false;
	} 
	p=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	return true;
}

//先序创建二叉树
void CreateTree(Tree &T)
{
	int x;
	scanf("%d",&x);
	if(x==-1)
	{
		T=NULL;
		return;
	}
	else
	{
		T=(Tree)malloc(sizeof(TreeNode));
		T->data=x;
		printf("输入%d的左结点:",x);
		CreateTree(T->lchild);
		printf("输入%d的右结点:",x);
		CreateTree(T->rchild);
	}
}

//层次遍历(利用队列) 
void LevelOrder(Tree T)
{
	Queue Q;
	InitQueue(Q);
	TreeNode *p=T;
	EnQueue(Q,p);
	while(!isEmpty(Q))
	{
		DeQueue(Q,p);
		printf("%d  ",p->data);
		if(p->lchild!=NULL)
		{
			EnQueue(Q,p->lchild);
		}
		if(p->rchild!=NULL)
		{
			EnQueue(Q,p->rchild);
		}
	}	
} 

int main()
{
	Tree T;
	CreateTree(T);
	LevelOrder(T); 
	return 0;	
} 

 

标签:遍历,TreeNode,层次,Queue,二叉树,front,return,data,rear
From: https://www.cnblogs.com/simpleset/p/17627955.html

相关文章

  • 二叉树的非递归遍历
    //非递归操作#include<stdio.h>#include<stdlib.h>#defineMaxSize200typedefstructTreeNode{intdata;structTreeNode*lchild,*rchild;}TreeNode,*Tree;typedefstruct{Treedata[MaxSize];inttop;}Stack;voidInitStack(S......
  • 二叉树的递归遍历
    #include<stdio.h>#include<stdlib.h>typedefstructTNode{intdata;structTNode*lchild,*rchild;}TreeNode,*Tree;/*在这段代码中,递归函数`CreateTree`在执行`return`语句后,会立即返回到调用它的上一层递归调用。但是,整个递归过程并没有结束,仍然会......
  • P9534 [YsOI2023] 广度优先遍历
    好题。首先考虑到对于任意的边的输入顺序,分层图是不会变的,即所有点到根的最短距离不变。那么分为两种边,分别为不同层的边相连,相同层的边相连。显然第二种边是无用的,我们将其放到最后输出即可。由于下层的决策会影响上层的决策而且不同层之间的边的顺序不会影响答案,所以我们按......
  • import.meta.globEager('./src/components/**/*.vue'); 遍历文件
    main.jsconstimportAll=(modules)=>{Object.keys(modules).forEach((key)=>{constcomponent=key.replace('/src/','@/').replace('.vue','');constcomponentName=key.split('/').slice......
  • 二叉树的层序遍历
    intfindBottomLeftValue(TreeNode*root){queue<TreeNode*>qu;if(root!=nullptr)qu.push(root);intsize=0;intresult=0;while(!qu.empty()){TreeNode*temp;size=qu.size();......
  • [代码随想录]Day16-二叉树part05
    题目:513.找树左下角的值思路:层序遍历是最好的选择了,先放右节点,再放左节点最后一个元素就是最左侧的节点。说白了层序遍历就是广度优先搜索BFS。代码:funcfindBottomLeftValue(root*TreeNode)int{node:=rootq:=[]*TreeNode{root}forlen(q)>0{......
  • p5两链表相交问题和二叉树
    (本文大多从杀戒之声处来,就想着自己方便看)两链表相交问题所谓相交,是指两链表有某一内存地址相同,则为相交,判断有环无环,哈希表(set),第一次相同(单向链表)快慢指针,快走2,慢走1,快慢指针第一次相遇后,将快指针返回头节点,慢指针不动,快改为走1,看快慢节点是否能相遇,有环则一定会在入环节......
  • [代码随想录]Day15-二叉树part04
    题目:110.平衡二叉树思路:就是后序,如果左右差的超过了1,那么就直接返回-1,如果最后收到了-1那一定是false。代码:/***Definitionforabinarytreenode.*typeTreeNodestruct{*Valint*Left*TreeNode*Right*TreeNode*}*/funcisBalanced(......
  • 代码随想录算法训练营第十六天| 104.二叉树的最大深度 111.二叉树的最小深度 222.
      104.二叉树的最大深度 (优先掌握递归)    卡哥建议:什么是深度,什么是高度,如何求深度,如何求高度,这里有关系到二叉树的遍历方式。大家要先看视频讲解,就知道以上我说的内容了,很多录友刷过这道题,但理解的还不够。   题目链接/文章讲解/视频讲解:https://programmerc......
  • 代码随想录算法训练营第十五天| 层序遍历 10 ,226.翻转二叉树 101.对称二叉树 2
     层序遍历   卡哥建议:看完本篇可以一口气刷十道题,试一试, 层序遍历并不难,大家可以很快刷了十道题。  题目链接/文章讲解/视频讲解:https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html  做题思......