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

Правило построения бинарного дерева из любого дерева

Деревья, представление деревьев. | Свойства | АВЛ-дерево. Сбалансированное дерево | Малое правое вращение | Прошитые деревья |


Читайте также:
  1. аблица 22. Вычисление интегрального показателя дерева №1
  2. аблица 32. Вычисление интегрального показателя дерева №1
  3. агнитный поток. Явление электромагнитной индукции. Закон электромагнитной индукции. Правило Ленца. Явление самоиндукции. Индуктивность. Энергия магнитного поля.
  4. азовите основные принципы построения и функционирования государственной службы.
  5. актичні цілі, як правило, мають визначатися програмами діяльності уряду, центральних і місцевих органів виконавчої влади, цільовими про­грамами.
  6. алог на игорный бизнес и фиксированный налог: основы построения, механизм исчисления и взимания.
  7. Антитела защищают организм от инфекционного или же от любого чужеродного вещества. Они любым способом пытаются обезвредить антиген: растворить его либо «склеить».

1. В каждом узле оставить только ветвь к старшему сыну (вертикальное соединение);

2. Соединить горизонтальными ребрами всех братьев одного отца;

3. Таким образом перестроить дерево по правилу:

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

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

4. Развернуть дерево таким образом, чтобы все вертикальные ветви отображали левых сыновей, а горизонтальные - правых.

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

В процессе преобразования правый указатель каждого узла бинарного дерева будет указывать на соседа по уровню. Если такового нет, то правый указатель NIL. Левый указатель будет указывать на вершину следующего уровня. Если таковой нет, то указатель устанавливается на NULL

Рис.6.14. Исходное дерево

Рис.6.15 Промежуточный результат перестройки дерева

Рис. 6.16. Представление дерева в виде бинарного

 

Описанный метод представления произвольных упорядоченных деревьев посредством бинарных деревьев можно обобщить на представление произвольного упорядоченного леса.

 

Правило построения бинарного дерева из леса:

корни всех поддеревьев леса соединить горизонтальными связями.

В полученном дереве узлы будут располагаться на трех уровнях.

Далее перестраивать по ранее рассмотренному плану:

в начале поддерево с корнем А,

затем В

и затем Н

В результате преобразования упорядоченного леса в бинарное дерево получается полное бинарное дерево с левым и правым поддеревом

 

рис.6.17. Упорядоченный лес

 

 

Рис.6.18. Промежуточный результат перестройки леса

 

 

Рис. 6.19. Представление леса в виде 2-го дерева

 

 


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


<== предыдущая страница | следующая страница ==>
Бинарные деревья.| Красно-черные деревья

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