Бинарное дерево на Java

Построение и обработка двоичных деревьев поиска. Реализовать программу, выполняющую следующий набор операций с деревьями поиска:
поиск вершины с заданным значением ключа с выводом счетчика числа появлений данного ключа добавление новой вершины в соответствии со значением ее ключа или увеличение счетчика числа появлений построчный вывод дерева в наглядном виде на основе процедур обхода:

- в прямом порядке.

- в симметричном порядке.

Рекомендации:

1) Объявить и реализовать подпрограмму поиска. Поиск начинается с корня дерева и в цикле для каждой вершины сравнивается ее ключ с заданным значением. При совпадении ключей, поиск заканчивается с выводом значения счетчика числа появлений данного ключа. При несовпадении поиск продолжается в левом или правом поддереве текущей вершины.

2) Объявить и реализовать рекурсивную подпрограмму добавления новой вершины в дерево. Подпрограмма использует один параметр-переменную, определяющую адрес текущей вершины. Если при очередном вызове подпрограммы этот адрес равен nil, то производится добавление нового элемента с установкой всех необходимых полей. В противном случае продолжается поиск подходящего места для новой вершины за счет рекурсивного вызова подпрограммы с адресом левого или правого поддерева. При совпадении ключей надо просто увеличить значение счетчика появлений.

3) Объявить и реализовать рекурсивные подпрограммы для построчного вывода дерева в прямом и симметричном порядке:

Все процедуры обхода должны выводить вершины с числом отступов, пропорциональным уровню вершины: корень дерева не имеет отступов, вершины первого уровня выводятся на 5 отступов правее, вершины 2-го уровня – еще на 5 отступов правее и т.д. Для этого в рекурсивные подпрограммы обхода надо ввести второй формальный параметр - уровень этой вершины.

Все процедуры обхода имеют похожую структуру. Например, процедура обхода в прямом направлении должна:

- проверить пустоту очередного поддерева

- вывести в цикле необходимое число пробелов в соответствии с уровнем вершины вывести информационную часть текущей вершины

- вызвать рекурсивно саму себя для обработки своего левого поддерева с увеличением уровня на 1

- вызвать рекурсивно саму себя для обработки своего правого поддерева с увеличением уровня на 1

Сравнение рассмотренных правил вывода двоичного дерева поиска приводится в следующей таблице:

Главная программа должна предоставлять следующие возможности:
- создание дерева с заданным числом вершин со случайными ключами;
- добавление в дерево одной вершины с заданным пользователем значением ключа поиск в дереве вершины с заданным ключом;
- построчный вывод дерева в наглядном виде.