-1

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

BST 类本身非常大，所以我认为发布它不是一个好主意。但是您可以在示例材料下找到源代码。参考代码位于 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 类型的泛型。在我的驱动程序类中，我只是添加了一组不平衡的元素 [A、B、C、D、E、F]，并且索引将正确显示我已经增加index 为 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 之前。

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

4

2 回答 2

1

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

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

您正试图在索引 (-1) 处插入一些东西。那是不合法的。

于 2019-10-31T18:37:41.373 回答
0

这是您更简洁的答案：

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

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

于 2019-10-31T22:00:57.400 回答