算法练习28（非递归方式遍历二叉树的先序中序后序） _二叉树

满堂花醉三千客，一剑霜寒十四洲。这篇文章主要讲述算法练习28：非递归方式遍历二叉树的先序中序后序相关的知识，希望能为你提供帮助。
来源于《程序员代码面试指南》仅用于个人学习和记录，便于复习
先序遍历

用递归方法解决的问题都能用非递归方法实现，这是因为递归方法无非就是利用函数栈来保存信息，如果用自己申请的数据结构来代替函数栈，也可以实现相同的功能。用非递归的方法实现二叉树的先序遍历，具体过程如下： 1、申请一个新的栈，记为stack,然后将头节点head压入stack中 2、从stack中弹出栈顶节点，记为cur,然后打印cur节点的值，再将节点cur的右孩子节点(不为空的话)先压入stack栈中，最后将cur的左孩子节点(不为空的话)压入stack中。 3、不断重复步骤2，直到stack为空，全部过程结束。

1、节点1先入栈，然后弹出并打印，1的右节点3先入栈，再把1的左节点2压入，stack从栈顶到栈底依次为2，3 2、节点2弹出并打印，先压入2的右节点5，再压入2的左节点4，stack从栈顶到栈底依次为4，5，3 3、节点4弹出并打印，节点4没有孩子节点压入stack，从栈顶到栈底依次为5，3。 4、节点5弹出并打印，节点5没有孩子节点压入stack，从栈顶到栈底依次为3。 5、节点3弹出并打印，将节点3的右节点7压入栈，再将节点3的左节点6压入栈，从栈顶到栈底依次为6，7 6、节点6弹出并打印，节点6没有孩子压入stack，从栈顶到栈底依次为7。 7、节点7弹出并打印，节点7没有孩子压入stack，stack已为空，过程停止。

文章图片

package com.example.springboot; import java.util.Stack; public class UnRecursiveTraversalBT public static class Node public int value; public Node left; public Node right; public Node(int v) value = https://www.songbingjia.com/android/v; //先序 public static void pre(Node head) System.out.println("先序遍历开始"); if (head!=null) Stack< Node> stack=new Stack< Node> (); stack.add(head); while (!stack.isEmpty()) head = stack.pop(); System.out.print(head.value+" "); if (head.right!=null) stack.push(head.right); if (head.left!=null) stack.push(head.left); System.out.println(); public static void main(String[] args) Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); head.right.right = new Node(7); pre(head); System.out.println("========");

中序遍历

用非递归的方式实现二叉树的中序遍历 1、申请一个新的栈stack，。初始时，令cur=head 2、先把cur节点压入栈中，对以cur节点为头节点的整棵树来说，依次把左边界压入栈中，即不停的令cur=cur.left,然后重复2 3、不断重复步骤2，直到cur为空，此时从stack中弹出第一个节点，记为node，打印node的值，并且让cur=node.right，并且重复步骤2. 4、当stack为空，且cur为空时，整个过程停止。

1、初始cur节点为1，将节点1压入stack，令cur=cur.left，即cur=2 2、cur节点为2，将节点2压入stack，令cur=cur.left，即cur=4 3、cur节点为4，将节点4压入stack，令cur=cur.left，即cur=null，从栈顶到栈底依次为4，2，1 4、cur=null，弹出栈顶第一个元素4并打印，并且记node=4，令cur=node.right，cur=null，从栈顶到栈底依次为2，1 5、cur=null，弹出栈顶第一个元素2并打印，并记node=2，令cur=node.right，cur=5，此时从栈顶到栈底依次为1 6、cur=5，将节点5压入stack，令cur=cur.left，即cur=null，此时从栈顶到栈底依次为5，1 7、cur=null，弹出栈顶5节点并打印，并记node=5，令cur=node.right，cur=null,此时从栈顶到栈底依次为1 8、cur=null，弹出栈顶节点1并打印，并记node=1，令cur=node.right，cur=3，此时stack=null 9、cur=3，将节点3压入stack，令cur=cur.left，cur=6，此时从栈顶到栈底依次为3 10、cur=6，将6压入stack，令cur=cur.left，cur=null，此时从栈顶到栈底依次为6，3 11、cur=null，弹出栈顶6节点并打印，并记node=6，令cur=node.right，cur=null，此时，从栈顶到栈底依次为3 12、cur=null，弹出栈顶元素3并打印，并记node=3，令cur=node.right，cur=7，此时stack=null. 13、cur=7，将7压入stack，，令cur=cur.left，cur=null，此时栈顶到栈底元素为7. 14、cur=null，此时弹出栈顶元素7，并记node=7，令cur=node.right，cur=null，stack=null，流程结束。

文章图片

package com.example.springboot; import java.util.Stack; public class UnRecursiveTraversalBT public static class Node public int value; public Node left; public Node right; public Node(int v) value = https://www.songbingjia.com/android/v; //中序遍历 public static void in(Node head) if(head!=null) Stack< Node> stack=new Stack< Node> (); while (!stack.isEmpty() || head!=null) if(head!=null) stack.push(head); head=head.left; else head=stack.pop(); System.out.print(head.value +" "); head=head.right; System.out.println(); public static void main(String[] args) Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); head.right.right = new Node(7); in(head); System.out.println("========");

后序遍历

用非递归的方式实现二叉树的后序遍历此方法为两个栈实现后序遍历 1、申请一个栈，记为s1，然后将头节点head压入s1中 2、从s1中弹出的节点记为cur，然后依次将cur的左孩子和右孩子压入s1中。 3、在整个过程中，每一个从s1中弹出的节点都放进s2中 4、不断重复步骤2和步骤3，直到s1为空，过程停止 5、从s2中依次弹出节点并打印，打印出的节点顺序就是后序遍历的顺序

1、节点1放入s1中 2、从s1中弹出节点1，节点1放入s2中，然后将2节点和3节点依次放入s1，此时s1从栈顶到栈底为3，2，s2从栈顶到栈底为1 3、从s1中弹出节点3，节点3放入s2，然后将6，7依次放入s1，此时s1从栈顶到栈底依次为7，6，2，s2从栈顶到栈底依次为3，1 4、s1中弹出7节点，7节点放入s2，7无孩子节点，此时s1从栈顶到栈底依次为6，2，s2从栈顶到栈底依次为7，3，1 5、s1中弹出6节点，6节点放入s2，6节点无孩子节点，此时s1从栈顶到栈底依次为2，s2从栈顶到栈底依次为6，7，3，1 6、s1中弹出2节点，2节点放入s2，然后依次将4，5放入s1，此时s1从栈顶到栈底依次为5，4，s2从栈顶到栈底依次为2，6，7，3，1 7、s1中弹出节点5，，节点5放入s2，5节点没有孩子节点，此时s1从栈顶到栈底依次为1，s2从栈顶到栈底依次为5，2，6，7，3，1 8、从s1中弹出节点4，节点4放入s2，4节点没有孩子节点，此时s1=null，s2从栈顶到栈底依次为4，5，2，6，7，3，1 9、此时过程结束，将s2中依次弹出并打印4，5，2，6，7，3，1。

文章图片

package com.example.springboot; import java.util.Stack; public class UnRecursiveTraversalBT public static class Node public int value; public Node left; public Node right; public Node(int v) value = https://www.songbingjia.com/android/v; //后序遍历 public static void posOrderUnRecuel(Node head) if(head!=null) Stack< Node> s1 = new Stack< > (); Stack< Node> s2 = new Stack< > (); s1.add(head); while (!s1.isEmpty()) head = s1.pop(); s2.push(head); if(head.left!=null) s1.push(head.left); if(head.right!=null) s1.push(head.right); while (!s2.isEmpty()) System.out.print(s2.pop().value+" "); public static void main(String[] args) Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); head.right.right = new Node(7); posOrderUnRecuel(head); System.out.println("========");

使用一个栈处理后序遍历

1、申请一个栈stack，将头节点压入stack，同时设置两个变量h和c，在整个流程中，h代表最近一次弹出并打印的节点，c代表stack栈顶节点，初始时，h为头节点，c为null 2、每次令c等于当前stack的栈顶节点，但是不从stack中弹出，此时分以下三种情况 ①如果c的左孩子节点不为null，并且h不等于c的左孩子节点，也不等于c的右孩子节点，，则把c的左孩子节点压入stack中，。解释一下原因：首先h的意义是最近一次弹出并打印的节点，所以h等于c的左孩子节点或右孩子节点，说明c的左子树或者c的右子树已经打印完毕，此时不应该再将c的左孩子放入栈中，否则说明左子树还没处理过，此时将c的左子树压入栈中。 ②如果①不成立，且c的右孩子不为空，h不等于c的右孩子节点，c把右孩子节点压入栈中。解释一下原因:如果h等于c的右孩子节点，说明c的右子树已经打印完了，此时不应该再将c的右孩子节点压入栈中。否则说明右子树还没处理过，此时将c的右孩子节点压入stack中。 ③如果条件①和条件②都不成立，说明c的左子树和c的右子树都已经打印完毕，那么从stack中弹出c并打印，然后令h=c。 3、一直重复步骤2，直到stack为空，过程停止。

1、节点1压入stack，初始时h节点为节点1，c为null，stack从栈顶到栈底为1。 2、令c等于stack的栈顶节点——节点1，此时步骤2的条件①命中，将节点2压入stack，h为节点1，stack从栈顶到栈底依次为2，1. 3、令c等于stack栈顶节点——节点2，此时步骤2的条件①命中，将节点4压入stack，h为节点1，stack从栈顶到栈底依次为4，2，1 4、令c等于stack栈顶节点——节点4，此时步骤2的条件③命中，将节点2弹出并打印，h为节点4，stack从栈顶到栈底依次为2，1. 5、令c等于stack栈顶节点——节点2，此时步骤2的条件②命中，节点5压入stack中，h为节点4，stack从栈顶到栈底依次为5，2，1 6、令c等于stack栈顶节点——节点5，此时步骤2的条件③命中，将节点5弹出并打印，h为节点5，stack从栈顶到栈底依次为2，1 7、令c等于stack栈顶节点——节点2，此时步骤2的条件③命中，将节点2弹出并打印，h为节点2，stack从栈顶到栈底依次为1 8、令c等于stack栈顶节点——节点1，此时步骤2的条件②命中，将节点3压入stack，h为节点2，stack从栈顶到栈底依次为3，1 9、令c等于stack栈顶节点——节点3，此时步骤2的条件①命中，将节点6压入stack，h为节点2，stack从栈顶到栈底依次为6，3，1 10、令c等于stack栈顶节点——节点6，此时步骤2的条件③命中，将节点6弹出并打印，h为节点6，stack从栈顶到栈底依次为3，1 11、令c等于stack栈顶节点——节点3，此时步骤2的条件②命中，将节点7压入stack，h为节点6，从栈顶到栈底依次为7，3，1 12、令c等于stack栈顶节点——节点7，此时步骤2的条件③命中，将节点7弹出并打印，h为节点7，从栈顶到栈底依次为3，1 13、令c等于stack栈顶节点——节点3，此时步骤2的条件③命中，将节点3弹出并打印，h为节点3，从栈顶到栈底依次为1 14、令c等于stack栈顶节点——节点1，此时步骤2的条件③命中，将节点1弹出并打印，h为节点1，stack为空，过程结束。

【算法练习28（非递归方式遍历二叉树的先序中序后序）】

文章图片

package com.example.springboot; import java.util.Stack; public class UnRecursiveTraversalBT public static class Node public int value; public Node left; public Node right; public Node(int v) value = https://www.songbingjia.com/android/v; //后序遍历 public static void pos(Node head) if(head!=null) Stack< Node> stack=new Stack< Node> (); stack.add(head); Node c=null; while (!stack.isEmpty()) c=stack.peek(); if(c.left!=null & & head!=c.left & & head!=c.right) stack.push(c.left); else if(c.right!=null & & head!=c.right) stack.push(c.right); else System.out.print(stack.pop().value+" "); head=c; System.out.println(); public static void main(String[] args) Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); head.right.right = new Node(7); pos(head); System.out.println("========");