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), в худшем О(высоты дерева)
(1 балл)
Создайте непараметризованный класс, содержащий статический параметризованный метод, принимающий на вход Selector и печатающий все элементы контейнера, к которому относится переданный Selector.
(1 балл)
Ваша программа должна принимать в качестве параметра имя файла, содержащего целые числа. Эти числа должны добавляться в дерево в порядке их следования в файле. Программа должна выводить на экран эти числа от меньшего к большему и от большего к меньшему, используя описанные выше методы.
