本文共 3147 字，大约阅读时间需要 10 分钟。

二叉树的非递归（全部用栈解决）前序，中序，后序遍历实现

先上代码再解释(注意我为什么把中序放在最前面，因为我的后面两个都是基于中序来的，所以先把中序搞懂了，其他的就简单了)

1.中序

class TreeNode {
        int val;    TreeNode left;      TreeNode right;  TreeNode(int x) {
    val = x; }  }  //使用栈来解决树的中序遍历public class Test{
      Stack
   
     stack =  new Stack
    
     ();    List
     
       inorderTraversal(TreeNode root) {
           List
      
        list = new ArrayList
       
        ();        TreeNode current = root;//current指向当前的所遍历的节点        while(current!=null||!stack.isEmpty())//三种方式都是这个出口        {
               while(current!=null)            {
                   stack.push(current);                current=current.left;//一直求左边的节点，直到最左边为止            }            current = stack.pop();            list.add(current.val);            current=current.right;        }      return  list;    }
       
      
     
    
   

下面是个草图，仅供参考

2.前序(在中序基础上只改一行代码)

class TreeNode {
        int val;    TreeNode left;      TreeNode right;  TreeNode(int x) {
    val = x; }  }  //使用栈来解决二叉树的前序遍历public class Test{
       Stack
   
     stack = new Stack
    
     ();    List
     
       firstTraversal(TreeNode root) {
           List
      
        list = new ArrayList
       
        ();        TreeNode current = root;        while(current!=null||!stack.isEmpty())        {
               while(current!=null)            {
                   list.add(current.val);//因为是先根节点，而根节点先入栈，所以提前把它放入                stack.push(current);                current=current.left;            }            current = stack.pop();            current=current.right;        }      return  list;    }
       
      
     
    
   

3.后序（这个比较复杂了，改的比较多不过大同小异）

class TreeNode {
        int val;    TreeNode left;      TreeNode right;  TreeNode(int x) {
    val = x; }  }  //使用栈来解决二叉树的后序遍历public class Test{
       Stack
   
     stack = new Stack
    
     ();    List
     
       firstTraversal(TreeNode root) {
           List
      
        list = new ArrayList
       
        ();        TreeNode current = root;        TreeNode temp;        while(current!=null||!stack.isEmpty())        {
               while(current!=null)            {
                   stack.push(current);                temp = current;                current=current.left;                temp.left=null;//这么做是因为是后序遍历，所以把根节点放入栈后，把孩子节点都放掉，这样就为后面的取节点提供了依据（任何一个父节点都是子节点取完后才可以取）            }            current = stack.peek();            //接下来分两步情况，取右节点还是抛出节点            if(current.left==null&&current.right==null)            {
                   while(stack.peek().left==null&&stack.peek().right==null)                {
                       Integer i= stack.pop().val;                    list.add(i);                    System.out.println(i);                    if(stack.isEmpty())                        return  list;                    current=stack.peek();                }                temp=current;                current=current.right;                temp.right=null;            }            else            {
                   temp=current;                current=current.right;                temp.right=null;            }        }      return  list;    }
       
      
     
    
   

谢谢！

转载地址：http://eilzi.baihongyu.com/