本期的 DFS 与 BFS 搜索算法，我将围绕二叉树来讲解，所以在了解什么是 BFS 与 DFS 之前，我们先来回顾一下二叉树 的基本概念
不管是递归（系统栈）实现，还是 栈 + 迭代 实现，深度遍历的额外空间复杂度都是：O(n)
二叉树是使用较多的一种树形结构，如比较经典的二叉排序树，Huffman编码等，都使用到了二叉树的结构，同时，在机器学习算法中，基于树的学习算法中也大量使用到二叉树的结构，因此，我们有必要对二叉树的结构
二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
推荐视频——关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
树的先根遍历简单而言就与，二叉树的前序遍历相似，都是“根左右”，只不过在左右之分上面，不是简单的只是左右而已，而是同一层上面的节点，从左边的节点遍历结束之后才轮到右边的下一个节点（同一层不一定只是左右两个节点）；
二叉树是由n个结点的有限集合，该集合或者为空集，或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
🎬 鸽芷咕：个人主页 🔥 个人专栏: 《linux深造日志》 《高效算法》
首先我们的目标是将节点的左右值进行交换，说到这里小伙伴可以自行想想可以使用几种方法进行交换，其效率如何，为什么？ok,回到正题，这道题同样是交换，我们交换两个节点的值需要通过根节点的指针拿到左右节点的地址，交换完了以后我们还需要继续按照同样的方式进行交换，那么怎么保存这些节点，小伙伴们可以使用栈也可以使用队列，只不过顺序不同而已，这里咋们使用栈。
树的分类有很多种，但基本都是 二叉树 的衍生，今天来学习下二叉树。 什么是二叉树 Binary Tree 先来个定义： 二叉树是有限个节点的集合，这个集合可以是空集，也可以是一个根节点和至多两个子二
栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。
二叉树的遍历和队列的相关概念前面已经介绍，忘记了的小伙伴复习后再看效果一定翻倍哟！
看官，不要生气，我没有骂你也没有鄙视你的意思，今天就是想单纯的给大伙分享一下树的相关知识，但是我还是想说作为一名程序员，自己心里有没有点树？你会没点数吗？言归正传，树是我们常用的数据结构之一，树的种类很多有二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树等等，我们今天就来聊聊二叉树相关的树。
二叉树 6.2.1 二叉树的概念 二叉树（Binary Tree）是结点的有限集合，这个集合或者为空，或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树,且子树有左右之分,次序不能颠倒。 二叉树是一种重要的树型结构,但二叉树不是树的特例。二叉树的5种形态分别为:空二叉树、只有根结点的二叉树、根结点和左子树、根结点和右子树、根结点和左右子树。 二叉树与树的区别:二叉树中每个结点的孩子至多不超过两个,而树对结点的孩子数无限制;另外,二叉树中结点的子树有左右之
1．先序遍历的递归算法定义：(也叫做先根遍历、前序遍历 ) . 若二叉树非空，则依次执行如下操作：
对高度为h的满二叉树的元素，从第一层到最后一层，在每一次中从左至右，顺序编号，从1到2^h-1.假设从满二叉树中删除k个其编号为2^h-i元素，1<=i<=k<2^h，所得到的二叉树被称为完全二叉树。
深度优先，前、中、后遍历顺序，就是组合[根左右]，移动根的位置，根左右、左根右、左右根，但是我即使代码会写了，还是搞不明白这个根左右与遍历的关系毛线头在哪里，特别是中序遍历的左根右，
数据结构中的树是什么样子呢？他就像是一个倒着生长的树，对照着两幅图看，是不是很相似。其中圆圈的位置就是数据存放的地方。
二叉树的遍历可以通过递归来实现。递归终止的条件是当前节点为空节点，然后返回。前中后序遍历的递归函数不同之处只是输出当前节点的那条语句不同。
-即使树中某个节点中只有一个子树的花，也要区分它是左子树还是右子树 二叉树一般有五种形态 1.空二叉树 2.只有一个根节点 3.根结点只有左子树 4.根节点只有右子树
3 月 12 号，是全国的重大节日：植树节。记得小时候就跟随老师一起植过树。现在参加工作了，虽然没有植过树，但是学到过很多树的结构，比如二叉树、B+ 树，红黑树。每次面试必问，恰逢植树节，本来是想讲解 B 树，但发现必须要理解了二叉树之后才能更好地讲解 B 树，所以先给大家讲下二叉树是什么，后面文章再更新 B 树。
首先我们一起来温习下二叉树的三种遍历方式：前序遍历、中序遍历、后续遍历。如果读者不太了解这三种遍历方式，建议找点博客看看二叉树的三种遍历，本文主要是借助二叉树的遍历结果来还原二叉树，所以本文默认读者是了解二叉树的遍历的。
前序遍历（中左右）：5 4 1 2 6 7 8 中序遍历（左中右）：1 4 2 5 7 6 8 后序遍历（左右中）：1 2 4 7 8 6 5
树（Tree）是n（n≥0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：①有且仅有一个特定的称为根（Root）的结点；②当n>1时，其余结点可分为m（m>0）个互不相交的有限集T 1 {T}_{1}T 1 、T 2 {T}_{2}T 2 、… 、T m {T}_{m}T m ，其中每一个集合本身又是一棵树，并且称为根的子树（Sub Tree）。
通过【学点数据结构和算法】系列的1-4，我们已经学习了数据结构中常用的线性结构。从物理存储方面来说，它们又分为顺序存储和链式存储结构。他们各自有自己的优缺点，顺序存储结构读快写慢，链式存储结构写快读慢。但是这些数据元素之间的关系都为一对一的关系，而我们生活中关系不止是一对一，有可能是一对多，多对多的情况… 本篇博客，我们就要学习一种新的数据结构——树，它将为我们展示一个全新的“世界”。
3 月 12 号，是全国的重大节日：植树节，记得小时候就跟随老师一起植过树。现在参加工作了，虽然没有植过树，但是学到过很多树的结构，比如二叉树、B+ 树，红黑树。每次面试必问，恰逢植树节，这里给大家做个二叉树的总结，也方便自己复习。
最近也是在准备笔试，由于没有系统的学过数据结构，所以每次在考到二叉树的遍历的时候都是直接跪，次数多了也就怒了，前些天也是准备论文没时间整这些，现在提交了，算是稍微轻松点了，所以花了半天的时间来学了下二叉树。现在记下来，以便后序查阅。
树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。一直以来，对于树的掌握都是模棱两可的状态，现在希望通过写一个关于二叉树的专题系列。在学习与总结的同时更加深入的了解掌握二叉树。本系列文章将着重介绍一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树。，通过系列的学习做到心中有“树”。
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。下面，以图1所示的二叉树为例，讲解二叉树的前序遍历、中序遍历、后序遍历。
二叉树的遍历是我们学习二叉树首先要了解的东西，我们都知道二叉树其实就是一串数组，那我们是如何访问他们的呢？这里就牵扯到了遍历顺序的问题。
性质3：在任意一棵二叉树中,如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
如图就是一个树结构，最上边的叫「根节点」，最下边的叫「叶子节点」。根节点有多个子节点，叶子节点没有子节点。二叉树就是，每个节点最多有两个子节点的树。
在文档管理软件里，二叉树的遍历算法如同在细心编排舞台，将文档数据有序地呈现。又像是潺潺流水，将一个个节点串联而成，每个节点犹如明珠，蕴含着左右两个子节点的可能。文档管理软件借助二叉树，将文档索引、文件夹构造等事宜娴熟布局，让用户宛如游览花园，轻松快捷地翻阅、寻觅和获取各类文档。
目录 一、树 二、二叉树 三、树、森林与二叉树的转换 一、树 树形结构 是数据元素(结点)之间有分支，并且具有层次关系的结构，可用于表示数据元素之间存在的一对多关系。 树(Tree) 是由n(n≥0)个结点构成的有限集合，当n=0时称为空树。若树非空，则具有以下两个性质： (1)有且仅有一个特定的结点，称为根(Root)。 (2)其余的结点可分为m个互不相交的集合T1，T2，…，Tm，其中每一个集合都是一棵树，并且称为根的子树( Subtree)。 如下图
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
我们知道普通的线性数据结构如链表，数组等，遍历方式单一，都是从头到尾遍历就行，但树这种数据结构却不一样，我们从一个节点出发，下一个节点却有可能遇到多个分支路径，所以为了遍历树的全部节点，我们需要借助一个临时容器，通常是栈这种数据结构，来存储当遇到多个分叉路径时的，存暂时没走的其他路径，等走过的路径遍历完之后，再继续返回到原来没走的路径进行遍历，这一点不论在递归中的遍历还是迭代中的遍历中其实都是一样的，只不过递归方法的栈是隐式的，而我们自己迭代遍历的栈需要显式的声明。
二叉树结点的各种遍历序列，其实质是对一个非线性结构进行线性化操作，使在这个访问序列中每一个结点（除第一个和最后一个）都有一个直接前驱和直接后继。
定义：二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
树和图是数据结构中比较麻烦的东西，里面涉及的概念比较多，也最有用， 就比如一般树广泛应用于人工智能的博弈上，而基于图的广度优先和深度优先搜索也广泛应用于人工智能寻路上面
说道二叉树，大家对于二叉树其实都很熟悉了，本文呢我也不想教科书式的把二叉树的基础内容在啰嗦一遍，所以一下我讲的都是一些比较重点的内容。
前面两篇博客介绍了线性表的顺序存储与链式存储以及对应的操作，并且还聊了栈与队列的相关内容。本篇博客我们就继续聊数据结构的相关东西，并且所涉及的相关Demo依然使用面向对象语言Swift来表示。本篇博客我们就来介绍树结构的一种：二叉树。在之前的博客中我们简单的聊了一点树的东西，树结构的特点是除头节点以外的节点只有一个前驱，但是可以有一个或者多个后继。而二叉树的特点是除头结点外的其他节点只有一个前驱，节点的后继不能超过2个。 本篇博客，我们只对二叉树进行讨论。在本篇博客中，我们对二叉树进行创建，然后进行各种遍历
所有的结点都只有左子树的二叉树叫左斜树.所有结点都是只有右子树的二叉树叫右斜树.这两者统称为斜树.上图中的树2就是左斜树,树3就是右斜树. 斜树每一层只有一个结点,结点的个数与二叉树的深度相同.
二叉树是一种特殊的数据结构，有一个根节点，根节点下面有一左一右两个子节点，每个子节点又有各自的子节点，层层深入成树状。
二叉树的遍历可以说是二叉树最重要的一个内容，如果想对树的算法有一定的认识，那么二叉树的遍历是一定要熟练使用的，本文将主要介绍一下二叉树的遍历。
上篇文章我们讲了许多理论方面的知识，虽说很枯燥，但那些都是我们今天学习的前提，一会看代码的时候你就会发现这些理论知识是多么地重要了。首先，我们还是要说明一下，我们学习的主要内容是二叉树，因为二叉树是最典型的一种树的应用，不管是考试还是面试，它都是必知必学的内容。
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
以这个树结构为例子。 孩子：a的孩子是bcd。b的孩子是ef。d的孩子是gh.c没有孩子.
俗话说：学如逆水行舟,不进则退;心似平原走马,易放难收。这句话对程序员而言，体会更深。这行已经越来越卷了，时刻准备着😃。 二叉树，在面试中，已是必备的开胃菜。而在二叉树相关的面试题目中，遍历更是常考题目。本文将从二叉树的遍历角度入手，从递归和非递归角度来分析和讲解二叉树的遍历。 遍历 二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中的所有节点，使每个节点被且仅被访问一次。 二叉树的遍历，有先序遍历、中序遍历以及后续遍历三种。 图一 上面三种遍历方式中的先序、中序以及后序三种方式，是父节点相对
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频
