每次循环拆分 ArrayList 并将中间值添加到二叉搜索树中

Question

1.说明

我正在制作一个使用水平顺序插入的二叉搜索树。水平订单插入的原因是因为我需要做一个完成二叉搜索树。

2。到目前为止我做了什么

我有一个 ArrayList 这些号码：

5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200

我插入的方式是：

insert 方法检查数字是否高于或低于 root。较低表示在 root 的左侧，较高表示在 root.
插入 BST 是从 ArrayList 的中间开始，即 90，然后将其插入 Tree。现在变成 root.
接下来我要做的是将 ArrayList 分成两部分，ArrayList 的左半部分和右半部分：

5, 20, 25, 50, 66, 75, 80

92, 95, 111, 150, 166, 175, 200

接下来要做的是我将中间的两半插入 Tree。 Tree 现在在 root 处为 90，在左侧为 50，在右侧为 150。
这应该继续，直到没有更多元素可插入。

3。问题

我的问题是这是手动完成的，我希望我的方法本身将 ArrayList 分成两半，取两半的中间，将两半分成两半每个，所以我们现在有四半，取每个的中间，将它们插入 Tree 等等。
我曾尝试在 for loop 中执行此操作，但我不知道如何处理它。
我不想手动操作的原因是它应该适用于任何 ArrayList 尺码，例如 3 号、7 号、15 号等

这显示了我希望它如何完成：

5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200 = mid is 90

5, 20, 25, 50, 66, 75, 80 = mid is 50

92, 95, 111, 150, 166, 175, 200 = mid is 150

5, 20, 25 = mid is 20

66, 75, 80 = mid is 75

92, 95, 111 = mid is 95

166, 175, 200 = mid is 175

92, 111 = mid is 92

166, 200 = mid is 166

4.代码

这是 insert 方法，它检查值是低于还是高于 root。

private BinaryNode<AnyType> insert( AnyType x, BinaryNode<AnyType> t )
    {
        if( t == null )
            return new BinaryNode<>( x, null, null);
        
        int compareResult = x.compareTo( t.element );

            if (compareResult < 0)
                t.left = insert(x, t.left);
            else if (compareResult > 0)
                t.right = insert(x, t.right);
            else
                ;  // Duplicate; do nothing

        return t;
    }

这是我手动将 ArrayList 分成两半的方法。

  public void createCompleteBinarySearchTree(ArrayList<Integer> list){

    Integer root = list.get(0) + (list.get(list.size()-1) - list.get(0)) / 2;
    Integer endOfMainArray = list.get(list.size() - 1);

    insert((AnyType) root);

    for(int i = 0; i <= list.size() -1; i++) {
        List<Integer> firstHalf = (List<Integer>) list.subList(0, root - 1);
        List<Integer> secondHalf = (List<Integer>) list.subList(root, endOfMainArray);

        Integer midOfFirstHalf = firstHalf.get(0) + (firstHalf.get(firstHalf.size() - 1) - firstHalf.get(0)) / 2;
        Integer midOfSecondHalf = secondHalf.get(0) + (secondHalf.get(secondHalf.size() - 1) - secondHalf.get(0)) / 2;


        insert((AnyType) midOfFirstHalf);

        insert((AnyType) midOfSecondHalf);

        insert((AnyType) firstHalf.get(0));

        insert((AnyType) firstHalf.get(2));

        insert((AnyType) secondHalf.get(0));

        insert((AnyType) secondHalf.get(2));
    }
}

这是我插入的 ArrayList。

List<AnyType> numbers = new ArrayList<AnyType>((Collection<? extends AnyType>)
        Arrays.asList(5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200));

Answer 1

您正在使用递归结构，因此递归函数通常可以使事情变得简单。

class BST<T> {
    T value;
    BST<T> left;
    BST<T> right;

    public BST(T[] contents) {
        insert(contents);
    }

    private void insert(T[] contents) {
        if (contents.length > 0) {
            if (contents.length == 1) {
                value = contents[0];
            } else {
                // Split it.
                int center = contents.length / 2;
                // Take the center value as my value
                value = contents[center];
                if (center > 0) {
                    // There is more to the left so put it in my `left` branch.
                    left = new BST<>(Arrays.copyOfRange(contents, 0, center));
                }
                if (center < contents.length) {
                    // ditto to the right.
                    right = new BST<>(Arrays.copyOfRange(contents, center + 1, contents.length));
                }
            }
        }
    }

    public int size() {
        return (left != null ? left.size() : 0)
                + (value != null ? 1 : 0)
                + (right != null ? right.size() : 0);
    }

    @Override
    public String toString() {
        return (left != null ? left.toString() + "," : "")
                + (value != null ? value : "")
                + (right != null ? "," + right.toString() : "");
    }
}

private void test(Integer[] integers) {
    System.out.println("Array = " + Arrays.toString(integers) + " length " + integers.length);
    BST<Integer> bst = new BST<>(integers);
    System.out.println("BST = " + bst.toString() + " length " + bst.size());
}

private void test() {
    test(new Integer[]{5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200});
    test(new Integer[]{5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175});
    test(new Integer[]{90});
    test(new Integer[]{});
}

每次循环拆分 ArrayList 并将中间值添加到二叉搜索树中

Split ArrayList each loop and add the middle value to the Binary Search Tree

java

binary-tree

arraylist

binary-search-tree