二叉树 2.0 -- 非递归遍历
二叉树递归遍历存在的问题
如果我们的二叉树只有左子树，而且树的高度还很深的时候，这个时候递归调用遍历的时候，栈帧空间开辟的较大，很可能造成栈溢出。但是我们一个程序中，为堆分配的空间要比栈大的多，这个时候我们可以实现一个二叉树遍历的非递归的实现形式，模拟栈帧调用的过程，自己模拟一个栈用于保存节点，然后实现遍历。
非递归实现树的遍历
前序
首先设置一个指针cur指向根节点，访问cur然后让cur入栈，并且是在循环中使cur一直指针它的的左子树，入栈的时候就访问了，当我们出栈的时候就使cur指向它的右子树，这里我们需要两层循环，一层主要是判断当前的栈是否为空的，一层主要是判断一直往左走的时候什么时候到达了左子树的尽头了。
void PrevNoROeder(){stack<Node*> sn;Node* cur = _root;while (cur || !sn.empty()){while (cur){cout << cur->_data << " ";sn.push(cur);cur = cur->_left;}cur = (sn.top())->_right;sn.pop();}cout << endl;}其实可以这样子理解的，我们的前序实际上是把所有的问题都转化成了访问了左子树，即使是访问右子树的时候，也好像是访问左子树一样，就是把这个树当成了一个树根
中序
同样是上面的内容，这个时候也是可以使用cur内容的，但是这个时候我们不是先访问，而是先进栈，当我们出栈的时候，我们在访问，然后出栈，出栈的时候把出来的这个节点的右子树当成是一个cur，这个时候还是一直当成是一个左子树来访问了
void InNoROrder(){stack<Node*> sn;Node* cur = _root;while (cur || !sn.empty()){while (cur){sn.push(cur);cur = cur->_left;}cout << (sn.top())->_data<<" ";cur = (sn.top())->_right;sn.pop();}cout << endl;}后序
首先让cur指向的是一个root，然后这个时候让cur一直往左走，当走到NULL的时候，我们想要出栈但是还不能出栈，因为我们还不知道当前节点的右子树是不是已经访问了呢。所以我们加上了一层判断，就是当我们的当前节点的右子树不是空的时候，并且当前节点的右子树不是刚刚出栈的节点的时候，我们就需要把当前节点的右子树。这里因为需要判断当前节点的右子树是不是刚刚出栈的节点，所以我们每次出栈的时候都需要标记一下当前出栈的节点，以便后来的比较使用。如果不是之前访问的节点，我们就可以出栈访问了。
void EndNoROrder(){stack<Node*> sn;Node* cur = _root;Node* prev = _root;while (cur || !sn.empty()){if (cur) //让所有的左子树入栈{sn.push(cur);cur = cur->_left;}else //所有的左子树都入栈了{if (((sn.top())->_right != NULL) && ((sn.top())->_right != prev)){cur = (sn.top())->_right;}else //所有的左右子树都访问完毕了{cout << (sn.top())->_data<<" ";prev = sn.top();sn.pop();}}}cout << endl;}通过上面的非递归三种方式的比较我们可以发现，三个的一个共同点是，一开始都是让所有的左子树节点先入栈，其中先序遍历的时候，入栈的时候就直接访问了，中序遍历的时候是出栈的时候才访问的，还有一个点就是，出栈的时候让cur指向栈顶的右子树，先序遍历和中序遍历是直接入栈的，但是后序遍历是需要一层判断，就是如果右子树不是刚刚访问过的，说明当前右子树还没有访问过，这个时候就需要访问右子树，如果是刚刚访问过的，这个时候就可以直接让cur出栈访问就好了，就是我们在后序遍历的时候，在即将出栈的时候需要加上一层判断就是当前的右子树是否已经被访问过了，如果没有被访问过，我们就需要是当前的右子树入栈如果访问过了，我们就可以使当前的top出栈了访问他了
相关文章：
田忌赛马贪心算法_田忌赛马 贪心算法
算法实验课回顾田忌赛马问题描述：你一定听说过田忌赛马的故事吧？如果3匹马变成n匹(n<100)，齐王仍然让他的马按照优到劣的顺序初赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子；输…
[转][小结][三种方法]实现WPF不规则窗体
实现WPF不规则窗体的三种常用的方法如下： 1.使用Blend等工具绘制一个不规则xaml，然后作为窗体的背景。这个可以参考xiaowei0705的这篇博文：WPF制作不规则的窗体 。 2.给window的Clip属性赋Path值。这个可以参考DebugLZQ前面的博文：…
VirtualBox虚拟机网络连接设置的四种方式
这里我先给大家大致讲解下VBox的网络配置及应用。 VirtualBox的提供了四种网络接入模式，它们分别是：1、NAT 网络地址转换模式(NAT,Network Address Translation)2、Bridged Adapter 桥接模式3、Internal 内部网络模式4、Host-only Adapter 主机…
redis-deskmanager 连不上 虚拟机 - centos redis
1、没设置redis密码 ： https://blog.csdn.net/HUXU981598436/article/details/54668779 2、关闭防火墙 转载于:https://www.cnblogs.com/Jomini/p/9650650.html
数据库1.0 -- 数据库的基本操作
安装数据库 安装数据库的时候我们需要安装三个软件，使用下面的命令，可能还会出现一些问题，关于数据库的安装，大家可以上网自行百度 yum install mysql yum install mysql-server yum install mysql-devel 我个人的理解大概是这…
12,缓冲运动。匀速运动停止条件
缓冲运动：iSpeed(iTarget-oDiv.offsetLeft)/7;速度离目标点越远，速度越大，离目标点越近速度越小； 只支持1px是最小单位，没有0.5px。所以当iSpeed为小数时如（0.7），oDiv.style.LeftoDi…
如何配置mac的mysql环境_mac安装mysql数据库及配置环境变量
安装mysql下载mysql。我下载的是：mysql-8.0.11-macos10.13-x86_64.dmg双击打开mysql-8.0.11-macos10.13-x86_64.dmg，然后双击mysql-8.0.11-macos10.13-x86_64.pkg一路点击继续，傻瓜式安装，没什么好说的此处选择“Use Legacy Passw…
三层交换机vlan间访问(第一种方式)
真的是原创，但是得感谢Ys_routesim软件的制作方。我将命令调试后并进行了解释。若是属于侵权，请立即告知我。不过学习了网工后，大段解读源代码不属于侵权吧。呵呵。 交换机的三层交换实际是具有路由功能的交换机，比如思科的Cisco …
(转载)深入浅出设计模式——桥接模式（Bridge Pattern）
模式动机设想如果要绘制矩形、圆形、椭圆、正方形，我们至少需要4个形状类，但是如果绘制的图形需要具有不同的颜色，如红色、绿色、蓝色等，此时至少有如下两种设计方案： 第一种设计方案是为每一种形状都提供一套各种颜色…
数据库2.0 -- 数据类型和数据表的基本操作
mysql支持多种数据类型，一般可以分为，数值，日期时间和字符（串） 数值类型 日期和时间类型 字符串类型 创建数据表 我们首先应该明白的就是一个结构的问题，一个用户可以管理多个数据库，每个数据…
virtual hust 2013.6.20 数论基础题目 D - Just the Facts
题目：Just the Facts 思路：枚举10000素数内，各因子出现的次数，然后取模为10。因为0是由2和5构成的，所以2和5的幂单独讨论，同时由于2的幂肯定大于5的，所以我们最后要算的再乘上2的减去后的幂就可…
MySQL中字段约束有哪些_mysql字段约束
为了确保数据的完整性和唯⼀性，关系型数 据库通过约束机制来实现目。一. unique 唯一性约束值不可重复；二. not null 非空约束值不可为空；三. default 默认值约束当增加数据时没有插⼊值时，会自动插⼊默认值；四. chec…
关于软件测试中那点小事中的大道理
如果想让测试在公司的项目中发挥出它最大的价值，并不是招两个测试技术高手，或引入几个测试技术，而是测试技术对项目流 程的渗透，以及测试流程的改进与完善。虽然，当然测试行业前景乐观，许多中小企业也都在引…
每日一题 -- 11-1
一天十题选择，一天一道编程，一天一个面试题，一个一个剑指offer 排序是必须要掌握的一个算法，非常的重要 题目描述 有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学…
Java中? extends T和? super T的理解
? 通配符类型 - <? extends T> 表示类型的上界，表示参数化类型的可能是T 或是 T的子类; <? super T> 表示类型下界（Java Core中叫超类型限定），表示参数化类型是此类型的超类型（父类型）&…
学习Modern UI for WPF
这两天断断续续的学了学Modern UI for WPF 没啥学习笔记呵呵，来自大牛王春明的博客园 http://www.cnblogs.com/wangchunming/category/342887.html 此大牛学习范围之广 成果之丰富 着实是学习的典范转载于:https://www.cnblogs.com/DragonX/p/3146818.html
idea的tomcat配置文件在哪里修改_MyBatis配置文件详解
MyBatis 的配置文件包含了会影响 MyBatis 行为的设置和属性信息，决定了mybatis的运行轨迹，能充分了解这些配置的以及配置所带来的的影响，你就是大神！配置文件的根节点是configuration，他的子孙节点有：prope…
《几何与代数导引》例1.4——定比分点
点$r$分有向线段$\vec{pq}$成定比$k$,即$\vec{pr}k\vec{rq}(k\neq-1)$.在仿射标架中，已知$p(a_1,a_2,a_3)$,$q(b_1,b_2,b_3)$和$k$,求$r(c_1,c_2,c_3)$解:由于$c_i-a_ik(b_i-c_i)$,因此$c_i\frac{kb_ia_i}{1k}$.转载于:https://www.cnblogs.com/yeluqing/archive/20…
C#第一个程序Helloworld
转载于:https://www.cnblogs.com/gzhbk/p/9656149.html
Leanote
https://github.com/leanote/leanote/wiki/Leanote-%E4%BA%8C%E8%BF%9B%E5%88%B6%E7%89%88%E8%AF%A6%E7%BB%86%E5%AE%89%E8%A3%85%E6%95%99%E7%A8%8B—-Mac-and-Linux 安装的网址 我们相当于是在本地建立了一个服务器，然后将我们的leanote部署上去了 我们这里的启…
微软安全新闻聚焦-双周刊第三十四期
Biweekly Spotlights 2013. 6. 5– 2013. 6. 20 第 34 期 微软发布 EMET 4.0 2013年6月17日 Enhanced Mitigation Experience Toolkit(EMET) 是微软提供的一个免费的攻击防御工具，它依托 Windows 系统本身的防御机制来阻止攻击者对各类…
mysql如何实现实时存储_OpenResty + Mysql 实现日志实时存储
应用场景和日志文件解析本配置主要解决 Nginx 向 MySQL 中实时插入日志的问题，采用 OpenResty Mysql 实现。1. 刚开始的时候看了 Nginx 和 MySQL 的连接模块。比如说 nginx-mysql-module，可以连接 MySQL。但是插入日志时遇到问题，我们知道 n…
简易RS232 建模二 （接收）
//clK系统时钟为50MHZ 先发低位后发高位 先接收地位后接收高位module uart_tx (input clk,rst_n, UART_CTS, output reg UART_RTS, input UART_RXD, output reg UART_TXD, output [7:0] led);reg [3:0]state;reg [30:0] count;reg [7:0] data;assign led rx_data; reg [7:0] …
《UNIX高级环境编程》 -- apue.h
在看《UNIX高级环境编程》这本书的时候，会遇到一个问题就是这个”apue.h”,这个是作者为了编写代码方便封装了一个库，我们可以使用下面的方式解决这个问题，让我们的代码可以像作者一样去使用，这样的话，我们就可以好好研…
mysql 多少个数据库_mysql数据库的几个基本概念
1、表数据库表是一系列二维数组的集合，用来存储数据和操作数据的逻辑结构。行是记录，列是字段，每一列表示记录的一个属性，都有相应的描述信息。2、数据类型：数据类型决定了数据在计算机中的存储格式，代表不…
教孩子正确对待分数
期末考试各科成绩渐渐公布了，小丽迫不及待地跑到办公室向老师打听分数。看到自己那一科成绩好时欣喜若狂，看到差的则懊悔不已。如果你的孩子也象小丽一样视考分为命根，该如何教孩子正确对待分数?让她从考分的困惑中解放出来?●考前给孩子制…
canvas初尝试
最近学习了canvas，就拿它做了这么个小东西，感觉已经爱上canvas了。上代码 /* * auhor : 开发部-前端组-李鑫超 * property { tableData : {Array} 表格数据 add v-1.0.0 } * property { columData : {Array} 表头数据 add v-1.0.0 } * property { me…
模板1.0 -- 模板基本原理
为什么需要模板 我们经常有这样的一种使用的情形，就是我们可能需要设计一个函数，然后函数的参数可能是整形的，也可能是浮点型的，还有可能是其他的类型的，这个时候如果对于每一个类型都写一个函数，未免有点…
[置顶] 我的GB28181标准开发里程碑——基于eXosip的IPC端与SPVMN注册成功
昨天编译搭建好eXosip的开发环境后，今天完成了SIP注册功能，里程碑一战啊！加油加油，成功就在眼前！ 今天基于eXosip做了一个IPC客户端，成功与公安部的SPVMN视频监控联网调测软件自测工具进行注册交互…
mysql如何避免特殊字符查询_如何避免MySQL中的特殊字符？
慕的地10843我已经用Java开发了自己的MySQL转义方法(如果对任何人都有用的话)。请参阅下面的类代码。警告：如果启用了任何_反斜杠_转义SQL模式，则出错。private static final HashMap sqlTokens;private static Pattern sqlTokenPattern;static{ …