Q：实现二叉树的前序中序和后序遍历，非递归。
A：前序和中序遍历中，当遇到null节点时，就从栈中出栈一个元素，
root=stack.pop();root=root.right。
但是后序遍历中，遇到null节点时，只有栈顶元素的右子树为空或者已经访问过，才能将栈顶元素出栈，root=stack.pop();prev=root;root=null;否则root=stack.peek().right;
双栈法后序遍历中，output栈中按照当前，右子树，左子树的顺序保存节点。
//非递归前序遍历
public static void preOrder(Node node)
{
Node root=node;
Deque<Node> stack=new ArrayDeque<>();
while (root!=null||stack.size()>0)
{
while (root!=null)
{
stack.push(root);
//节点入栈时就输出节点的信息
System.out.print(root.data);
//入栈的时候转移为左子节点
root=root.left;
}
if (stack.size()>0)
{
root=stack.pop();
//出栈的时候转移为右子节点
root=root.right;
}
}
}
//非递归中序遍历
public static void midOrder(Node node)
{
Node root=node;
Deque<Node> stack=new ArrayDeque<>();
while (root!=null||stack.size()>0)
{
if (root!=null)
{
stack.push(root);
//入栈的时候转移为左子节点
root=root.left;
}
else
{
root=stack.pop();
//节点出栈时才输出其信息
System.out.print(root.data);
//出栈的时候转以为右子节点
root=root.right;
}
}
}
//非递归后序遍历
public static void postOrder(Node node)
{
Node root=node;
Node prev=node;
Deque<Node> stack=new ArrayDeque<>();
while (root!=null||stack.size()>0)
{
while (root!=null)
{
stack.push(root);
//入栈的时候转移为左子节点
root=root.left;
}
if (stack.size()>0)
{
Node temp=stack.peek().right;//important
//如果栈顶元素没有右子树或者右子树已经输出过
//那么栈顶元素没有保存的必要，直接弹出栈顶元素
if (temp==null||temp==prev)
{
root=stack.pop();
//节点出栈时才输出其信息
System.out.print(root.data);
prev=root;
root=null;
}
//否则右子树没有被访问过，需要访问右子树
else
root=temp;
}
}
}
//双栈法后序遍历
public static void doubleStackPostOrder(Node node)
{
Node root=node;
Deque<Node> stack=new ArrayDeque<>();
Deque<Node> output=new ArrayDeque<>();
while (root!=null||stack.size()>0)
{
while (root!=null)
{
stack.push(root);
//output栈按照当前，右子树，左子树的顺序保存节点
output.push(root);
//入栈的时候转移为右子节点
root=root.right;
}
if (stack.size()>0)
{
root=stack.pop();
//出栈的时候转移为左子节点
root=root.left;
}
}
while (output.size()>0)
{
root=output.pop();
//output栈输出节点的信息
System.out.print(root.data);
}
}
这里贴上链接：http://m.blog.csdn.net/maoshaofeng8/article/details/54645941
https://zm10.sm-tc.cn/?src=l4uLj8XQ0J2TkJjRnIybkdGRmovQnJOekqCck56S0J6Ni5ack5rQm5qLnpaTjNDJx8vKzMbG&uid=aab0ff0df7f137e85a695755587073e7&hid=a1c2d0064512b394a31c7daa771b6741&pos=3&cid=9&time=1506676695782&from=click&restype=1&pagetype=0000000002000408&bu=web&query=%E4%BA%8C%E5%8F%89%E6%A0%91%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E9%9D%9E%E9%80%92%E5%BD%92+Java&mode=&v=1&uc_param_str=dnntnwvepffrgibijbprsvdsdichei
