非递归前序

法一(技巧)

• 非递归的前序 。我们利用栈的性质替代递归，因为递归有时候在效率方面不是令人满意的。
• 利用栈，我们直到栈的顺序为现金先出。那么 顺序如何添加 ？递归是左递归，右递归。但是利用栈要相反，因为如果左进栈、右进栈会出现以下后果：

• 所以，我们要利用递归的思路， 需要先放右节点进栈，再放左节点进栈 ，这个下次·再取节点取到左节点·，这个节点再右节点进栈，左节点进栈。然后循环一直到最后会一直优先取到左节点。达到和递归顺序相仿效果。

• 每pop完添加右左节点直接输出(访问)即可完成前序非递归遍历。

public void qianxu3( node t)// 非递归前序 栈 先左后右 t一般为root

{

Stack<node> q1 = new Stack<node>();

if (t == null)

return;

if (t != null) {

q1.push(t);

}

while (!q1.empty()) {

node t1 = q1.pop();

if (t1. right != null) {

q1.push(t1.right);

}

if (t1.left != null) {

q1.push(t1.left);

}

System.out.print(t1.value + ” “);

}

}

法二(传统)

方法二和非递归 中序遍历 的方法类似，只不过需要修改输出时间，在进栈时候输入访问节点即可。 具体参考中序遍历分析 。

public void qianxu2(node t) {

Stack<node> q1 = new Stack();

while(!q1. isEmpty ()||t!=null)

{

if (t!=null) {

System.out.print(t.value+” “);

q1.push(t);

t=t.left;

}

else {

t=q1.pop();

t=t.right;

}

}

}

非递归中序

非递归中序和前序有所区别。

我们直到中序排列的顺序是：左节点，根节点，右节点。那么我们在经过根节点的前面节点 不能释放 ， 因为后面还需要用到它。所以要用栈先储存。

它的规则大致为 ：

• 栈依次存入左节点所有点，直到最左侧在栈顶。
• 开始抛出栈顶并访问。(例如第一个抛出2)。 如果有右节点 。那么将右节点加入栈中， 然后右节点一致左下遍历直到尾部 。（这里5和7没有左节点，所以不加） 但是 如果抛出15。右节点加入23.再找23的左侧节点加入栈顶。就这样循环下去直到栈为空。

可行性分析：中序是左—中—右的顺序。访问完左侧。当 抛出当前点 的时候说明 左侧已经访问完(或者自己就是左侧) ，那么需要首先访问当前点的右侧。那么这个右节点把它当成根节点重复相同操作（因为右节点要满足先左再右的顺序）。这样其实就是 模拟了一个递归的过程 ，需要自己思考。

实现代码1：

public void zhongxu2(node t) {

Stack<node> q1 = new Stack();

while(!q1.isEmpty()||t!=null)

{

if (t!=null) {

q1.push(t);

t=t.left;

}

else {

t=q1.pop();

System.out.print(t.value+” “);

t=t.right;

}

}

}

实现代码2：(个人首次写的)

public void zhongxu3(node t)// 先储藏所有左侧点，抛出一个点，访问该点右节点，对右节点在储存所有子左节点

{

Stack<node> q1 = new Stack();

if (t == null)

return;

if (t != null) {

q1.push(t);

}

node t1 = q1.peek();// 不能抛出，要先存最左侧

while (t1.left != null) {

t1 = t1.left;

q1.push(t1);

}

while (!q1.isEmpty()) {

node t2 = q1.pop();

System.out.print(t2.value + ” “);

if (t2.right != null) {

t2 = t2.right;

q1.push(t2);

while (t2.left != null) {

t2 = t2.left;

q1.push(t2);

}

}

}

}

非递归后序※

非递归 后序遍历 有两种方法

一种方法是利用和前面中序、前序第二种方法类似的方法进入压栈出栈，但是要借助额外的标记次数，一个节点访问第二次才能输出。(这个访问第一次是入栈，第二次是子树解决完毕自己即将出栈（先不出栈）)。

法1(传统方法)

在前面的前序和中序先到最左侧压入栈的时候，两种顺序依次是

• 前序: 中入栈——>左入栈——>左出栈——>中出栈——>右入栈——>右孩子入出——>右出栈 在入栈时候操作即可前序
• 中序: 中入栈——>左入栈——>左出栈——>中出栈——>右入栈 ——>右孩子入出——>右出栈 按照出栈顺序即可完成中序

而在后序遍历中：它有这样的规则：

• 入栈，第一次访问
• 即将出栈。第二次访问，
• 如果有右孩子 ，先不出栈把右孩子压入栈第一次访问， 如果没右孩子 。访问从栈中弹出。
• 循环重复，直到栈为空

实现代码为(用map记录节点出现次数)：

public void houxu2(node t) {

Stack<node> q1 = new Stack();

Map<Integer,Integer >map=new HashMap<>();

while(!q1.isEmpty()||t!=null)

{

if (t!=null) {

q1.push(t);

map.put(t.value, 1); //t.value标记这个值节点出现的次数

t=t.left;

}

else {

t=q1.peek();

if(map.get(t.value)==2) {//第二次访问，抛出

q1.pop();

System.out.print(t.value+” “);

t=null;//需要往上走

}

else {

map.put(t.value, 2);

t=t.right;

}

}

}

}

法2(双栈)：

另一种方法是借助 双栈 进行处理。我们曾在前序方法一借助一个栈右压，左压。持续让达到一个前序遍历的效果。但是这个方法很难实现后续。

• 分析相同方法，如果我们先压左，再压右，那么我们获得的顺序将是和前序完全相反的顺序（ 顺序为 ：中间，右侧，左侧。 倒过来刚好是左侧、右侧、中间的后续 ）对称看起来的前序。即用另一个栈将序列进行反转顺序！

• 如果再这个过程，我们利用另一个栈进行储存，将它的首次入栈用一个栈存入， 相当于起到一个反转的作用 。

• 实现代码为：

public void houxu3(node t)// q1和q2 q1要先右后左，先遍历右侧，q1先装右侧就把右侧放到前面，左侧放在上面（栈顶）

{

Stack<node> q1 = new Stack();

Stack<node> q2 = new Stack();

if (t == null)

return;

if (t != null) {

q1.push(t);

}

while (!q1.isEmpty()) {

node t1 = q1.pop();

q2.push(t1);

if (t1.left != null) {

q1.push(t1.left);

}

if (t1.right != null) {

q1.push(t1.right);

}

}

while (!q2.isEmpty()) {

node t1 = q2.pop();

System.out.print(t1.value + ” “);

}

}

总结

测试结果：

这部分内容比较多，也可能比较杂，希望大家好好吸收，也可能笔者写的大意或者错误。还请大佬指正。！

• 另外，完整代码还请关注公众号(bigsai)。笔者认真更新数据结构与算法。有兴趣可以关注一波学一起学习。回复 数据结构 或者 爬虫 有精心准备学习资料赠送。