Для задания HW мне было поручено добавить несколько методов в класс BinarySearchTree. У меня есть два метода: balance и InsertTree (я думаю, он должен был называться InsertNode). Авторы из учебника предоставили псевдокод того, как должны выглядеть методы. Оба метода работают друг с другом;Баланс должен взять несбалансированное дерево и вставить каждый элемент в массив. Я считаю, что 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] и индекса будет правильно показывать, что я увеличил индекс до 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, поэтому любая помощь в решении этой проблемы будет высоко оценена.
edit:
Я считаю, что проблема была исправлена. Я поместил созданный массив обратно в метод balance, а не за его пределы, и добавил массив в аргументы методов InsertTree. Затем мне пришлось изменить каждый условный вывод из this.tree.add в this.add. Я также переместил свое дерево BinarySearchTree обратно в сбалансированный метод, потому что до того, как я получил NullPointerException.
Работает ли мой метод, как предполагалось, еще предстоит определить.