二叉树基础之前序遍历、中序遍历、后序遍历的递归和非递归实现

转载请注明原文地址：http://www.cnblogs.com/ygj0930/p/6604347.html 

一：树的结点

    一般默认树的结点由：结点值、左儿子、右儿子，构造函数组成。

class TreeNode{
    int value;
    TreeNode  left;
    TreeNode  right;
    public TreeNode(int i){
    this.value=i;
    }
}

二：二叉树的遍历实现——递归和非递归

    1：递归实现==按照遍历方式（前、中、后）对左、根、右的访问顺序去 打印结点值、递归左儿子、递归右儿子

    public void preorder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.println(root.val);    //根
        preorder(root.left,pre);//左
        preorder(root.right,pre);//右
    }

    public void inorder(TreeNode root){
        if(root==null){
            return;
        }
        inorder(root.left,in); /左
        System.out.println(root.val);//根
        inorder(root.right,in);//右
    }

    public void postorder(TreeNode root){
        if(root==null){
            return;
        }
        postorder(root.left,post);//左
        postorder(root.right,post);//右
        System.out.println(root.val);//根
    }

    2：非递归实现==使用 栈 来控制结点的处理顺序

    前序遍历==利用栈的倒序输出特性，每次弹出当前结点时按“先右后左”的顺序把当前结点的儿子结点入栈。

 public void preorder(TreeNode root,ArrayList<Integer> pre){
        if(root==null){
            return;
        }
        Stack node=new Stack<TreeNode>();
        TreeNode curr=null;
        node.push(root);
        while(!node.isEmpty()){
            //处理根结点
            curr=node.pop();
            pre.add(curr.val);
            //先把右儿子入栈
            if(root.right!=null){
                node.push(root.right);
            }
            //后把左儿子入栈，下一循环时就是左儿子先处理
            if(root.left!=null){
                node.push(root.left);
            }
        }
    }

    中序遍历==curr指向根，把根入栈：令curr指向左儿子，如果非空则入栈，重复这步；//循环遍历左子树

                                                  如果curr为空，则弹出栈顶元素；//处理子树的根

                                                  令curr指向弹出元素的右儿子，如果非空则入栈；//处理右儿子。然后回到第一步时处理右儿子的左子树

                                                  重复以上三步直到栈为空。

    public void inorder(TreeNode root,ArrayList<Integer> in){
        if(root==null){
            return;
        }
        Stack<TreeNode> node=new Stack<TreeNode>();
        TreeNode curr=root;
        //先把根入栈
        node.push(root);
        while(!node.isEmpty()){
            //循环处理左子树，让左子树入栈
            while(curr!=null){
                curr=curr.left;
                if(curr!=null){
                node.push(curr);
                }
            }
            //左子树入栈完毕，开始处理栈中结点。由于是 按照 根—左 的顺序入栈的，所以处理的时候是 左——根
            curr=(TreeNode)node.pop();
            in.add(curr.val);
            
            //元素弹出时说明前面的它的左子树已经处理完了，并且元素自身作为根也处理了。此时看这个根有没有右儿子，有则入栈处理 右。回到第一步，右子树的处理同样是：左、根、右
            curr=curr.right;
            if(curr!=null){
                node.push(curr);
            }
        }
    }

    

    后序遍历==使用两个栈，root入栈1：S1弹出栈顶，curr指向S1弹出的元素，把curr入S2，同时令curr的左右儿子依次入S1；

                                                    重复上面，直到S1为空时，树遍历完毕，依次弹出S2则为后序遍历。

                    由于栈1结点的儿子是按照“左右”顺序入栈的，所以出栈再入栈2时就是按照“根右左”的顺序，所以栈2弹出时就是“左右根”后序遍历了。

    public void postorder(TreeNode root,ArrayList<Integer> post){
        if(root==null){
            return;
        }
        Stack<TreeNode> s1=new Stack<TreeNode>();
        Stack<TreeNode> s2=new Stack<TreeNode>();
        s1.push(root);
        TreeNode curr=null;
        //S1弹出栈顶，curr指向S1弹出的元素，把curr入S2，同时令curr的左右儿子依次入S1
        while(!s1.isEmpty()){
            curr=(TreeNode)s1.pop();
            s2.push(curr);
            if(curr.left!=null){
                s1.push(curr.left);
            }
            if(curr.right!=null){
                s1.push(curr.right);
            }
        }
        //依次弹出S2则为后序遍历
        while(!s2.isEmpty()){
            curr=(TreeNode)s2.pop();
            post.add(curr.val);
        }