二叉树的多种遍历

import java.util.Stack;

/**
 * 分别使用递归和非递归的方式实现二叉树的先序、中序和后序以及层次遍历
 */
public class BinaryTreeTraversal {
    //先序遍历递归实现
    public void preOrderRecur(Node head){
        if(head==null) return;
        System.out.print(head.value+" ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }
    //中序遍历递归实现
    public void inOrderRevur(Node head){
        if(head==null) return;
        inOrderRevur(head.left);
        System.out.print(head.value+" ");
        inOrderRevur(head.right);
    }
    //后序遍历递归实现
    public void posOrderRevur(Node head){
        if(head==null) return;
        posOrderRevur(head.left);
        posOrderRevur(head.right);
        System.out.print(head.value+" ");
    }
    //先序遍历非递归方式实现
    public void preOrderUnRecur(Node head){
        System.out.print("pre-order: ");
        if(head!=null){
            Stack<Node> stack = new Stack<Node>();
            stack.add(head);//利用栈的方式
            while(!stack.isEmpty()){
                head = stack.pop();//弹出根节点
                System.out.print(head.value+" ");
                if(head.right!=null){
                    stack.push(head.right);//压入右节点
                }
                if(head.left!=null){
                    stack.push(head.left);//压入左节点
                }
            }
        }
        System.out.println();
    }
    //中序遍历非递归方式实现
    public void inOrderUnRecur(Node head){
        System.out.print("in-order: ");
        if(head!=null){
            Stack<Node> stack = new Stack<>();
            while(!stack.isEmpty()||head!=null){
                if(head!=null){
                    stack.push(head);
                    head = head.left;
                }else{
                    head = stack.pop();
                    System.out.print(head.value+" ");
                    head = head.right;
                }
            }
            System.out.println();
        }
    }
    //两个栈实现非递归方式的后序遍历
    public void postOrderUnRecur(Node head){
        System.out.print("pos=order: ");
        if(head!=null){
            Stack<Node> s1 = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s1.push(head);
            while(!s1.isEmpty()){
                head = s1.pop();
                s2.push(head);
                if(head.left!=null){
                    s1.push(head.left);
                }
                if(head.right!=null){
                    s2.push(head.right);
                }
            }
            while(!s2.isEmpty()){
                System.out.print(s2.pop().value+" ");
            }
        }
        System.out.println();
    }
    //使用一个栈实现非递归方式的后序遍历
    public void posOrderUnRecur2(Node h){
        //h代表最近一次弹出并打印的节点，c代表stack的栈顶节点
        System.out.print("pos=order: ");
        if(h!=null){
            Stack<Node> stack = new Stack<>();
            stack.push(h);
            Node c = null;
            while(!stack.isEmpty()){
                c = stack.peek();
                if(c.left!=null&&h!=c.left&&h.right!=c.right){
                    stack.push(c.left);//说明c的左右子树还没打印完毕，此时c左节点可以入栈
                }else if(c.right!=null&&h!=c.right){
                    stack.push(c.right);//说明c的右子树还没有处理过，次数c的右节点入栈
                }else{
                    //左右子树都已遍历完毕，弹出当前节点并打印
                    System.out.print(stack.pop().value+" ");
                    h = c;
                }
            }
        }
        System.out.println();
    }
    //层次遍历二叉树(广度优先遍历)
    public void levelOrderUnRecur(Node h){
        System.out.print("pos=order: ");
        LinkedList<Node> queue = new LinkedList<>();
        Node p;
        queue.push(h);
        while(!queue.isEmpty()){
            p = queue.removeFirst();
            System.out.println(p.value+" ");
            if(p.left!=null)
                queue.addLast(p.left);
            if(p.right!=null)
                queue.addLast(p.right);
        }
        System.out.println();
    }
    //深度优先遍历
    public void depthTraversal(Node head){
        Stack<Node> stack = new Stack<>();
        stack.push(head);
        while(!stack.isEmpty()){
            Node temp = stack.pop();
            System.out.print(temp.value+" ");
            if(temp.right!=null) stack.push(head.right);
            if(temp.left!=null) stack.push(head.left);
        }
    }
}