如果要写出非递归的遍历算法，无论用哪种遍历方法，根据《再不会“降维打击”你就Out了！》《神力加身！动态编程》《史上最猛之递归屠龙奥义》三篇文章中讲到的知识和技巧，都要借助堆栈来记忆“历史路径”以用于回溯。此方法是经典做法，但同时也有两个显著弊端：
栈是限定仅在表尾进行插入和删除操作的线性表。 队列是只允许在一段进行插入操作、而在另一端进行删除操作的线性表。
所有的结点都只有左子树的二叉树叫左斜树.所有结点都是只有右子树的二叉树叫右斜树.这两者统称为斜树.上图中的树2就是左斜树,树3就是右斜树. 斜树每一层只有一个结点,结点的个数与二叉树的深度相同.
二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。下面，以图1所示的二叉树为例，讲解二叉树的前序遍历、中序遍历、后序遍历。
二叉树细分了两种类型的二叉树，一种叫做“满二叉树”，就是每一层都挂满了节点，没有空位。另一种叫做“完全二叉树”，完全二叉树假设有n层，那么n-1层和满二叉树是一样的，但是第n层最后一个节点前边都挂满了节点。这是它们两个概念的唯一具体区别。表示图如下：
刚接触二叉树的学习的时候，相信很多人可能会被二叉树各种各样的叫法和概念给绕晕了，今天就来科普一下关于二叉树我们需要知道的一些树的种类，以及它的特点。
上一篇文章《精通二叉树的“独门忍术”——线索二叉树（上）》提到了线索二叉树的改良，并给出了改良后的“中序遍历”“前序遍历”线索二叉树的定义。本文就来谈谈改良后的“前序遍历”的线索二叉树的转换与遍历算法。
结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6 树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6 叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I...等节点为叶结点 双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点 孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点 根结点：一棵树中，没有双亲结点的结点；如上图：A 结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推 树的高度或深度：树中结点的最大层次； 如上图：树的高度为4 树的如下概念只需了解，我们只要知道是什么意思即可： 非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G...等节点为分支结点 兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点 堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为堂兄弟结点 结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙 森林：由m（m>=0）棵互不相交的树组成的集合称为森林
二叉查找树，其实就是加了一点限制条件的二叉树，我们限制二叉查找的每一个结点的左子树都小于右子树，按照这个规则进行插入和删除，这样就形成了一棵二叉查找树。起这个名字很显然表示了它的用途，由于数据依据大小规则插入的原因，我们可以较快地查找到所需要的数据。
二叉树是由n(n>=0)个节点组成的数据集合。当 n=0 时，二叉树中没有节点，称为空二叉树。当 n=1 时，二叉树只有根节点一个节点。当 n>1 时，二叉树的每个节点都最多只能有两个子树，递归地构建成一棵完整的二叉树。
树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。一直以来，对于树的掌握都是模棱两可的状态，现在希望通过写一个关于二叉树的专题系列。在学习与总结的同时更加深入的了解掌握二叉树。本系列文章将着重介绍一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树。，通过系列的学习做到心中有“树”。
从名字上不能看出，这种二叉树就是为了实现快速搜索而设计的，同时支持快速插入、删除。
二叉树 定义 二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。 基本术语 度：节点所拥有子节点的个数 叶子节点：度为0的节
众所周知，红黑树是非常经典，也很非常重要的数据结构，自从1972年被发明以来，因为其稳定高效的特性，40多年的时间里，红黑树一直应用在许多系统组件和基础类库中，默默无闻的为我们提供服务，身边有很多同学经常问红黑树是怎么实现的，所以在这里想写一篇文章简单和大家聊聊下红黑树
之前谈到的线性表、栈和队列都是一对一的数据结构，但是现实中也存在很多一对多的数据结构，这篇要写的就是一种一对多的数据结构———树。全文分为如下几部分：
1、在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。
树是 n(n >= 0) 个节点的有限集。当 n = 0 时，称为空树。在任意一棵非空树中:
在计算机科学中,相对的大小要比绝对的数量更重要，计算机只看重相对的输赢。在计算机中，由于经常要做的事情是判断真假、比较大小、排序、挑选最大值这类的操作。在计算机的世界里为这些事情专门设计一种数据结构，称为二叉树。
不知道多久以前的上期介绍了一种比较广泛的树，儿子兄弟表示法的普通树。这种树实际上也是一种二叉树，但是由于它在概念上并不是二叉的，所以决定先来介绍这种树。而如今，儿子兄弟表示法的树已经讲完了，现在来理解更为实用且实际上更为简单的二叉树想必会更加容易了。
假如我们遇到一个猜数字的题，即给定一个序列，猜出该序列中的某个数字。一般该序列是有序的，用户猜出一个数字之后提示该数字是大了还是小了。
二叉树是最简单的树形结构，所有的一般树都可以转换为二叉树，转换后的二叉树也能按一定规则还原为一般树。
森林是由若干棵树组成的，所以可以完全理解为，森林中的每一棵树都是兄弟，可以按照兄弟的处理办法来操作。步骤不如：
在之前的系列中。我们学习了DFS、BFS，也熟悉了平衡二叉树，满二叉树，完全二叉树，BST（二叉搜索树）等概念。在本节中，我们将学习一种二叉树中常用的操作 -- 剪枝。这里额外说一点，就本人而言，对这个操作以及其衍化形式的使用会比较频繁。因为我是做规则引擎的，在规则引擎中，我们会有一个概念叫做决策树，那如果一颗决策树完全生长，就会带来比较大的过拟合问题。因为完全生长的决策树，每个节点只会包含一个样本。所以我们就需要对决策树进行剪枝操作，来提升整个决策模型的泛化能力（ML概念）... 听不懂也没关系，简单点讲，就是我觉得这个很重要，或者每道算法题都很重要。如果你在工作中没有用到，不是说明算法不重要，而可能是你还不够重要。
平衡二叉树 对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。 平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1 一棵好的平衡二叉树的特征： （1）保证有n个结点的树的高度为O(logn) （2）容易维护，
而我们在数据结构中所探讨的与此有相似之处，又与此有莫大的不同。我们数据结构吗，要从树这种结构说起。
很多时候我们需要使用非递归的方式实现二叉树的遍历，非递归枚举相比递归方式的难度要高出一些，效率一般会高一些，并且前中后序枚举的难度呈一个递增的形式，非递归方式的枚举有人停在非递归后序，有人停在非递归中序，有人停在非递归前序(这就有点拉胯了啊兄弟)。
在搞清楚多叉树转换为二叉树之前，我们有必要想清楚，为什么要这样转换？多叉树哪里有缺点需要我们转换为二叉树使用？我们来考虑一个问题：“如果我们将一个多叉树存放在一个数组中，然后删除了整个多叉树。我们能否通过这个仅有的数组恢复原来的多叉树呢？”
本博客代码参考：https://www.cnblogs.com/ysocean/p/8032642.html#_label9
树（一对多的数据结构） 树（Tree）是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树种： （1）有且仅有一个特定的称为根（Root）的结点； （2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。 对于树的定义还需要强调两点： 1.n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。 2.m>0时，子树的个数没有限制，但它们一定是互不相交的。 结点分类： 结点拥有的子
完全二叉树只要确保节点从左往右从上往下节点的顺序和同样深度的满二叉树一样，同时只需要确保除了最后一个节点都是齐全的就可以。例如下图就是一个完全二叉树。
二叉树是一种基本的树数据结构，由以分层方式连接的节点组成。二叉树中的每个节点最多可以有两个子节点：左子节点和右子节点。树中最顶层的节点称为根，而没有子节点的节点称为叶。
给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1
假设有一棵树，最上层的是root节点，而父节点会依赖子节点。如果现在有一些节点已经标记为无效，我们要删除这些无效节点。如果无效节点的依赖的节点还有效，那么不应该删除，如果无效节点和它的子节点都无效，则可以删除。剪掉这些节点的过程，称为剪枝，目的是用来处理二叉树模型中的依赖问题。
昨天的文章讲述了二叉树的先序、中序和后序的遍历方法（递归和非递归）,但是这种遍历方法有什么意义么？今天来讲讲这些算法可以用来做什么，只要稍加更改，我们就可以得到另外一个功能，只需要仅仅几行代码的修改！ 还记得上篇文章二叉树的分类么？今天我们要来说三种树的分类：完全二叉树、平衡二叉树和搜索二叉树！
前面两篇博客介绍了线性表的顺序存储与链式存储以及对应的操作，并且还聊了栈与队列的相关内容。本篇博客我们就继续聊数据结构的相关东西，并且所涉及的相关Demo依然使用面向对象语言Swift来表示。本篇博客我们就来介绍树结构的一种：二叉树。在之前的博客中我们简单的聊了一点树的东西，树结构的特点是除头节点以外的节点只有一个前驱，但是可以有一个或者多个后继。而二叉树的特点是除头结点外的其他节点只有一个前驱，节点的后继不能超过2个。 本篇博客，我们只对二叉树进行讨论。在本篇博客中，我们对二叉树进行创建，然后进行各种遍历
如何巧妙地用二叉树遍历算法来升级和增强监控软件的稳定性呢？二叉树遍历算法有前序遍历、中序遍历还有后序遍历，就像一把利器，能在不同场景下大展身手，让监控软件的性能和稳定性都提上一个档次。
在数据结构与算法中，树是一个比较大的家族，家族中有很多厉害的成员，这些成员有二叉树和多叉树(例如B+树等)，而二叉树的大家族中，二叉搜索树(又称二叉排序树)是最最基础的，在这基础上才能继续拓展学习AVL(二叉平衡树)、红黑树等知识。
二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。简言之，二叉树是数据结构中非常重要的东西，在很多OJ试题和笔试题中，都会出现它的影子；至于高阶数据结构中的各种树，比如二叉搜索树、AVL树、红黑树、B树等都是基于二叉树的高阶树。总之，现在把普通二叉树学好了，对以后的学习是十分有帮助的。
完全二叉树就是像下图一样的二叉树，所有叶结点的深度相同，并且所有内部结点都有两个子结点
所谓遍历二叉树，就是遵从某种次序，顺着某一条搜索路径访问二叉树中的各个结点，使得每个结点均被访问一次，而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、中序和后序遍历的规则及其算法实现。本文全部代码示例可从此处获得。
第六章 递归 1.小结 1.1 一个递归的方法每次用不同的参数值反复调用自身 1.2 某种参数值使递归的方法,而不再调用自身.这成为基值情况,也称为是递归算法的出口,递归算法必须要有出口,不然就会造成死循环 1.3 三角数字就是它本身以及所有比它小的数字的和.例如4的三角数组是10,因为4+3+2+1 =10 1.4 三角数字和阶乘都可以通过递归来实现 1.5 任何可以用递归完成的操作都可以用一个栈来实现 1.6 递归的方法可能效率很低,如果是这样的话,有时可以用一个简单的循环或者是一个基于栈的方法来替代
二叉树的遍历 → 不用递归，还能遍历吗中讲到了二叉树的深度遍历的实现方式：递归、栈+迭代
树这种数据结构模拟了自然界中树的概念，自然界中的树有根、叶子、枝干，数据结构中的树也是如此，只不过是倒过来的：
平衡二叉树:它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，且为了方便后面的介绍，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。 基于二叉树的链式结构，于是可以先malloc动态开辟出二叉树的每个节点并初始化，然后通过节点中的指针struct BinaryTreeNode* left（指向左树）和struct BinaryTreeNode* right（指向右树），将各个节点连接起来，最后大致模拟出了一棵二叉树，代码如下：
从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM
