【二叉树】层序遍历

时间:2024-02-11 22:19:00 标签:  遍历  

 目录

层序遍历概念&结构 

层序遍历的实现

整体思路

代码实现

图示理解

BT升级

整体思路

代码实现

图示理解​

应用

题目


前序&中序&后序遍历:深度优先遍历dfs

层序遍历:广度优先遍历bfs

层序遍历概念&结构 

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

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

层序遍历的实现

层序遍历用队列实现,需要把队列的代码拷贝到多文件项目里面:单链表实现【队列】_单链表队列出队-CSDN博客

整体思路

  • 把根节点放入队列
  • 保存根节点在tmp,打印根节点(遍历),然后把根节点的左右孩子入队列
  • 根节点出队列
  • 循环上诉过程(父亲出的时候就带入父亲的左右孩子)
  • 若为NULL则不入队列
  • 达到一层一层遍历(层序遍历)

    注意

  • tmp保存的是树节点的地址

  • 销毁的是队列的头节点(里面也是树节点的地址)

  • 不会销毁树的节点

代码实现

测试代码在前面博文有:链式二叉树(1)-CSDN博客

//层序遍历
void LevelOrder(BTNode* root)
{Queue pq;QueueInit(&pq);if(root)QueuePush(&pq, root);while (!QueueEmpty(&pq)){BTNode* tmp = QueueFront(&pq);//队列头的元素QueuePop(&pq);//出元素到队头printf("%d ", tmp->data);if(tmp->left)QueuePush(&pq, tmp->left);if(tmp->right)QueuePush(&pq, tmp->right);}QueueDestroy(&pq);
}int main()
{BTNode* root = CreatBinaryTree();LevelOrder(root);BinaryTreeDestory(root);root = NULL;return 0;
}

图示理解

BT升级

若我们想要一层一层打印,怎样去一层一层打印? 

整体思路

  • 设置一个变量LeveSize记录每层的个数
  • 每一层的数据个数,控制一层一层数据出队列
  • 换行打印

代码实现

//BT升级换行打印
//层序遍历
void LevelOrder(BTNode* root)
{Queue pq;QueueInit(&pq);if (root)QueuePush(&pq, root);int levesize = 1;while (!QueueEmpty(&pq)){while (levesize--){BTNode* tmp = QueueFront(&pq);//队列头的元素QueuePop(&pq);//出元素到队头printf("%d ", tmp->data);if (tmp->left)QueuePush(&pq, tmp->left);if (tmp->right)QueuePush(&pq, tmp->right);}printf("\n");levesize = QueueSize(&pq);//队列里面的元素个数}QueueDestroy(&pq);
}int main()
{BTNode* root = CreatBinaryTree();LevelOrder(root);BinaryTreeDestory(root);root = NULL;return 0;
}

图示理解

应用

大家可以思考扫雷用递归去实现?QQ加好友的好友?

  • 展开形式:广度优先遍历
  • 展开形式:深度优先遍历
  • 八度递归
  • 层序遍历:加好友的好友(搜索算法)>>>>后面的算法篇章我们会介绍

题目

练习:请写出下面的前序/中序/后序/层序遍历

1.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为( )
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA
2.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为()
A E
B F
C G
D H
3.设一课二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde
4.某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出(同一层从左到右)的序列为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF

答案:AADA

🙂感谢大家的阅读,若有错误和不足,欢迎指正。大家新年快乐!!

来源:分享自作者个人站点/博客

智能推荐

 目录 层序遍历概念&结构  层序遍历的实现

标签:遍历  

二叉树准备: public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(in

标签:遍历  

目录 前言: 层序遍历: 解析:

标签:遍历  

这是树的第5篇算法,力扣链接。 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1:

标签:遍历  

这是树的第7篇算法,力扣链接。 给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历) 示例 1:

标签:遍历  

题目给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。示例 1:输入:root = [3,9,20,null,null,15,7]输出:[[3],[9,20],[15,7]]</pre>示例 2:输入:root = [1]输出:[[1]]

标签:遍历  二叉树  LeetCode  

力扣107 二叉树的层序遍历题目:给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)示例 1:输入:root = [3,9,20,n

标签:遍历  二叉树  力扣  

给定一个 N 叉树&#xff0c;返回其节点值的层序遍历。&#xff08;即从左到右&#xff0c;逐层遍历&#xff09;。 树的序列化输入是用层序遍历&#xff0c;每组子节点都由 null 值分隔&#xff08;参见示例&#xff09;。 示例 1&#xff1a;

标签:遍历  

这是树的第7篇算法&#xff0c;力扣链接。 给你二叉树的根节点 root &#xff0c;返回其节点值的 锯齿形层序遍历 。&#xff08;即先从左往右&#xff0c;再从右往左进行下一层遍历&#xff0c;以此类推&#xff0c;层与层之间交替进行&#xff09;。 示例 1&#xff1a;

标签:遍历  

给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。

标签:遍历  

坚持刷题&#xff0c;老年痴呆追不上我&#xff0c;今天刷&#xff1a;二叉树的层序遍历 题目 102二叉树的层序遍历

标签:遍历  

1.题目给你二叉树的根节点 root ,返回它节点值的 前序,中序,后续遍历。spark打酱油输入:root = [1,null,2,3]输出:[1,2,3]示例 2:

标签:遍历  二叉树  

二叉树前言二叉树的遍历主要有深度优先遍历和广度优先遍历,深度优先遍历是优先访问一个子树上的所有节点,访问的属性是竖向的,而广度优先遍历则是优先访问同一层的所有节点,访问属性是横向的。深度优先遍历深度优先遍历主要有三种顺序:前序遍历 —— 根左右中序遍历 —— 左根右后序遍历 —— 左右根这三种遍历顺序用递归可以很容易实现,主要讲的是非递归的实现方法。而要使用迭代的方法来遍历

标签:遍历  二叉树  

本文是力扣LeeCode-102、二又树的层序遍历 学习与理解过程&#xff0c;本文仅做学习之用&#xff0c;对本题感兴趣的小伙伴可以出门左拐LeeCode。 给你二叉树的根节点 root &#xff0c;返回其节点值的

标签:遍历  

文章目录 题目描述我的解法思路结果分析 官方题解思路分析

标签:遍历  

二叉树的层序遍历 Java 102. 二叉树的层序遍历错误① 队列的声明错误② &#96;List<List<Integer>>&#96;的声明

标签:二叉树  

题目&#xff1a; 代码(首刷看解析 2024年1月24日&#xff09;&#xff1a; class Solution {public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> r

标签:遍历  

二叉树是逻辑结构,二叉链表是二叉树的物理实现,是它的一种存储结构。两者之间的关系属于概念和实现,抽象和具体的关系。&nbsp;前序遍历:根节点->左子树->右子树中序遍历:左子树->根节点->右子树后序遍历:左子树->右子树->根节点深度优先遍历:

标签:遍历  二叉树  php  

一、深度优先遍历二叉树1.前序遍历(先添加根节点的值,然后添加左右节点的值)1.1.递归遍历1.1.1.思路递归遍历二叉树相对简单:考虑特殊情况:当根节点为空的时候,直接返回null如果根不为空,则将根的值添加进入List判断左右节点是否为空,非空则开始递归递归的方法:用于判断是否还有左右节点,添加节点的值,有节点则继续递归,没有则返回上一个节点

标签:遍历  二叉树  

1.二叉树的遍历二叉树主要有两种遍历方式:深度优先遍历:先往深走,遇到叶子节点再往回走。前序遍历(递归法,迭代法) 中左右中序遍历(递归法,迭代法)&nbsp;左中右后序遍历(递归法,迭代法)&nbsp;左右中

标签:遍历  二叉树  

猜你喜欢

二叉树的遍历一、二叉树的遍历算法可以将二叉树的遍历分为:先序遍历 (根、左、右),中序遍历 (左、根、右),后序遍历 (左、右、根)先序遍历动画 (根、左、右)中序遍历动画 (左、根、右)后序遍历动画 (左、右、根)

标签:遍历  二叉树  

       &#x1f4dd;个人主页&#xff1a;五敷有你        &#x1f525;系列专栏&#xff1a;算法分析与设计 ⛺️稳中求进&#xff0c;晒太阳

标签:遍历  

题目&#xff1a; 代码&#xff08;首刷自解 2024年1月24日&#xff09;&#xff1a; class Solution {public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<

标签:遍历  

102.二叉树的层序遍历 给你二叉树的根节点 root &#xff0c;返回其节点值的 层序遍历 。 &#xff08;即逐层地&#xff0c;从左到右访问所有节点&#xff09;。

标签:遍历  

题外&#xff1a;另外三种遍历可以看这&#xff1a; 层序遍历&#xff1a; Leetcode:二分搜索树层次遍历-CSDN博客 先序遍历&#xff1a; 二叉树的先序&#xff0c;中序&#xff0c;后序遍历-CSDN博客 后序遍历&#xff1a; 二叉树的先序&#xff0c;中序&#xff0c;后序遍历-CSDN博客 题目&#xff1a; 给定一个二叉树的根节点 root &#xff0c;返回 它的 中序 遍历 。 示

标签:遍历  

145. 二叉树的后序遍历 给你一棵二叉树的根节点 root &#xff0c;返回其节点值的 后序遍历 。 示例 1&#xff1a; 输入&#xff1a;

标签:遍历  

前言我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。LeetCode 算法到目前我们已经更新到 144 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。难度水平:简

标签:遍历  二叉树  LeetCode  

大家新年快乐&#xff0c;long年大吉 今天的题很简单&#xff0c;前序用栈就行。 电脑没拿&#xff0c;用我妈的pad艰难敲代码&#xff0c;敲字 知识点随便写点吧&#xff0c;这里基础点挺多&#xff0c;以后补充下 栈&#xff1a;先进后出&#xff0c;数据结构用stack&#xff0c;或者可以用ArrayList模拟 队列&#xff1a;先进先出&#xff0c;数据结构用queue&#xff0c;可以用LinkedList模拟 代码如下

标签:遍历  

题目 144. 二叉树的前序遍历 分析 这道题目是比较基础的题目&#xff0c;我们首先要知道二叉树的前序遍历是什么&#xff1f; 就是【根 左 右】 的顺序&#x

标签:遍历  

二叉树的遍历 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台备战技术面试&#xff1f;力扣提供海量技术面试资源&#xff0c;帮助你高效提升编程技能&#xff0c;轻松拿下世界 IT 名企 Dream Offer。

标签:遍历  

102. 二叉树的层序遍历 1、题目2、题目分析3、复杂度最优解代码示例4、适用场景 1、题目 给你二叉树的根节点 root

标签:遍历  

 &#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm&#61;1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm&#61;1001.2014.3001.5482

标签:二叉树  

2023每日刷题&#xff08;九十七&#xff09; Leetcode—145. 二叉树的后序遍历

标签:遍历  

2023每日刷题&#xff08;九十六&#xff09; Leetcode—144. 二叉树的前序遍历

标签:遍历  

讲了这么多数据结构相关的知识(可以看我的数据结构文章专栏): 抓紧刷题巩固一下了 目录 1.单值二叉树 题目描述 思路1

标签:二叉树  

103.二叉树的锯齿形层序遍历 给你二叉树的根节点 root &#xff0c;返回其节点值的 锯齿形层序遍历 。&#xff08;即先从左往右&#xff0c;再从右往左进行下一层遍历&#xff0c;以此类

标签:遍历  

Problem: 199. 二叉树的右视图

标签:递归  

题目&#xff1a; 代码(首刷自解 2024年1月24日&#xff09;&#xff1a; /*// Definition for a Node.class Node {public:int val;vector<Node*> children;Node() {}Node(int _val) {val &#6

标签:遍历  

力扣105 根据先序遍历以及中序遍历构建二叉树题目:给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例 1:

标签:遍历  二叉树  力扣  

关于最近最近在看算法相关的,接下来想记录一下自己学习的、个人认为比较值得记录的算法。这篇博客主要是用自己的理解复述了根据中序、前序遍历重建二叉树这个博客的内容,大家可以主要看这个博客,我写得不如远矣。根据前序和中序遍历重建二叉树我们知道前序、中序、后序遍历二叉树有很多方法,比如递归进行遍历,使用栈/队列进行深度/广度优先遍历,更有甚者使用Morris方法进行额外空间复杂度为O(1)的遍历,但从遍历后的序列重建二叉树就比较麻烦。这里描述一下从前序遍历序列和中序遍历序列重构二叉树的方法,要求二叉树没有重复的元素。

标签:遍历  二叉树  

&nbsp;二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。1、二叉树的遍历方法对于二叉树,有深度遍历和广度遍历,深度遍历有前序、中序以及后序三种遍历方法,广度遍历即我们平常所说的层次遍历。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁,而对于广度遍历来说,需要其他数据结构的支撑,比如堆。所以,对于一段代码来说,可读性有时候要比代码本身的效率要重要的多。所谓前序,中序,后续遍历命名的由来是我们访问二叉树,根节点的顺序。前序遍历就是优先访问根节点,中序遍历是第二个访问根节点,后续遍历就是访问完左右节点之后,最后访问根节点。

标签:递归  遍历  二叉树  

给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1:

标签:遍历  

遍历 遍历即:遍历每个元素。 for遍历每个元素只会遍历一次。 而二叉树遍历每个元素则会遍历三次。 中序遍历-节点的中序

标签:遍历  

1.叉树链式结构的实现 1.1前置说明 在学习二叉树的基本操作前&#xff0c;需先要创建一棵二叉树&#xff0c;然后才能学习其相关的基本操作。 为了方便调

标签:遍历  

相关问题

相关文章

热门文章

推荐文章

相关标签