拆分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、80

92、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 = 中间是 90

---

5, 20, 25, 50, 66, 75, 80 = 中间是 50

92, 95, 111, 150, 166, 175, 200 = 中间是 150

---

5, 20, 25 = 中间是 20

66, 75, 80 = 中间是 75

---

92, 95, 111 = 中间是 95

166, 175, 200 = 中间是 175

---

92, 111 = 中间是 92

166, 200 = 中间是 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;

    }

Answer 1

您正在使用递归结构，因此递归函数通常可以使事情变得简单。class BST<T> {&nbsp; &nbsp; T value;&nbsp; &nbsp; BST<T> left;&nbsp; &nbsp; BST<T> right;&nbsp; &nbsp; public BST(T[] contents) {&nbsp; &nbsp; &nbsp; &nbsp; insert(contents);&nbsp; &nbsp; }&nbsp; &nbsp; private void insert(T[] contents) {&nbsp; &nbsp; &nbsp; &nbsp; if (contents.length > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (contents.length == 1) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; value = contents[0];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Split it.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int center = contents.length / 2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // Take the center value as my value&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; value = contents[center];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (center > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // There is more to the left so put it in my `left` branch.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; left = new BST<>(Arrays.copyOfRange(contents, 0, center));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (center < contents.length) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // ditto to the right.&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right = new BST<>(Arrays.copyOfRange(contents, center + 1, contents.length));&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; public int size() {&nbsp; &nbsp; &nbsp; &nbsp; return (left != null ? left.size() : 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + (value != null ? 1 : 0)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + (right != null ? right.size() : 0);&nbsp; &nbsp; }&nbsp; &nbsp; @Override&nbsp; &nbsp; public String toString() {&nbsp; &nbsp; &nbsp; &nbsp; return (left != null ? left.toString() + "," : "")&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + (value != null ? value : "")&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; + (right != null ? "," + right.toString() : "");&nbsp; &nbsp; }}private void test(Integer[] integers) {&nbsp; &nbsp; System.out.println("Array = " + Arrays.toString(integers) + " length " + integers.length);&nbsp; &nbsp; BST<Integer> bst = new BST<>(integers);&nbsp; &nbsp; System.out.println("BST = " + bst.toString() + " length " + bst.size());}private void test() {&nbsp; &nbsp; test(new Integer[]{5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175, 200});&nbsp; &nbsp; test(new Integer[]{5, 20, 25, 50, 66, 75, 80, 90, 92, 95, 111, 150, 166, 175});&nbsp; &nbsp; test(new Integer[]{90});&nbsp; &nbsp; test(new Integer[]{});}