public class BinarySearch {
    /**
     * 二分查找
     * @param data
     * @return
     */
    public int binarySearch(long[] data,long n) {
        //左右 端点
        int left =0;
        int right =data.length-1;
        //中间元素
        int mid=-1;
        while(left<right){  // 有两种情况   1.left = right   2.  left>right  错位
            //防绕死代码
            if(mid==(left+right)/2)break;
            //找中间 元素序号
            mid =(left+right)/2;
            if(data[mid]<n){   //说明在 mid右边  这个时候左端点右扩
                left=mid;
            }else if(data[mid]>n){//说明在 mid左边  这个时候右端点右扩
                right=mid;
            }
        }
        //防止发生错位
        if(data[right]==n){
            return right;
        }else if(data[left]==n){
            return left;
        }else if(data[mid]==n){
            return mid;
        }
        return -1;
    }
    public static void main(String[] args) {
        BinarySearch bs=new BinarySearch();
        long[] data=http://www.mamicode.com/{1,3,5,7,9};
        System.out.println(bs.binarySearch(data, 3));
        System.out.println(bs.binarySearch(data,6));

    }
}

public class Node {

    //左右节点
    Node right =null;
    Node left =null;
    
    //数据存放
    long data =http://www.mamicode.com/Long.MAX_VALUE;
    public Node(Node right, Node left, long data) {
        super();
        this.right = right;
        this.left = left;
        this.data =http://www.mamicode.com/ data;
    }
    public Node(long data) {
        this.data=http://www.mamicode.com/data;
    }
    public Node() {
    }
}

public class BinarySortedTree {
    // 根节点
    Node root = null;

    public boolean add(long data) {
        // 包装一下
        Node n = new Node(data);
        // 判断根节点
        if (root == null)
            root = n;
        else {
            // 当前节点
            Node current = root;
            // 保存父节点
            Node parent = current;

            while (current != null) {
                parent = current;
                if (data > current.data) {
                    // 向左子树查找空位
                    current = current.left;
                } else {
                    // 向右子树查找空位
                    current = current.right;
                }
            }

            // parent不知道 current最后拿的是左子树还是右子树
            if (parent.data < data) {// 说明当时走了左子树
                parent.left = n;
            } else if (parent.data > data) {// 说明当时走了右子树
                parent.right = n;
            }
        }

        return true;
    }


    /**
     *前序遍历
     * 
     * 用迭代的方式 遍历 左 中右
     */
    public void indexNum1(Node temp) {
        //因为 输出根节点总是在 输出 其他节点之前   然后其他节点当做子树根节点遍历 
        System.out.println(temp.data);
        //先走左
        if(temp.left!=null){
            indexNum2(temp.left);
        }
        //再走右子树
        if(temp.right!=null){
            indexNum2(temp.right);
        }
        return ;
        
    }
    
    /**
     *中序遍历
     */
    public void indexNum2(Node temp) {
        if(temp.left!=null){
            indexNum2(temp.left);
        }
        //左子树走到头运行这个 
        System.out.println(temp.data);
        //再走右子树
        if(temp.right!=null){
            indexNum2(temp.right);
        }
        return ;
        
    }
    
    
    
    /**
     *后序遍历
     * 
     * 用迭代的方式 遍历 左 中右
     */
    public void indexNum3(Node temp) {
        if(temp.left!=null){
            indexNum3(temp.left);
        }
        //再走右子树
        if(temp.right!=null){
            indexNum3(temp.right);
        }
        System.out.println(temp.data);
        return ;
        
    }

    public static void main(String[] args) {
        BinarySortedTree bst=new BinarySortedTree();
        bst.add(10);
        bst.add(2);
        bst.add(3);
        bst.add(5);
        
        bst.indexNum3(bst.root);
        
    }

}