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

Question

1. 说明我正在制作一个使用级别顺序插入的二叉搜索树。Level Order Insertion 的原因是因为我需要制作一个 完整的二叉搜索树。2. 到目前为止我做了什么我有ArrayList这些数字：5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200我插入它们的方式是：该insert方法检查数字是高于还是低于root. 较低表示在 的左侧root，较高表示在 的右侧root。插入到90BST的中间开始，并将其ArrayList插入到Tree. 这现在变成了root。接下来我要做的是将ArrayList分成两部分，左半部分和右半部分ArrayList：5、20、25、50、66、75、8092、95、111、150、166、175、200接下来要做的是我把两半的中间插入到Tree. 现在Tree是 90 root，左边是50，右边是 150。这应该继续，直到没有更多的元素要插入。3. 问题我的问题是这是手动完成的，我希望我的方法本身将其ArrayList分成两半，取两半的中间，将两半各分成两半，所以我们现在有四半，各取中间，将它们插入Tree等等。我试图在 a 中做到这一点for loop，但我不知道如何处理它。我不想手动执行的原因是它应该适用于任何ArrayList尺寸，例如尺寸 3、尺寸 7、尺寸 15 等。这显示了我希望它如何完成：5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200 = 中间是 905, 20, 25, 50, 66, 75, 80 = 中间是 5092, 95, 111, 150, 166, 175, 200 = 中间是 1505, 20, 25 = 中间是 2066, 75, 80 = 中间是 7592, 95, 111 = 中间是 95166, 175, 200 = 中间是 17592, 111 = 中间是 92166, 200 = 中间是 1664. 代码这是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;    }

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[]{});

}