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 - 2for(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);}//随机生成我们待查找的数字xint 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 falseif(null == parentNode) {return false;}//此时说明找到数字x了,直接return trueif(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;}
}