所谓遍历二叉树，就是遵从某种次序，顺着某一条搜索路径访问二叉树中的各个结点，使得每个结点均被访问一次，而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、中序和后序遍历的规则及其算法实现。本文全部代码示例可从此处获得。
解决二叉树的很多问题的方案都是基于对二叉树的遍历。遍历二叉树的前序，中序，后序三大方法算是计算机科班学生必写代码了。其递归遍历是人人都能信手拈来，可是在手生时写出非递归遍历恐非易事。正因为并非易事，所以网上出现无数的介绍二叉树非递归遍历方法的文章。可是大家需要的真是那些非递归遍历代码和讲述吗？代码早在学数据结构时就看懂了，理解了，可为什么我们一而再再而三地忘记非递归遍历方法，却始终记住了递归遍历方法？ 三种递归遍历对遍历的描述，思路非常简洁，最重要的是三种方法完全统一，大大减轻了我们理解的负担。而我们常接触
很多时候我们需要使用非递归的方式实现二叉树的遍历，非递归枚举相比递归方式的难度要高出一些，效率一般会高一些，并且前中后序枚举的难度呈一个递增的形式，非递归方式的枚举有人停在非递归后序，有人停在非递归中序，有人停在非递归前序(这就有点拉胯了啊兄弟)。
二 叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中， 前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。 一.前序遍历 前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。 1.递归实现 void pre_order(BTre
说到树的四种遍历方式，可能大家第一时间都会想到它的四种遍历方式，并快速说了它的特点。
由于本人的码云太多太乱了，于是决定一个一个的整合到一个springboot项目里面。
维护一个cur指针和栈，cur指针指向当前处理的节点，栈中存将要处理的节点，二者任意为空结束循环。
上一篇文章《精通二叉树的“独门忍术”——线索二叉树（上）》提到了线索二叉树的改良，并给出了改良后的“中序遍历”“前序遍历”线索二叉树的定义。本文就来谈谈改良后的“前序遍历”的线索二叉树的转换与遍历算法。
二 叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树，有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法，就要采用栈去模拟实现。在三种遍历中， 前序和中序遍历的非递归算法都很容易实现，非递归后序遍历实现起来相对来说要难一点。 一.前序遍历 前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。 1.递归实现 void pre_order(BTree
教科书式遍历在数据结构书中有，前中后代码有点差距，前序和中序比较容易理解，后序相对复杂一点，代码风格不统一。
深度优先，前、中、后遍历顺序，就是组合[根左右]，移动根的位置，根左右、左根右、左右根，但是我即使代码会写了，还是搞不明白这个根左右与遍历的关系毛线头在哪里，特别是中序遍历的左根右，
上图是一棵二叉树，前序遍历结果：1 2 4 5 3 6 咦，我想你可能会疑惑什么叫做前序遍历，其实很简单，就是按照 根 -》 左 -》 右 的方式去遍历二叉树。
二叉树的定义： 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要
发现规律没？左右的位置始终不变，前序遍历，根在前面，中序遍历，根在中间，以此类推。
前序遍历的方式，也就是对每一棵子树，按照根节点、左子树、右子树的顺序进行访问，也就是根-左-右的访问顺序。因为每一棵非空子树，又可拆分为根节点、左子树和右子树，所以可以按照根-左-右的方式，递归访问每棵子树。
问题二还是比較好写，一的话可能须要细致想想，可是假如是面试的话。可能我一时也说不出来。
前序遍历顺序为: 根结点->左子树->右子树，所以对于正在访问的根结点，可以直接访问，访问完之后，按照相同的方式访问左子树，再访问右子树，过程如下 :
二叉树的非递归遍历
算法实现： pre、mid：前序遍历、中序遍历的结果结果数组 pl、pr、ml、mr：前序、中序遍历结果数组的左右边界 p：创建当前树的根结点 leftRoot、rightRoot：创建当前树的左子树、右子树的根结点 pos：记录当前树的根在中序遍历中的位置 (根在前序遍历中的位置不用记录，前序遍历结果的第一个就是) num：记录左子树结点的个数 lpl、 lpr、 lml、 lmr：记录前序遍历、中序遍历中左子树的范围 rpl,、rpr,、rml、rmr：记录前序遍历、中序遍历中右子树的范围
首先我们要知道，三种不同遍历方式的过程。看下图很容易理解，并且不容易忘。 前序遍历：根 左 右 中序遍历：左 根 右 后序遍历：左 右 根
前一阵子在学习HashMap的时候，知道了在java8之后的HashMap使用数组+链表+红黑树的结构来实现，看代码的时候百思不得其解。
注意我们这里用的是二分搜索树来演示二叉树的这个遍历，才会有中序遍历的那个排序的特征。
补充知识: 二叉树的前序遍历，又称为先序遍历，是指先访问节点本身，然后按照先左后右的顺序遍历其左右子树。具体步骤如下：
二叉树遍历（Traversing binary tree）是指从根节点触发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被依次访问且仅仅被访问一次。
在介绍二分搜索树之前我们先来看二叉树，二叉树是最基本的树形结构，二叉树由一个根节点和多个子节点组成，包括根节点在内的每个节点最多拥有左右两个子节点，俗称左孩子和右孩子。树和链表一样也是动态的数据结构：
发现大家周末的时候貌似都不在学习状态，周末的文章浏览量和打卡情况照工作日差很多呀，可能是本周日是工作日了，周六得好好放松放松，哈哈，理解理解，但我还不能不更啊，还有同学要看呢。
对它进行非递归的前序遍历，它是这样搞的： 前序遍历是根、左子树、右子树 所以首先从根结点开始，顺着访问左子树：8、3、1 然后现在还有谁没访问？ 🆗，是1的左子树、3的左子树，和8的左子树。 所以下面倒着访问1、3、8的左子树就行了。 所以非递归的前序遍历是这样处理的： 他把一棵二叉树分为两个部分：
二叉树是一类简单而又重要的树形结构，在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构，简单的逻辑，广泛的应用和大量的指针操作，在面试过程屡见不鲜，快被面试官玩坏了。相关的问题在百行代码内就可解决，特别适合手写代码，因此我们要充分做好准备，迎接面试时关于二叉树的相关问题，尤其是手写代码。
广义表表示 ：L = (A (B (C, D), E ( , F) ) ) 可以得出
二叉树要求树的每一个结点（除叶结点）的子结点最多只能有 2 个。在二叉树的基础上，继续对其进行有序限制则变成二叉排序树。
前面,我们在"树的概念"一文中已经介绍过了二叉树的基本概念,二叉树较于线性表(顺序表和链表等),难度有一定提升,主要是要熟练掌握递归,很多有关"二叉树"的操作都需要使用递归算法.
为什么要研究树结构？首先因为树在计算机程序中是非常重要的数据结构之一，并且树结构本身是一种天然的组织结构。在很多情况下将数据使用树结构存储后，会发现出奇的高效。甚至有些问题，必须要使用树结构才能够解决。
如果要写出非递归的遍历算法，无论用哪种遍历方法，根据《再不会“降维打击”你就Out了！》《神力加身！动态编程》《史上最猛之递归屠龙奥义》三篇文章中讲到的知识和技巧，都要借助堆栈来记忆“历史路径”以用于回溯。此方法是经典做法，但同时也有两个显著弊端：
本篇博客参照了兰亭风雨的博客：http://blog.csdn.net/ns_code/article/details/12977901/
深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：
二叉树是我们常见的数据结构之一，在学习二叉树之前我们需要知道什么是树，什么是二叉树，本篇主要讲述了二叉树，以及二叉树的遍历。
题目： Given a binary tree, return the inorder traversal of its nodes’ values.
采用2个栈，这个与前序遍历类似，只不过是在该打印的时候，用一个栈将其存放起来，最后打印。
在实现二分搜索树之前，我们先思考一下，为什么要有树这种数据结构呢？我们通过企业的组织机构、文件存储、数据库索引等这些常见的应用会发现，将数据使用树结构存储后，会出奇的高效，树结构本身是一种天然的组织结构。常见的树结构有：二分搜索树、平衡二叉树（常见的平衡二叉树有AVL和红黑树）、堆、并查集、线段树、Trie等。Trie又叫字典树或前缀树。 树和链表一样，都属于动态数据结构，由于二分搜索树是二叉树的一种，我们先来说说什么是二叉树。二叉树具有唯一的根节点，二叉树每个节点最多有两个孩子节点,二叉树的每个节点最多有一个父亲节点，二叉树具有天然递归结构，每个节点的左子数也是一棵二叉树，每个节点的右子树也是一颗二叉树。二叉树如下图：
前序遍历（DLR），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。
二叉树的后序遍历顺序是左-右-根。我们可以采用一个栈来辅助，不过它和前序遍历以及中序遍历还是有点区别的，我们把后序遍历的结果放到一个 LinkedList 容器中作为返回值，具体步骤如下：
然后就是一直递归下去，在访问到节点的时候，可以进行节点的相关处理，比如说简单的访问节点值
主要是对递归不成体系，没有方法论，每次写递归算法 ，都是靠玄学来写代码，代码能不能编过都靠运气。
在上一篇中，我们了解了树的基本概念以及二叉树的基本特点和代码实现，还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是，由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。因此，我们使用非递归（这里主要是循环，循环方法比递归方法快, 因为循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销）来重新实现一遍各种遍历算法，再对二叉树的另外一种特殊的遍历—层次遍历进行实现，最后再了解一下特殊的二叉树—二叉查找树。
来源：https://segmentfault.com/a/1190000008850005
从图上我们看出二分搜索树每个节点的值大于其左子节的所有节点的值小于其右子节点的所有节点的值
从根节点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问1次 且 只被访问1次
我们在栈与队列：匹配问题都是栈的强项中提到了，「递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中」，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
