Бинарное дерево. Построение бинарного дерева

Ранее были рассмотрены упорядоченные ориентированные деревья, поскольку в них сыновья любого узла упорядочены слева направо, а пути по дереву ориентированы от начального узла пути к его потомкам. Бинарное (двоичное) дерево (БД) может быть или пустым, или деревом, у которого любой узел или не имеет сыновей, или имеет либо левого сына, либо правого сына, либо обоих. Тот факт, что каждый сын любого узла определен как левый или как правый сын, существенно отличает двоичное дерево от упорядоченного ориентированного дерева.

Любое дерево можно представить в виде эквивалентного БД. Алгоритм преобразования рассмотрим на примере дерева, изображенного на рис. 16.

Рис. 16 – Произвольное дерево, которое требуется преобразовать в БД

Порядок преобразования состоит из 2 этапов.

1. Для каждой вершины уничтожаются все исходящие из нее дуги, кроме самой левой. Вместо них рисуются дуги, которые соединяют выделенную вершину с вершиной, расположенной справа от нее на том же уровне.

2. Для каждой вершины осуществляется выбор левого и правого сыновей по правилу:

- левым сыном является вершина, расположенная непосредственно ниже данной вершины,

- правым сыном является вершина, расположенная непосредственно справа от данной на одном ярусе.

На рис. 17.а показан первый этап преобразования дерева, а на рис. 17.б – заключительный этап.

Рис. 17.а – Дерево после первого этапа преобразования

Рис. 17.б – БД, построенное на основе исходного дерева

Если любой узел БД, который не является листом, имеет левое и правое поддерево, то дерево называется строго бинарным деревом. Строго БД с n листьями всегда содержит 2n- 1 узлов. Полное БД уровня n – это дерево, в котором каждый узел уровня меньше n имеет непустое правое и левое поддеревья.

К БД применимы те же операция, что и к другим деревьям.

Не нашли, что искали? Воспользуйтесь поиском: