Бинарное дерево определяется как конечное множество узлов, которое или пусто, или состоит из корня и двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями корня. Для работы с древовидными структурами имеется множество алгоритмов, и многие из них используют одну и ту же идею, а именно идею прохождения или обхода дерева. Обход дерева подразумевает такой порядок работы с его узлами, для которого каждый из них посещается точно один раз. Для обхода бинарного дерева могут быть использованы три способа, определяемых рекурсивно. На рисунке ниже изображены все варианты обходов бинарного дерева.
Явное использование структуры бинарного дерева позволяет быстро вставлять
и удалять записи и производить эффективный поиск, и особенно целесообразно
для организации динамических таблиц, подверженных частым вставкам и удалениям.
Рассмотрим простой метод построения дерева.
Первую запись с ключом К1 поместим в корень дерева.
Второй ключ К2 сравним с К1. Если К2 < К2, поместим его в левое поддерево,
а если К2 >= К1, то в правое поддерево.
В общем случае, когда требуется поместить в дерево i-й ключ,
поступаем так: сравниваем Кi с ключами, начиная с корня.
Если Кi меньше очередного ключа, то переходим к левому сыну,
в противном случае – к правому, а если соответствующий сын отсутствует,
то это и есть место, куда нужно вставить ключ Ki.
Рисунок ниже иллюстрирует результат помещения последовательности целых чисел в дерево.
Программа, текст которой можно посмотреть справа, демонстрирует возможности работы с таблицей на основе бинарного дерева.