如何将排序的数组列表转换为BST

Question

我有以下代码可以使用，如何使此方法创建BST。我正在使用自定义导入，可以执行"T.setRoot(("，"n.getRightChild(("，"n.setLeftChild(("等，这应该不难弄清楚。

public static <E> BTree<E> taulukostaPuu(ArrayList<E> L) {
BTree<E> T = new BTree<E>();
//TODO
return T;
}     

我怎样才能制作一个递归方法来遍历元素的数组列表并将它们添加到 BST 中。我想保持这个结构完好无损。我找到的所有示例都是在 arraylist 包含整数时使用的，这使得以元素形式实现它们非常困难。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

您是否检查过此单击此处，这是了解BST的良好开端，以防您谈论简单的BST。