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

Представление любого дерева, леса бинарными деревьями.

Читайте также:
  1. А тот русский националист, кто проявит физическую агрессию в отношении любого жида – собственноручно распишется в своей духовно-интеллекутальной слабости
  2. Глава 7 Интерпретация и представление результатов........................................221 1 страница
  3. Глава 7 Интерпретация и представление результатов........................................221 10 страница
  4. Глава 7 Интерпретация и представление результатов........................................221 11 страница
  5. Глава 7 Интерпретация и представление результатов........................................221 12 страница
  6. Глава 7 Интерпретация и представление результатов........................................221 2 страница
  7. Глава 7 Интерпретация и представление результатов........................................221 3 страница

Дерево и лес любого вида можно преобразовать единственным образом в эквивалентное бинарное дерево.

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

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

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

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

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

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

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

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

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

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

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

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

 

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


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


<== предыдущая страница | следующая страница ==>
Бинарные деревья.| Машинное представление деревьев в памяти ЭВМ.

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