среда, 25 мая 2011 г.

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

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

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

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

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



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


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

Комментариев нет:

Отправить комментарий