如何修复我的数组，使我没有 IndexOutOfBoundsException？

Question

对于硬件作业，我的任务是将一堆方法添加到 BinarySearchTree class。我有两个方法是 balance 和 InsertTree（我认为它应该被命名为 InsertNode）。教科书中的作者提供了这些方法应该是什么样子的伪代码。两种方法相互配合； balance 应该采用不平衡树并将每个元素插入数组。我相信 InsertTree 应该从数组中取出元素并将它们放回新形成的树中。

BST Class 本身很大，所以我认为发布它不是一个好主意。但是您可以在示例材料下找到源代码 here。参考中的代码在 ch07.trees 包中。

到目前为止，这是我对作者伪代码的解释：

ArrayList<T> array = new ArrayList<T>();

public void balance()
// Will read, store, and recreate the tree
{
      Iterator<T> iter = this.iterator();
      int index = 0;
      while(iter.hasNext())
      {
          array.add(iter.next());
                  index++;
      }
      System.out.println(array.toString());
      System.out.println(index);

      tree = new BinarySearchTree<T>();
      tree.InsertTree(0, index -1);
  }

public void InsertTree(int low, int high)
// Will find the mid-point and insert other elements into left and right subtrees
  {
      if (low == high)
      {
          tree.add(array.get(low));
      }
      else if((low + 1) == high)
      {
          tree.add(array.get(low));
          tree.add(array.get(high));
      }
      else
      {
            int mid = (low + high)/2; 
            tree.add(array.get(mid));
            tree.InsertTree(low,mid-1);
            tree.InsertTree(mid+1,high);
      }
  }

我必须使用 ArrayList，因为所有方法都是 T 类型的泛型。在我的驱动程序中 class 我只是添加一组不平衡的元素 [A、B、C、D、E、F ] 和索引将正确显示我已将索引增加到 6。但是，当新树调用 InsertTree(0, index - 1) 时，我得到这个：

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 2, Size: 0
at java.util.ArrayList.rangeCheck(Unknown Source)
at java.util.ArrayList.get(Unknown Source)
at ch07.trees.BinarySearchTree.InsertTree(BinarySearchTree.java:180)
at ch07.trees.BinarySearchTree.balance(BinarySearchTree.java:163)
at ch07.trees.HWDriver.main(HWDriver.java:67)

第 163 行是 tree.InsertTree(0, index -1);，第 180 行是 tree.add(array.get(mid));

看来问题出在中间点，但我不确定问题出在哪里。我不是使用 ArrayLists 的专家，所以任何解决这个问题的帮助将不胜感激。

编辑：

我相信问题已经解决。我将我创建的数组放回 balance 方法而不是方法之外，并将该数组添加到 InsertTree 方法参数。然后，我不得不将每个条件输出从 this.tree.add 更改为 this.add。我还将我的 BinarySearchTree 树移回平衡方法，因为在我得到 NullPointerException 之前。

我的方法是否按预期工作仍有待确定。

Answer 1

看看当你有一个空集合时会发生什么...

int index = 0;
[...]
tree = new BinarySearchTree<T>();
tree.InsertTree(0, index -1);

您正试图在索引 (-1) 处插入内容。那是不合法的。

Answer 2

这里是你更简洁的答案：

this.tree = new BinarySearchTree<T>();
this.tree.InsertTree(0, index-1);

因此您创建了一个新的空树并将其存储在成员变量"tree"中。然后，您尝试将新的空树告诉 insertTree(0, 5) .

如何修复我的数组，使我没有 IndexOutOfBoundsException？

How can I fix my array so I don't have an IndexOutOfBoundsException?

java

binary-search-tree

tree-balancing