import java.util.LinkedList;
import java.util.Queue;

class Node{
    public int data;
    public Node left;
    public Node right;
    public Node(int data){
        this.data=http://www.mamicode.com/data;
        this.left=null;
        this.right=null;
    }
}

public class BinaryTree {
    private Node root;
    public BinaryTree(){
        root=null;
    }
    /*
    * 插入到排序二叉树
    * */
    public void insert(int data){
        Node newNode=new Node(data);
        if(root==null){
            root=newNode;
            return;
        }
        Node node=root;
        Node parent;
        while(true){
            parent=node;
            if(data<node.data){
                node=node.left;
                if(node==null){
                    parent.left=newNode;
                    return;
                }
            }else{
                node=node.right;
                if(node==null){
                    parent.right=newNode;
                    return;
                }
            }
        }
    }
    /*
    * 将数值输入构建二叉树
    * */
    public void buildTree(int[] data){
        for(int i=0;i<data.length;i++){
            insert(data[i]);
        }
    }
    /*
    * 先序遍历
    * */
    public void preOrder(){
        preOrder(root);
    }
    public void preOrder(Node node){
        if(node==null) return;
        System.out.print(node.data+" ");
        preOrder(node.left);
        preOrder(node.right);
    }

    /*
    * 中序遍历
    * */
    public void inOrder(){
        inOrder(root);
    }
    public void inOrder(Node node){
        if(node==null) return;
        preOrder(node.left);
        System.out.print(node.data+" ");
        preOrder(node.right);
    }

    /*
    * 后序遍历
    * */
    public void postOrder(){
        postOrder(root);
    }
    public void postOrder(Node node){
        if(node==null) return;
        preOrder(node.left);
        preOrder(node.right);
        System.out.print(node.data+" ");
    }
    /*
    * 层序遍历
    * */
    public void layerTranverse(){
        Node node = root;
        Queue<Node> queque=new LinkedList<Node>();
        queque.add(root);
        while(!queque.isEmpty()){
            node=queque.poll();
            System.out.print(node.data+" ");
            if(node.left!=null) queque.add(node.left);
            if(node.right!=null) queque.add(node.right);
        }
    }

    public static void main(String[] args) {
        BinaryTree bitree=new BinaryTree();
        int[] data=http://www.mamicode.com/{2,8,7,4,9,3,1,6,7,5};
        bitree.buildTree(data);
        System.out.print("二叉树的先序遍历：");
        bitree.preOrder();
        System.out.println();
        System.out.print("二叉树的中序遍历：");
        bitree.inOrder();
        System.out.println();
        System.out.print("二叉树的后序遍历：");
        bitree.postOrder();
        System.out.println();
        System.out.print("二叉树的层序遍历：");
        bitree.layerTranverse();
        System.out.println();
    }
}