Метод K [] preOrder () бинарного дерева поиска: об общем возврате - PullRequest
Новая
       28

Метод K [] preOrder () бинарного дерева поиска: об общем возврате

0 голосов
/ 31 октября 2011

Реализация Использование: лабораторная работа по структуре данных за октябрь / 28/2011. Задание: реализовать двоичное дерево поиска

Проблема: K [] возврат методов preOrder (), inOrder () и postOrder ()

Сведения о проблеме: BST должен иметь только корень в качестве параметра.Вышеупомянутые методы были описаны в интерфейсе, заданном нашим профессором, следующим образом: 

    /**
    * Returns an array of keys filled according
    * to the pre-order traversing in a BST.  
    */      
    public K[] preOrder();      
    public K[] order();         
    public K[] postOrder();

Я мог бы создать общий массив с помощью следующего кода: 

public K[] preOrder() {

    if (root == null) { return null; }

    ArrayList<K> list = new ArrayList<K>();
    preOrderRecursive(root,list);
    K[] toReturn = (K[]) Array.newInstance(this.getRoot().getKey().getClass(), list.size());

    for (int i = 0; i < list.size(); i++) {
        toReturn[i] = list.get(i);
    }

    return toReturn;
}

Но, когдаЯ проверил метод с использованием класса тестирования, также предоставленного нашим профессором, я получил исключение nullPointerException, которое, я думаю, ссылается на корень BST, который был когда-то создан, но был удален в какой-то момент в тесте, и когдаон вызывает метод снова, метод возвращает ноль, а не пустой массив, как ожидалось тестом: 

    (...)

    tree1 = new BSTImpl<Integer, Integer>();
    for (int i = 0; i < SIZE; i++) {
        tree1.insert(i, i);
    }
    tree1.remove(1);
    tree1.remove(2);
    tree1.remove(3);
    tree1.remove(4);
    assertArrayEquals(new Integer[]{},tree1.preOrder());

    (...)

Зная, что я не могу изменить тип возвращаемого значения или параметры метода, что я могусделать, чтобы избежать этого исключения?Могу ли я как-то получить тип компонента и использовать его для создания экземпляра пустого массива (как бы я это сделал?)?

Любые советы по улучшению моего кода также приветствуются.

1 Ответ

0 голосов
/ 31 октября 2011

Вопрос: Вам действительно нужен массив Integer ? - Я так не думаю.

Я полагаю, assertArrayEquals() не не проверяет тип компонента массивов, а скорее сравнивает только содержащиеся в нем значения.

С кодом, который вы показали, я бы сказал, что ничего другого было бы невозможно из-за стирания типа.

Так что попробуйте вернуть Object[] или любой другой тип, применяемый в вашем случае:

return new Object[0];

и

return list.toArray();

(необязательные броски требуются, но это должно быть хорошо.)

EDIT:

Хорошо, так что <K extends Comparable>?
В этом случае используйте:

return new Comparable[0];

и

return (Comparable[])list.toArray(new Comparable[]);

...