解决二叉树的很多问题的方案都是基于对二叉树的遍历。遍历二叉树的前序，中序，后序三大方法算是计算机科班学生必写代码了。其递归遍历是人人都能信手拈来，可是在手生时写出非递归遍历恐非易事。正因为并非易事，所以网上出现无数的介绍二叉树非递归遍历方法的文章。可是大家需要的真是那些非递归遍历代码和讲述吗？代码早在学数据结构时就看懂了，理解了，可为什么我们一而再再而三地忘记非递归遍历方法，却始终记住了递归遍历方法？ 三种递归遍历对遍历的描述，思路非常简洁，最重要的是三种方法完全统一，大大减轻了我们理解的负担。而我们常接触
先序非递归遍历比较简单，感觉与DFS类似，根据先序遍历的规则根左右，先将根节点压入栈，然后遍历左子树，再遍历左子树的左子树，一头走到NULL，把每次遍历的左子树的根节点依次入栈并把当前结点数据打印出来。最后为NULL，开始回溯，返回到前一结点（也就是当前结点的根节点），开始遍历右子树。依次类推。
教科书式遍历在数据结构书中有，前中后代码有点差距，前序和中序比较容易理解，后序相对复杂一点，代码风格不统一。
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
所谓遍历二叉树，就是遵从某种次序，顺着某一条搜索路径访问二叉树中的各个结点，使得每个结点均被访问一次，而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、中序和后序遍历的规则及其算法实现。本文全部代码示例可从此处获得。
小编带大家学习数据结构中的二叉树，我们这里的实现主要是用 C 语言去实现的，当然也有 C++的语法，用基础的语言有助于我们更好理解数据结构。
前序遍历的非递归算法 #include<iostream> using namespace std; #include<stack> struct node { char data; node*
定义：二叉树是有限结点的集合 二叉树有五种形态，有四种表示方法，其中括号表示法是最重要的，下面的链式存储结构也是根据括号表示法来的== 二叉树的性质： 性质1：非空二叉树上的叶子节点数等于双分支节点数加1 性质2：非空二叉树的第i层上最多有2（i-1）个结点 性质3：高度位h的二叉树最多有2（h）-1个结点
非递归其实就是非递归遍历，非递归运用了 栈 的思想，包括了先中后3种方式遍历，费话不多说，开整。
二叉树是每个结点最多有两个子树的树结构，常被用于实现二叉查找树和二叉堆。二叉树是链式存储结构，用的是二叉链，本质上是链表。二叉树通常以结构体的形式定义，如下，结构体内容包括三部分：本节点所存储的值、左孩子节点的指针、右孩子节点的指针。
然后就是一直递归下去，在访问到节点的时候，可以进行节点的相关处理，比如说简单的访问节点值
而我们在数据结构中所探讨的与此有相似之处，又与此有莫大的不同。我们数据结构吗，要从树这种结构说起。
二叉树的深度优先遍历有三种方式，先序（先根次序）、中序（中根次序）和后序（后根次序）遍历。
这次来写一下 LeetCode 的第 94 题，二叉树的中序遍历。
https://leetcode-cn.com/problems/binary-tree-inorder-traversal/
来自：juejin.im/post/5ba3bb52e51d450e942f3031
叶子节点就是左右孩子都是空的，但是并不是每一颗树都像上图所示的那样这么规整，有些树树可以只有左孩子没有右孩子的。二叉树的节点一定会大于左节点的值小于右节点的值，每一个节点都要满足，所有每一个节点下面拿出来的树都可以作为一个二叉树。既然有大于等于了，那么这科树的元素一定要有可比较性才可以。
二叉树是一种非常重要的数据结构。在算法题中经常会使用到，在面试中的占比也是非常大的。
思维导图： 思路分析： 要实现二叉树的非递归遍历，就必须要借助栈的结构特点来实现； 我们根据遍历的顺序，然后对入栈的结点进行分析遍历即可； 代码实现： 就以这个二叉树为例吧！ 1，先序遍历； 对于
二叉树是一种特殊的数据结构，有一个根节点，根节点下面有一左一右两个子节点，每个子节点又有各自的子节点，层层深入成树状。
二叉树是一类简单而又重要的树形结构，在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构，简单的逻辑，广泛的应用和大量的指针操作，在面试过程屡见不鲜，快被面试官玩坏了。相关的问题在百行代码内就可解决，特别适合手写代码，因此我们要充分做好准备，迎接面试时关于二叉树的相关问题，尤其是手写代码。
这一题，需要清楚非递归遍历二叉树的知识，你是否和我一样又回头预习了复习了这个知识呢
一、参考代码 完成比完美更重要，自己动手写一些看 [99] 恢复二叉搜索树 二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下，恢复这棵树。 放轻松，虽然是c++实现，拒绝奇技淫巧，通俗易懂。 //递归遍历 class Solution { public: void recoverTree(TreeNode* root) { // 01 check if (root == NULL) { return; }
本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有，分而治之，搜索，动态规划，回溯，贪心等，结合这些思想再去思考如今很火的大数据，云计算和机器学习，是不是也别有一番风味呢？ 在平凡之路上，开发者不免要读英语文献，推送英语能力提升消息。 01 — 你会学到什么？ 树的递归遍历算法很容易理解，代码也很精简，但是如果想要从本质上理解二叉树常用的三种遍历方法，还得要思考树的非递归遍历算法。 读完后的收获： 您将学到二叉树的中序遍历的非递归版本 明白栈这种数据结构该怎么使用 02 — 讨论的问题是什么？
在上一篇中，我们了解了树的基本概念以及二叉树的基本特点和代码实现，还用递归的方式对二叉树的三种遍历算法进行了代码实现。但是，由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。因此，我们使用非递归（这里主要是循环，循环方法比递归方法快, 因为循环避免了一系列函数调用和返回中所涉及到的参数传递和返回值的额外开销）来重新实现一遍各种遍历算法，再对二叉树的另外一种特殊的遍历—层次遍历进行实现，最后再了解一下特殊的二叉树—二叉查找树。
二叉树的遍历可以说是二叉树最重要的一个内容，如果想对树的算法有一定的认识，那么二叉树的遍历是一定要熟练使用的，本文将主要介绍一下二叉树的遍历。
Given a binary tree, find the left most value in the last row of the tree.
非递归遍历二叉树 中序遍历 leecode94 左根右 var inorderTraversal = function(root) { // 中序遍历 const number= [] const arr = [] while(true){ while(root){ arr.push(root) root = root.left } if (!arr.length) {
发现大家周末的时候貌似都不在学习状态，周末的文章浏览量和打卡情况照工作日差很多呀，可能是本周日是工作日了，周六得好好放松放松，哈哈，理解理解，但我还不能不更啊，还有同学要看呢。
算法实现： pre、mid：前序遍历、中序遍历的结果结果数组 pl、pr、ml、mr：前序、中序遍历结果数组的左右边界 p：创建当前树的根结点 leftRoot、rightRoot：创建当前树的左子树、右子树的根结点 pos：记录当前树的根在中序遍历中的位置 (根在前序遍历中的位置不用记录，前序遍历结果的第一个就是) num：记录左子树结点的个数 lpl、 lpr、 lml、 lmr：记录前序遍历、中序遍历中左子树的范围 rpl,、rpr,、rml、rmr：记录前序遍历、中序遍历中右子树的范围
本公众号主要推送关于对算法的思考以及应用的消息。算法思想说来有，分而治之，搜索，动态规划，回溯，贪心等，结合这些思想再去思考如今很火的大数据，云计算和机器学习，是不是也别有一番风味呢？ 在这个征程中，免不了读英文博客，paper，书籍等，提升英语阅读能力也至关重要呀，为了满足大家需要，本公众号也推送这方面的消息。 01—你会学到什么？ 树的递归遍历算法很容易理解，代码也很精简，但是如果想要从本质上理解二叉树常用的三种遍历方法，还得要思考树的非递归遍历算法。 读完后的收获： “”将学到二叉树的后序遍历的非递归
二叉树（binary tree） 是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
在JS中，存在几个内置属性天然支持数据浅复制，但是每个属性都有一定的适用条件和范围。
二叉树的深度优先遍历算法都是用递归函数实现的，这是很低效的，原因在于系统帮你调用了一个栈并做了诸如保护现场和恢复现场等复杂的操作，才使得遍历可以用非常简洁的代码实现。二叉树深度优先遍历算法的非递归实现用用户定义的栈来代替系统栈，也就是用非递归的方式来实现遍历算法，可以得到不小的效率提升。
给定一个列表，该列表中的每个要素要么是个列表，要么是整数。将其变成一个只包含整数的简单列表。
PS：树型结构是一种重要的非线性数据结构，教科书上一般都是树与二叉树，由此可见，树和二叉树是有区别和联系的，网上有人说二叉树是树的一种特殊形式，但经过查资料，树和二叉树没有一个肯定的说法，但唯一可以肯定都是树型结构。但是按照定义来看二叉树并不是树的一种特殊形式（下面解释）。树型数据结构的作用可以表示数据元素之间一对多的关系，一个公司里的各个部门都可以用树形来表示。
之前学习的链表、队列、栈和数组，都是线性的。而树不同，树是由顶点和边组成的。就像下图，每个结点之间可能存在一定的关系：上下存在父子关系，左右存在兄弟关系。
层序遍历。听名字也知道是按层遍历。我们知道一个节点有左右节点。而每一层一层的遍历都和左右节点有着很大的关系。也就是我们选用的数据结构不能一股脑的往一个方向钻，而左右应该均衡考虑。这样我们就选用队列来实现。
所谓二叉树的遍历，是指按照某条搜索路径访问树中的每个结点，使得每个几点均被访问一次，而且仅被访问一次。
二叉树的非递归遍历
在计算机中，遍历本身是一个线性操作。所以遍历同样具有线性结构的数组或链表，是一件轻而易举的事情。
您可以使用一个栈来存储节点，以便在遍历二叉树时进行回溯。由于您要求不能修改树的结构，我们需要在原树上进行操作。以下是一个可能的解决方案：
俗话说：学如逆水行舟,不进则退;心似平原走马,易放难收。这句话对程序员而言，体会更深。这行已经越来越卷了，时刻准备着😃。 二叉树，在面试中，已是必备的开胃菜。而在二叉树相关的面试题目中，遍历更是常考题目。本文将从二叉树的遍历角度入手，从递归和非递归角度来分析和讲解二叉树的遍历。 遍历 二叉树的遍历是指从根节点出发，按照某种次序依次访问二叉树中的所有节点，使每个节点被且仅被访问一次。 二叉树的遍历，有先序遍历、中序遍历以及后续遍历三种。 图一 上面三种遍历方式中的先序、中序以及后序三种方式，是父节点相对
前序遍历的顺序是根、左、右。任何一颗树都可以认为分为左路节点，左路节点的右子树。先访问左路节点，再来访问左路节点的右子树。把访问左路节点的右子树看成一个子问题，就可以完整递归访问了。
以下是一个使用 Go 语言编写的函数，该函数使用一个栈作为辅助数据结构，以非递归方式遍历二叉树，输出每个结点的关键字。这个算法的时间复杂度为 O(n)。
上图是一棵二叉树，前序遍历结果：1 2 4 5 3 6 咦，我想你可能会疑惑什么叫做前序遍历，其实很简单，就是按照 根 -》 左 -》 右 的方式去遍历二叉树。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
实时音视频
