德赢Vwin官网
App
前序遍历：先访问该节点，然后访问该节点的左子树和右子树；
中序遍历：先访问该节点的左子树，然后访问该节点，再访问该节点的右子树；
后序遍历：想访问该节点的左子树和右子树，然后访问该节点。
递归遍历
对于递归遍历比较简单：
void preorder(TreeNode* root) {
if (root == NULL)
return;
visit(root);
preorder(root->left);
preorder(root->right);
}
void inorder(TreeNode* root) {
if (root == NULL)
return;
inorder(root->left);
visit(root);
inorder(root-
void postorder(TreeNode* root) {
if (root == NULL)
return;
postorder(root->left);
postorder(root->right);
visit(root);
}
非递归（迭代）遍历
非递归实现在遍历根节点后还要回来，因此要基于栈（先进后出）来保存节点。
注：二叉树遍历的非递归实现文章里有不同的实现方式，更易于理解记忆。
前序遍历
压入顺序：右子树->左子树->根节点
使得访问的时候的顺序成为：根->左子树->右子树
vector
vector
stack
if (root == NULL)
return result;
s.push(root);
while(!s.empty()) {
TreeNode* p = s.top();
s.pop();
result.push_back(p->val);
if (p->right)
s.push(p->right);
if (p->left)
s.push(p->left);
}
return result;
}
中序遍历
压入顺序：右子树->根->左子树
只有当左子树已经访问完后，才能访问根节点
对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束
vector
vector
stack
if (root == NULL)
return result;
TreeNode* p = root;
while (!s.empty() || p != NULL) {
if (p != NULL) {
// push 左子树入栈
s.push(p);
p = p->left;
} else {
// 左子树为空时，访问该节点，然后访问右子树
p = s.top();
result.push_back(p->val);
s.pop();
p = p->right;
}
}
return result;
}
后序遍历
先压入根，然后是右子树，最后左子树
要求最后访问根节点，即访问该根节点时必须访问完左子树和右子树，我们只需要保证访问某一节点时，该节点的右子树已经被访问，否则需要将该节点重新压入栈。
对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。
vector
vector
if (root == NULL)
return result;
stack
TreeNode* p = root; //当前正访问的节点
TreeNode* q; //记录刚刚访问过的节点
do{
while (p != NULL) {
s.push(p);
p = p->left;
}
q = NULL;
while (!s.empty()) {
p = s.top();
s.pop();
if (p->right == q) { //当右子树已经访问过了，才可以访问根
result.push_back(p->val);
q = p; //记录刚刚访问过的节点
} else {
s.push(p); //第一次访问到该节点，需要将它重新入栈
p = p->right;
break;
}
}
} while (!s.empty());
return result;
}
二叉树的前序遍历、中序遍历、后续遍历的非递归实现
- C语言(117708)
- 二叉树(12147)
相关推荐
文件系统-多叉树与二叉树的转化
在这一节中，我们来学习如何使用程序来实现一棵文件树。在上一节中，我们了解到使用文件树的方式来整合计算机中所有的资源，而这一棵文件树则是一棵多叉树。也就是说，树上的每一个节点都可能有多个子节点。
2023-10-11 10:06:28
77
77
数据结构面试之二叉树相关操作
根据前序可知根结点为1；
根据中序可知 4 7 2 为根结点 1 的左子树和 8 5 9 3 6 为根结点 1 的右子树；
递归实现，把 4 7 2 当做新的一棵树和 8 5 9 3 6 也当做新的一棵树；
在递归的过程中输出后序。
2023-10-10 14:50:4640
40
如何遍历中文字符串
今天和大家分享下如何遍历中文字符串，主要是如何打印中文字符，因为中文字符串每个字符占用不只一个字节的空间，如果我们逐个字节遍历，会出现奇怪的结果。而UTF-8编码写的中文字符是有特定结构的，我们可以
2023-07-03 09:15:26185
185
解析LeetCode第226号题目：反转二叉树
*简单讲就是把每个节点的左子树和右子树进行交换** 。
显然，这需要我们能够遍历该二叉树。
那么遍历二叉树就有两种经典的解法：深度优先遍历，Deep First Search，简称DFS；另一个是广度优先遍历，Breadth First Search，简称BFS。
2023-02-17 14:52:30405
405
HashMap遍历操作为什么不能一边遍历一遍删除呢？
上面出现这样的原因是在使用 foreach 对 HashMap 进行遍历时，同时进行 put 赋值操作会有问题，异常 ConcurrentModificationException。
2023-02-10 11:25:53233
233
五张图带你体会堆算法
二叉堆是一种特殊的堆，二叉堆是完全二叉树或者近似完全二叉树，二叉堆满足堆特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
2022-11-10 09:29:07359
359二叉树的统一迭代法
我们以中序遍历为例，在二叉树：听说递归能做的，栈也能做！中提到说使用栈的话，无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。
2022-08-03 11:22:59244
244用迭代法编写二叉树的前后中序遍历案例
递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
2022-07-25 15:40:19266
266为什么可以用迭代法来实现二叉树的前后中序遍历呢
我们在栈与队列：匹配问题都是栈的强项中提到了，递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
2022-07-19 11:50:17710
710怎么就能构造成二叉树呢？
一直跟着公众号学算法的录友 应该知道，我在二叉树：构造二叉树登场！，已经讲过，只有 中序与后序 和 中序和前序 可以确定一颗唯一的二叉树。前序和后序是不能确定唯一的二叉树的。
2022-07-14 11:20:47754
754判断对称二叉树要比较的是哪两个节点
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
2022-07-06 16:26:05637
637C语言数据结构：什么是二叉树？
完全二叉树：完全二叉树是效率很高的数据结构。对于深度为K，有n个节点的二叉树，当且仅当每一个节点都与深度为K的满二叉树中编号从1至n的节点一一对应时，称为完全二叉树。
2022-04-21 16:20:101349
1349二叉树上应该怎么求
二叉树上应该怎么求，二叉搜索树上又应该怎么求？ 在求众数集合的时候有一个技巧，因为题目中众数是可以有多个的，所以一般的方法需要遍历两遍才能求出众数的集合。 但可以遍历一遍就可以求众数集合，使用了
2021-11-22 11:32:461063
1063二叉排序树AVL如何实现动态平衡
什么是AVL树 大家好，我是bigsai，好久不见，甚是想念,今天给大家讲讲AVL树。 对于树这种数据结构，想必大家也已经不再陌生，我们简单回顾一下。 在树的种类中，通常分成二叉树和多叉树，我们
2021-10-28 17:02:261246
1246
算法学习中如何打印二叉树节点
大家好，我是吴师兄，直接开始今天的算法学习，冲冲冲。 一、题目描述 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。 例如: 给定二叉树: [3,9,20,null,null
2021-10-22 09:37:001231
1231如何修剪二叉搜索树
的值在[L, R]中 (R=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。 思路 相信看到这道题目大家都感觉是一道简单题（事实上leetcode上也标明是简单）。 但还真的不简单！ 递归法 直接想法就是：递归处理，然后遇
2021-10-11 14:16:201042
1042C++基础语法中的二叉树详解
本期是C++基础语法分享的第十四节，今天给大家来梳理一下树！ 二叉树 BinaryTree.cpp： #include 《stdio.h》#include 《stdlib.h》 #define
2021-09-29 18:02:521662
1662如何才能够翻转二叉树
有所收获！ 226.翻转二叉树题目地址：https://leetcode-cn.com/problems/invert-binary-tree/ 翻转一棵二叉树。 这道题目背后有一个让程序员心酸的故事
2021-09-01 11:45:311390
1390C语言编程中如何求出二叉树后序遍历
题目 已知二叉树前序为 ABDFGCEH 后序序列为 BFDGACEH ，要求输出后序遍历为 FGDBHECA 大体思路 又先序得出根，先序的根后为左树一部分，我们再在中序序列里找到先序的根，此处
2021-08-23 11:04:523299
3299二叉树的所有路径介绍
以为只用了递归，其实还用了回溯 257. 二叉树的所有路径 题目地址：https://leetcode-cn.com/problems/binary-tree-paths/ 给定一个二叉树，返回所有
2021-08-13 17:51:512403
2403
二叉树的前序遍历非递归实现
我们之前说了二叉树基础及二叉的几种遍历方式及练习题，今天我们来看一下二叉树的前序遍历非递归实现。 前序遍历的顺序是， 对于树中的某节点，先遍历该节点，然后再遍历其左子树，最后遍历其右子树。 我们先来
2021-05-28 13:59:071420
1420二叉树操作的相关知识和代码详解
见的二叉树操作作个总结： 前序遍历，中序遍历，后序遍历； 层次遍历； 求树的结点数； 求树的叶子数； 求树的深度； 求二叉树第k层的结点个数； 判断两棵二叉树是否结构相同； 求二叉树的镜像； 求两个结点的最低公共祖先结点； 求任
2020-12-12 11:04:441564
1564
螺旋遍历二维数组漫画讲解
来自公众号：程序员小灰 第二天 什么意思呢？我们来举个例子，给定下面这样一个二维数组： 我们需要从左上角的元素1开始，按照顺时针进行螺旋遍历，一直遍历完所有的元素，遍历的路径就像下图一样： 经过这样
2020-11-26 14:01:421384
1384Offer系列面试题0：重建二叉树
以本题的序列为例，前序遍历序列的第一个数字 3 就是根结点的值，在中序遍历序列，找到根结点值的位置。根据中序遍历特点，在根结点的值 3 前面的数字都是左子树结点的值，在根结点的值 3 后面的数字都是右子树结点的值。
2020-07-09 15:03:541224
1224
红黑树（Red Black Tree）是一种自平衡的二叉搜索树
平衡（Balance）：就是当结点数量固定时，左右子树的高度越接近，这棵二叉树越平衡（高度越低）。而最理想的平衡就是完全二叉树/满二叉树，高度最小的二叉树。
2020-07-01 15:05:404117
4117
删除二叉搜索树中的节点
因为是二叉搜索树，对于树上每个节点来说，其 右子树的节点都要大于其左子树的节点 ，那么要找对应节点，我们可以从根节点开始，一路比较，大的话就去右边找，小的话就去左边找，这样每次我们都往下，可以保证时间复杂度是 O(h)。
2020-06-23 10:33:522701
2701
面试二叉树看这11个就够了
根据前、中序遍历的特点，（根左右、左根右），先根据前序遍历确定根节点，然后在中序遍历知道该根节点的左右树的数量，反推出前序遍历中左子树的结点有哪些。根据该思路进行递归即可完成二叉树的重建。
2019-11-27 16:25:063044
3044面试算法之重建二叉树
节点呢？左子节点有几个呢？很显然我们是不知道的，由此可以得出，只知道前序遍历是不可能反推出二叉树的，中序遍历也是如此，自己可以尝试一下。
2019-11-27 15:59:392203
2203详解电源二叉树到底是什么
作为数据结构的基础，树分很多种，像 AVL 树、红黑树、二叉搜索树....今天我想分享的是关于二叉树，一种基础的数据结构类型。今天从实例入手，给大家介绍一个电源二叉树的分析。
2019-06-06 15:05:468782
8782
二叉树，一种基础的数据结构类型
然后我们再定义一棵深度也为 3 的二叉树，该二叉树的 n 个结点（n≤7），当从 1 到 n 的每个结点都与上图中的编号结点一一对应时，这二叉树就称为完全二叉树。
2019-04-13 10:48:263780
3780
基于二叉树的ensemble异常检测算法
次数即为从决策树的根节点到叶子节点所经历的边数，称之为路径长度（path length）。假设样本集合共有n个样本点，对于二叉查找树（Binary Search Tree, BST），则查找失败的平均路径长度为
2018-12-11 16:57:513610
3610
计算机二级公共基础知识完整版免费下载快来复习吧！
经过对部分考生的调查以及对近年真题的总结分析，笔试部分经常考查的是算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找，读者应对此部分进行重点学习。详细重点学习知识点
2018-09-28 15:30:24
12
12
RFID防碰撞策略
协议内嵌入其中，解决了传统RFID系统标签识别效率较低、成本过高的问题，同时具有较高的安全性优势。与后退二叉树、动态自适应、二叉树搜索等算法进行比较，结果表明该策略能大大降低系统搜索的次数，提高标签的吞吐率。
2018-02-05 15:53:251
1熵的二叉树多类支持向量机的漏洞分类
为了有效提高漏洞分类的准确性，针对基于二叉树多类支持向量机分类算法的分类复杂性和分类结果依赖二叉树的结构等缺点，提出了一种基于熵的二又树多类支持向量机的漏洞分类算法。根据定义最小超球体进行漏洞
2018-01-25 10:40:380
0AVL 树和普通的二叉查找树的详细区别分析
那 AVL 树和普通的二叉查找树有何区别呢？如图，如果我们插入的是一组有序上升或下降的数据，则一棵普通的二叉查找树必然会退化成一个单链表，其查找效率就降为 O(n)。而 AVL 树因其平衡的限制，可以始终保持 O(logn) 的时间复杂度。
2018-01-15 14:36:115199
5199
基于二叉树的算术编码二值化方法
在算术编码研究中，待编码的语法元素需要采用何种二值化方法以及二值化后每个比特的概率模型选择是算术编码算法设计必须面对的问题．提出了一种基于二叉树的熵编码二值化方法．该方法首先获得语法元素的统计概率
2018-01-03 16:53:170
0广度优先遍历的关键路线生成树算法
关键路线的确定对于运用关键路线法进行项目管理具有十分重要的意义。本文首先定义了项目管理图模型，然后在此基础上提出了一种基于广度优先遍历的关键路线生成树算法，最后通过对项目管理图模型的研究，实现了
2017-12-19 11:28:380
0哈夫曼树基本概念与构造
哈夫曼树又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。若在一棵树中存在着一个结点序列 k1，k2，……，kj， 使得 ki是ki+1 的双亲（1《=i《j），则称此结点序列是从 k1 到 kj 的路径。
2017-12-11 10:01:1233480
33480
二叉树层次遍历算法的验证
实现二叉树的层次遍历算法，并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。
2017-11-28 01:05:461723
1723
如何使用递归遍历转换树形数据
广度遍历的过程是把所有节点扁平化到一个队列中了，这个过程是不可逆 的，换句话说，我们在处理过程中丢掉了树形结构信息。然后我们要生成的 DOM 树，是需要结构信息的——因此，需要将结构信息附加在每个节点上。这里我们把生成的 DOM 和数据节点绑定起来，由 DOM 保存结构信息。
2017-11-02 16:46:304277
4277
java 二叉树实现
父子关系的节点的有限集合。对于这个有限的节点集合而言，它满足如下条件： 当N=0时，改节点集合为空，这课树也被称为空树 在任意的非空树中，有且仅有一个根（root）节点 当N》1时，除根节点以外的其余节点可分为M个互为相交的有限集合T1，
2017-09-28 14:48:162
2遍历图像像素的14种方法_OpenCV2版书本配套示例程序24
遍历图像像素的14种方法_OpenCV2版书本配套示例程序24，来自一本国外OpenCV2书籍的示例-遍历图像像素的14种方法。
2016-06-06 15:20:546
6二叉树法遍历查找代码
2015-10-12 18:10:314
4先序创建一颗二叉树遍历
2014-03-17 18:27:0813
13基于二叉树的时序电路测试序列设计
为了实现时序电路状态验证和故障检测，需要事先设计一个输入测试序列。基于二叉树节点和树枝的特性，建立时序电路状态二叉树，按照电路二叉树节点(状态)与树枝(输入)的层次逻辑
2012-07-12 13:57:4034
34华为部分面试题
第二部分，填空题 1. 什么是UML？分哪两类？ 2. OS一般的两种进程调度策略 3. 进程间的四种通讯方式 4. 一棵二叉树的前序，中序，后序遍历结果
2011-09-07 16:14:17138
138Merkle树遍历技术的研究
Merkle树应用于数字加密技术。它的遍历技术主要包含树的根节点生成和认证路径的生成。本文主要比较各种Merkle树的遍历技术,提出自己的遍历方法,并进行了实验仿真和对实验结果的
2010-03-01 16:16:0214
14基于Hash和二叉树的路由表查找算法
基于Hash和二叉树的路由表查找算法
:提出了一种基于Hash和二又树的路由表查找算法，这一算法可以满足()C-768的转发要求，支持超过10万条前缀的大规模路由表，并且
2010-02-22 17:06:1535
35基于二叉树分解的自适应防碰撞算法
该文提出了一种基于二叉树分解的自适应防碰撞算法。新算法利用标签EPC 的唯一性，通过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二叉树搜索，从而将一个庞大且复杂
2009-11-17 14:09:2821
21基于三角形二叉树的实时大规模地形渲染算法
提出一种大规模地形渲染算法，对大规模地形进行分块，用三角形二叉树表示地形网格，在实时漫游中，通过强制分割和强制合并实时更新网格，充分利用帧与帧之间的连贯性并自
2009-04-01 09:20:2517
17二叉树算法在单总线技术中的应用
介绍了单总线技术和二叉树算法。单总线技术可以将地址线、数据线和控制线合成一根线，并允许在这根线上挂接多个单总线器件。提出了用二叉树算法搜索单总线器件注册码，并
2009-03-16 09:38:1220
20
工商网监
评论