二叉树遍历非递归实现

二叉树的遍历

关于二叉树遍历，先序，中序，后序其实都是很简单了。 二叉树一般定义：

public class Node{ public int value; public Node left; public Node right; public Node(int val){ this.val=val; } }

递归实现

先序遍历

public void preOrder(Node tree){ if(tree==null) return; System.out.println(tree.val); preOrder(tree.left); preOrder(tree.right); }

中序，后序仅仅是语句的交换。非常简单，不给出了。

非递归实现

所有递归实现的算法，都可用非递归实现： 思路： 一般将递归转为非递归，不是利用循环就是利用栈。 我们可以自己申请栈来实现： 步骤如下： 1. 申请一个新的栈，将头节点压入栈 2. 从栈中弹出栈顶节点，记为cur，然后打印cur节点的值，再将节点cur的右孩子压入stack，最后压入left child 3. 不断重复步骤2. 直到栈空，全部过程结束

重要的技巧 或者思想：

弹出一个结点的时候，如果它有孩子的话! 要压入它的左右孩子节点！ 没有就直接弹出

代码：

public void preOrderRecur(Node head){ if(head!=null){ Stack<Node> stack=new Stack<Node>(); stack.push(head); //add也可以，但add是ArrayList或者说List类的方法 while(!stack.empty()){ head=stack.pop(); System.out.println(head.val); if(head.right!=null){ stack.push(head.right); } if(head.left!=null){ stack.push(head.left); } } } }

这种弹出父结点然后就压入它的左右子节点的做法是最经常用到的技巧！ !

中序遍历的非递归

仍然是申请一个栈，同时cur=head先把cur节点压入栈，对以cur为头节点的整颗左子树来说，依次把 左边界压入栈中，不停令cur=cur.left;,重复步骤2，直到cur为空， 此时弹出一个节点，记为node.打印node的值，并且让cur=node.right 然后继续重复步骤2直到整个stack为空！ 本质上就是遍历最左边的子树后，每次遇到cur为空就弹出一个，其实它为空，说明该节点是最左边的节点，然后把它赋给cur=node.right 如果node是叶节点就肯定没了，如果是普通节点就肯定有node.right, 当然我们是先弹出了这个node，再去压入它的右节点。 public void inOrderUncur(Node head){ if(head!=null) return; Stack<Node> stack=new Stack<Node>(); Node cur=head; while(!stack.empty()||head!=null){ if(head!null){ stack.push(head); head=head.left; }else{ head=stack.pop(); //此时head已经为空了，弹栈 System.out.println(head.val); head=head.right;//如果head.right为null那么一样会继续pop直到这个head不是null，即它的右节点存在了！ } } }

总结这个方法： push到left为空，pop到right不为空！

后序遍历

直观的想法： 使用两个栈实现。 压入head节点 第一个栈负责依次 弹出父节点 ，然后压入 左子节点 由右子节点 注意是先左后右的压入，其实因为我们用了第二个栈 弹出的节点都压入第二个栈！ 所以我们要保证第二个栈弹出的顺序是 后序遍历的顺序，所以按照左先右后的压入第一个栈，那么弹出第二个栈的时候就肯定是左边先出，右边后出！ 最后我们只需要依次弹出打印右边的即可

public void postOrderUnRecur(Node head){ if(head!=null){ Stack<Node> s1=new Stack<Node>(); Stack<Node> s2=new Stack<Node>(); s1.push(head); while(!s1.empty()){ head=s1.pop();//update s2.push(head); if(head.left!=null){ s1.push(head.left); } if(head.right!=null){ s2.push(head.right); } } while(!s2.empty()){ System.out.println(s2.pop().val+" "); } } }

还有一种方法，使用一个栈实现后序非递归 它的思想是多设置两个变量h和c 。h代表最近一次弹出并打印的节点 c代表栈顶节点。 然后分3种情况处理。这个算法后续再讨论