采用[二叉排序树]实现：判断给定的一个数字x是否在指定的一个无序的数字序列中存在

package tree.binarytree;

import java.util.Random;

/**
 * Created by Lanxiaowei
 * Craated on 2016/12/12 17:14
 * 判断给定的一个数字x是否在指定的一个无序的数字序列中存在
 * 采用二叉排序树方式实现
 */
public class TestBinarySortTree {

    public static void main(String[] args) {
        //测试100次
        test(100);
    }

    /**
     * 测试方法
     * @param times    测试的总次数
     */
    public static void test(int times) {
        if(times <= 0) {
            throw new IllegalArgumentException("The number [times] MUST be greater than zero.");
        }

        while(times-- > 0) {
            System.out.println("/**********************华丽的分割线 begin************************/");
            int min = 1;
            int max = 100;
            //先随机生成一个随机数作为二叉树的父节点
            int parentVal = random(min,max);
            //打印生成的parent节点数值
            System.out.println("Parent:" + parentVal);
            //创建二叉树的父节点
            BinarySortTreeNode parentNode = new BinarySortTreeNode(parentVal);
            //假设我们的无序数字序列的长度n=10,这里我们随机生成无序数字序列里的每个数字,然后插入二叉树结构中
            int n = 10;
            //用于存储每个子节点的数值
            int num = 0;
            //这里之所以是n - 2,是因为我们已经生成了父节点,剩下我们只需要生成n - 1个子节点,
            //而i是从零开始的,因此这里是n - 2
            for(int i=0; i < n - 2; i++) {
                //随机生成每个子节点的数值
                num = random(min,max);
                System.out.println("Child:" + num);
                //创建每个子节点
                BinarySortTreeNode child = new BinarySortTreeNode(num);
                //往二叉排序树里插入子节点
                parentNode.insert(parentNode,child);
            }

            //随机生成我们待查找的数字x
            int x = random(min,max);
            //查找数字x是否在二叉树中存在
            boolean exists = parentNode.search(parentNode,x);
            System.out.println("Number x[" + x + "] exists in binary sorted tree?:" + exists);
            System.out.println("/**********************华丽的分割线 end**************************/\n");
        }
    }

    /**
     * 二叉排序树的每个节点
     */
    public static class BinarySortTreeNode {
        //左子节点
        private BinarySortTreeNode left;
        //右子节点
        private BinarySortTreeNode right;
        /**节点上的值*/
        private int val;

        public BinarySortTreeNode() {}

        public BinarySortTreeNode(int val) {
            this.val = val;
        }

        /**
         * 往指定的父节点上插入一个子节点
         * @param parentNode    父节点
         * @param newNode       待插入的节点
         * @return
         */
        public boolean insert(BinarySortTreeNode parentNode, BinarySortTreeNode newNode) {
            if(null == parentNode) {
                throw new IllegalArgumentException("Parent Node MUST be specified.");
            }
            //若待插入的节点数值大于等于父节点,则待插入的newNode此时应该在右边
            if(parentNode.val <= newNode.val) {
                //如果父节点此刻的右树为空,那么就将待插入的newNode作为父节点右树的父节点
                if(parentNode.right == null) {
                    parentNode.right = newNode;
                    return true;
                } else {
                    //如果父节点的右树不为空,那么就插入到右树的父节点下
                    return insert(parentNode.right, newNode);
                }
            }
            //若待插入的节点数值大于等于父节点,则待插入的newNode此时应该在左边
            if(parentNode.val > newNode.val) {
                //如果父节点此刻的左树为空,那么就将待插入的newNode作为父节点左树的父节点
                if(parentNode.left == null) {
                    parentNode.left = newNode;
                    return true;
                } else {
                    //如果父节点的左树不为空,那么就插入到左树的父节点下
                    return insert(parentNode.left, newNode);
                }
            }
            return false;
        }

        /**
         * 在指定的父节点为parentNode的二叉树下查找是否存在一个数字x
         * @param parentNode  二叉树的父节点
         * @param x           待查找的数字x
         * @return
         */
        public boolean search(BinarySortTreeNode parentNode, int x) {
            //如果二叉树为null,直接return false
            if(null == parentNode) {
                return false;
            }
            //此时说明找到数字x了,直接return true
            if(parentNode.val == x) {
                return true;
            }
            //此时应该在右子树中查找
            if(parentNode.val < x) {
                return search(parentNode.right,x);
            }
            //此时应该在左子树中查找
            if(parentNode.val > x) {
                return search(parentNode.left,x);
            }
            return false;
        }
    }

    /**
     * 生成[min,max)区间内的随机数
     * @param min
     * @param max
     * @return
     */
    public static int random(int min,int max) {
        Random random = new Random();
        return random.nextInt(max)%(max - min + 1) + min;
    }
}