生成二叉搜索树

Question

当我有一个包含100个元素的数组列表(如{3,2,6,7,...,99} )时，如何创建BST

Answer 1

我相信TreeSet是一个二叉树的实现。因为整数有一个自然的顺序，你可以简单地循环你的整数数组，并将它们添加到一个TreeSet<Integer>中。

还要注意的是，有一个方法Arrays.binarySearch可以在排序数组中执行二进制搜索。

int[] someInts = {3,2,6,7, /*...,*/ 99};

// use a TreeSet
TreeSet<Integer> ints = new TreeSet<Integer>();
for (int i : someInts)
    ints.add(i);

System.out.println(ints.contains(2)); // true      
System.out.println(ints.contains(5)); // false

// or sort the array and use Arrays.binarySearch
Arrays.sort(someInts);
System.out.println(Arrays.binarySearch(someInts, 2) >= 0); // true
System.out.println(Arrays.binarySearch(someInts, 5) >= 0); // false

Answer 2

对此数组进行第一次排序，然后使用BST

编辑

1- BST在排序后的数组上工作。

2-使用这个伪代码See Here

Answer 3

除非你想自己实现所有的东西(在这种情况下，你可能想要检查here)，否则你应该看看Collections.binarySearch。

2：http://download.oracle.com/javase/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List