java - 如何将排序的Arraylist转换为BST

Question

我有下面的代码可以使用，如何让这个方法创建一个 BST。我正在使用 Elements.I 正在使用可以执行“T.setRoot()”、“n.getRightChild()”、“n.setLeftChild()”等操作的自定义导入，这应该不难弄清楚。

public static <E> BTree<E> taulukostaPuu(ArrayList<E> L) {

     BTree<E> T = new BTree<E>();
        //TODO
     return T;
 }     

我怎样才能创建一个递归方法来遍历元素的Arraylist并将它们添加到BST中。我想保持这个结构完整。我发现的所有示例都是在数组列表包含整数时使用的，这使得以元素形式实现它们非常困难。 BST 必须是平衡的。

我尝试过以下操作:

private static <E> BTree<E> buildRecursively(ArrayList<E> L,E start,E 
  end,BTree<E> T){
     if (start.compareTo(end) < 0)
         return T;
     E x = L.get((L.size()/2) + (L.size() % 2));
     T.setRoot(new BTreeNode<E>(x)); 
     T.setLeftChild(buildRecursively(L, start, L.get((L.size()/2) + (L.size()  
     %  2)-1)),T);
     T.setRightChild(buildRecursively(L, L.get((L.size()/2) + (L.size() % 
    2)+1), 
    L.get(L.size()-1)),T);

但这显然不起作用。

这就是我目前正在处理的内容:

  public static <E> BTree<E> taulukostaPuu(ArrayList<E> L) {

     BTree<E> T = new BTree<E>();

     E root = L.get((L.size()/2) + (L.size() % 2));
     T.setRoot(new BTreeNode<E>(root));


     return T;
}

不知道从这里去哪里。我应该以某种方式从 x 遍历数组列表以找到 2 个子元素的元素并递归地执行此操作。有什么建议么？

Answer 1

你检查过这个吗click here如果您谈论的是简单的 BST，那么这是理解 BST 的一个良好的开始。