前言
参加多益的笔试，让写一个二叉树的后续遍历，咋一看这不是很easy吗，仔细一看，要求非递归实现，额.....抱歉，不会了，于是在这里特地整理下二叉树三种遍历方式的非递归实现。
分析
前序遍历，即“根左右”的顺序遍历，上图的遍历结果：ABCDEF
中序遍历，即“左根右”的顺序遍历，上图的遍历结果：CBDAEF
后序遍历，即“左右根”的顺序遍历，上图的遍历结果：CDBFEA
好了，废话说完，上代码：
import java.util.Stack;
public class Tree {
public static void main(String[] args) {
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");
Node nodeE = new Node("E");
Node nodeF = new Node("F");
nodeA.leftNode = nodeB; nodeA.rightNode = nodeE;
nodeB.leftNode = nodeC; nodeB.rightNode = nodeD;
nodeE.rightNode = nodeF;
inOrder(nodeA);
preOrder(nodeA);
posOrder(nodeA);
}
static class Node{
String value;
Node leftNode = null;
Node rightNode = null;
public Node(String value) {
this.value = value;
}
}
//中序遍历
public static void inOrder(Node root) {
if(root == null) return;
else {
Stack<Node> stack = new Stack<Tree.Node>();
while(!stack.isEmpty()||root!=null){
//一直遍历到左子树最左下角，沿路保存根节点
while(root!=null){
stack.push(root);
root = root.leftNode;
}
//当root为空时，即已到达左子树最左下角，开始出栈
if(!stack.isEmpty()){
root=stack.pop();
System.out.print(root.value+" ");
root = root.rightNode;
}
}
}
}
//前序遍历
public static void preOrder(Node root) {
if(root == null) return;
else {
Stack<Node> stack = new Stack<Tree.Node>();
while(root!=null||!stack.isEmpty()){
while(root!=null){
System.out.print(root.value+" ");
stack.push(root);
root = root.leftNode;
}
if(!stack.isEmpty()){
root = stack.pop();
root = root.rightNode;
}
}
}
}
//后序遍历
//后序遍历稍有不同，这里我们借用两个stack来实现
public static void posOrder(Node root) {
if(root == null) return;
else {
Stack<Node> stack1 = new Stack<Tree.Node>();
Stack<Node> stack2 = new Stack<Tree.Node>();
stack1.push(root);
while(!stack1.isEmpty()){
Node tempNode = stack1.pop();
stack2.push(tempNode);
if(tempNode.leftNode!=null){
stack1.push(tempNode.leftNode);
}
if(tempNode.rightNode!=null){
stack1.push(tempNode.rightNode);
}
}
while(!stack2.isEmpty()){
System.out.print(stack2.pop().value+" ");
}
}
}
}
```swift
