Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

Реализация очереди с помощью указателей | Разновидности очередей | Реализация стеков с помощью массивов | Итерационный вычислительный процесс | Рекурсивный вычислительный процесс | Вычисление факториала числа N с помощью рекурсии | Лекция 6 | Построение выражений в обратной польской записи | Преобразование скобочных выражений в обратную польскую запись | Нелинейные структуры. Деревья |


Читайте также:
  1. Б) из дерева
  2. В) Построение оценки эмпирической функции распределения и формирование классификационной шкалы
  3. Ветви дерева, или изучение ремесел
  4. Висвакарман, творец всего, создавший мир из неизвестного дерева, сделал это следующим образом.
  5. Вопрос 35 Конструктор формы списка иерархического справочника при указании размещения дерева...
  6. Вопрос 8 Если в конструкторе печати указано имя процедуры, которая будет выполнять построение печатной формы, и такая процедура уже присутствует в модуле...

 

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

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

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

 

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

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

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

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

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

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

 

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

 

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

 

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

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

 


Дата добавления: 2015-07-16; просмотров: 547 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Обходы дерева| Помеченные деревья и деревья выражения

mybiblioteka.su - 2015-2024 год. (0.007 сек.)