完整的BST部分花了一些时间来弄清实际内容。
您的要求还要求插入订单级别。我不能说这确实可以
“插入”，但是它可以按顺序构建BST。
输入列表必须首先排序。
通过建立根目录并将其添加
到BST，然后将左侧内容拆分为左右列表，将
它们添加到列表列表中，然后处理列表列表，可以完成顺序构建。每轮
拆分和添加到列表列表都是一个插入级别。
如所注意到的，完整部分更加困难。处理该问题的方法是
与普通的平衡树不同地计算列表的根。在
正常的平衡树中，根索引为length / 2。为了使BST完整
，必须偏移根索引，以便通常会出现在
根右侧的节点出现在根左侧。由于
只要计算适用于任何长度的名单，然后每个分割子列表中
正确建立。
据我所知，通过增加
长度上每个附加元素的偏移量直到达到
水平宽度的1/2来计算偏移量。因此，高度为4的BST在最低级别具有8个元素。的列表
大小8，9，10，… 15创建BST用的4高度对于这些列表的根
索引的列表然后4，5，6，7，7,7，7,7。
似乎可以工作。
public class Node<T extends Comparable<T>> { protected Node<T> left; protected Node<T> right; protected T data; }public class BTree<T extends Comparable<T>> { private Node<T> root = new Node<>(); public void addData(T data) { Node<T> parent = root; while (parent.data != null ) { if ( data.compareTo( parent.data ) > 0 ) { if ( parent.right == null ) parent.right = new Node<>(); parent = parent.right; } else { if ( parent.left == null ) parent.left = new Node<>(); parent = parent.left; } } parent.data = data; }}private void run() { for ( int i = 2; i < 65; ++i ) { List<Integer> intList = IntStream.range(1, i).boxed().collect(Collectors.toList()); BTree<Integer> bTree = new BTree<>(); List<List<Integer>> splitLists = new ArrayList<>(); splitLists.add(intList); while (splitLists.size() > 0 ) { List<List<Integer>> tSplitLists = new ArrayList<>(); for ( List<Integer> tIntList: splitLists) { int length = tIntList.size(); // compute starting point int mid = calcMid(length); // length/2 ; //+ calcOffset(length); bTree.addData(tIntList.get(mid)); if ( mid - 0 > 0) tSplitLists.add(tIntList.subList(0, mid)); if ( length - (mid+1) > 0) tSplitLists.add(tIntList.subList(mid+1, length)); } splitLists = tSplitLists; } bTree.printNode(); }}private int calcMid(int length) { if ( length <= 4 ) return length / 2; int levelSize = 1; int total = 1; while ( total < length ) { levelSize *= 2; total += levelSize; } int excess = length - (total - levelSize); int minMid = (total - levelSize + 1) / 2; if ( excess <= levelSize / 2 ) { return minMid + (excess - 1); } else { int midExcess = levelSize/2; return minMid + (midExcess - 1); }}请参阅如何打印二叉树图？有关打印二叉树的代码。
PS>我相信您可以通过清除和复制列表而不是每次都创建新列表来使它更好。
编辑：你去获取
printNode上面引用的代码吗？
1 2 / 1 2 / 1 3 3 / / 2 4 / 1
等等 …
