Просмотр исходного текста страницы Java Test 20120321

'''(3 балла)'''

Создайте параметризованный класс двоичного деревева поиска, позволяющий хранить объекты, реализующие интерфейс java.lang.Comparable. Дерево должно быть реализовано таким образом, что в левой ветке храняться узлы со значением меньше корня, а в правой - больше корня.
В классе должны быть реализованы следующие методы:
# добавление узла (при добавлении элемента, значение которого уже присутствует в дереве должно быть сгенерированно Ваше собственное исключение BinaryTreeInsertionException)
# нахождение высоты дерева (возвращает int)
# поиск элемента (возвращает boolean)

'''(3 балла)'''

Создайте параметризованный интерфейс Selector<T>, содержащий следующие методы:
# T current()
# boolean hasNext()
# void next()
Добавьте к классу дерева два метода, один позволяет получать Selector, перебирающий элементы от меньшего к большему, а другой - от большего к меньшему, соответственно.

'''(3 балла)'''

Сделайте так, чтобы эти Selector'ы корректно работали в том случае, если после создания Selector'а и прохождения нескольких элементов в дерево были добавлены узлы. Такие узлы должны быть выданы селектором в "естественном" порядке, т.е., например, селектор перебирающий элементы от меньшего к большему, выдает минимальный элемент из не обработанных.

Например, к дереву с корнем 5 добавили узлы 2, 0, 4, 8, 6, 10. После чего, был создан селектор и с его помощью пройдены улы 0, 2, 4, 5, 6. Если после этого в дерево добавили узлы 1, 3, 7, то селектор следующими выдаст 1, 3, 7, 8, 10.

Selector'ы должны быть реализованы таким образом, чтобы время работы операций было следующим:
# current - O(1)
# hasNext, next - в лучшем случае О(1), в худшем О(logN)

'''(1 балл)'''

Создайте непараметризованный класс, содержащий статический параметризованный метод, принимающий на вход Selector и печатающий все элементы контейнера, к которому относится переданный Selector.

'''(1 балл)'''

Ваша программа должна принимать в качестве параметра имя файла, содержащего целые числа. Эти числа должны добавляться в дерево в порядке их следования в файле. Программа должна выводить на экран эти числа от меньшего к большему и от большего к меньшему, используя описанные выше методы.