Работа с бинарными деревьями в Pascal

Бинарные деревья (основные понятия)

Определение:
Бинарное (двоичное) дерево (binary tree) - это упорядоченное дерево, каждая вершина которого имеет не более двух поддеревьев, причем для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.

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

Узел дерева, не имеющий потомков, называется листом.



Схематичное изображение бинарного дерева:


Операции над бинарными деревьями
Бинарное дерево должно реализовывать следующие операции:

• Инициализация бинарного дерева:
  текущий указатель устанавливается неопределенным (или нулевым, nil), а количество узлов нулевым.
• Помещение в бинарное дерево элемента:
  для нового элемента в бинарном дереве создается соответствующий узел, указатели на потомков которого пусты (поиск позиции для такого узла начинается с корня и проходит согласно правилам, определяющим структуру бинарного дерева).
• Получение значения текущего элемента
• Поиск заданного элемента:
  если искомый элемент находится в дереве, то возвращается указатель на него, в противном случае возвращается nil, сигнализирующий о неуспехе поиска значения
• Удаление узла из дерева
• Уничтожение бинарного дерева

Рассмотрим эти операции более подробно>>