数据结构6——二叉树（非递归遍历）

之前讲了递归调用二叉树，下面简单的介绍非递归二叉树遍历。

非递归二叉树遍历是采用的栈的方式，将结点分为，根节点，左子树，右子树的顺序分别在不同的时候入栈和出栈。

1：非递归前序遍历（DLR）

 1 /*
 2  * 非递归二叉树遍历方法
 3  */
 4 public class BinTreeNoRecur {
 5     
 6     //非递归的方法实现和前序遍历（DLR）一样的效果,思想是先将一个结点入栈，如果不为空，则直接输出给节点，并且将输出的结点作为当前节点
 7     //然后再将右子树入栈，左子树入栈，右子树是后出来，所以先进栈
 8     public static void preOrderNoRecur(BinTreeNode root){
 9         BinTreeNode curr;
10         LinStack ls=new LinStack();
11         if (ls==null) return;
12         ls.push(root);                                 //首先将栈顶的元素注入栈中
13         while(ls.notEmpty()){                        //当栈不为空的时候开始遍历
14             curr=(BinTreeNode) ls.pop();            //出栈得到栈顶的元素
15             System.out.print(" "+curr.getData());
16             
17             if (curr.getRightChild()!=null)            //如果右孩子节点不为空，则将右孩子结点压入栈中
18                 ls.push(curr.getRightChild());
19             if(curr.getLeftChild()!=null)
20                 ls.push(curr.getLeftChild());        //如果左孩子节点不为空，则将左孩子结点压入栈中
21         }
22     }
23

2:非递归二叉树中序遍历

//非递归实现中序遍历　　　　　　思考一下这个方法为什么错误了？
    public static void inOrderNoRecur(BinTreeNode root){

        LinStack lins=new LinStack();
        if (root==null) return;
        BinTreeNode curr=root;
        lins.push(curr);                            //直接将根部元素压入栈底
        
        while(lins.notEmpty()){                        //判断栈是否为空
            //这里面是while循环，而不是if是因为需要将所有的左子树的结点都遍历完，再遍历右子树
            while (curr.getLeftChild()!=null) {    
                lins.push(curr.getLeftChild());
                curr=curr.getLeftChild();
            }
            curr=(BinTreeNode) lins.pop();
            System.out.print(" "+curr.getData());
            
            if (curr.getRightChild()!=null) {
            curr=curr.getRightChild();
            lins.push(curr);
            }
        }
    }

正确方法：

 1 //非递归实现中序遍历
 2     public static void inOrderNoRecur(BinTreeNode root){
 3 
 4         LinStack lins=new LinStack();
 5         if (root==null) return;
 6         BinTreeNode curr=root;
 7         //判断栈是否为空或者判断堆栈是否为空
 8         while(curr!=null||lins.notEmpty()){                        
 9             //这里面是while循环，而不是if是因为需要将所有的左子树的结点都遍历完，再遍历右子树
10             while (curr!=null) {    
11             //第一次不为空的时候压入的是根结点，之后一直遍历左子树
12                 lins.push(curr);
13                 curr=curr.getLeftChild();
14             }
15             curr=(BinTreeNode) lins.pop();
16             System.out.print(" "+curr.getData());
17             curr=curr.getRightChild();
18         }
19     }

3：后序二叉树的非递归遍历

 1         while(curr!=null||linstack.notEmpty()){
 2             //先进入左子树中
 3             while(curr!=null){
 4                 linstack.push(curr);
 5                 curr=curr.getLeftChild();
 6             }
 7             //获得栈顶的位置，因为在上面的while循环中，先push进去一个结点，在传入下一个结点中
 8             //如此，最后的一个结点一定会没有左子树，那么此时curr指向的是一个空节点。
 9             //因此我们得将当前节点指定为栈的顶节点
10             curr=(BinTreeNode) linstack.getTop();
11             
12             /*如果右结点为空，或者右结点之前遍历过，表明对于一个子树，其左结点已经打印完毕，打印根结点*/  
13             if(curr.getRightChild()==null||curr.getRightChild()==preNode){  
14                curr=(BinTreeNode) linstack.pop(); 
15                System.out.print(" "+curr.getData());
16                preNode = curr;  
17                curr=null;                    
18             }  
19             else{  
20                 curr=curr.getRightChild();
21             }  
22         }