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

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

образом в эквивалентное бинарное дерево.

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

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

кальное соединение);

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

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

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

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

одном ярусе с ней).

4. Развернуть дерево таким образом, чтобы все вертикальные ветви

отображали левых сыновей, а горизонтальные - правых.

В результате преобразования любого дерева в бинарное получа-

ется дерево в виде левого поддерева, подвешенного к корневой вер-

шине.

В процессе преобразования правый указатель каждого узла би-

нарного дерева будет указывать на соседа по уровню. Если такового

нет, то правый указатель NIL. Левый указатель будет указывать на

вершину следующего уровня. Если таковой нет, то указатель уста-

навливается на NIL.

(A) (A)

/ │ /

(b) (c) (d) (b)

/ /

(e) (f) (g) (c)

/ │ /

(h) (i) (k) (e) (d)

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

(f)

(A) /

│ (h) (g)

(b)───(c)────(d)

│ │ (i)

(e) (f)───(g)

│ (k)

(h)───(i)───(k)

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

перестройки дерева дерева в виде бинарного

Описанный выше метод представления произвольных упорядо-

ченных деревьев посредством бинарных деревьев можно обобщить

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

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

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

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

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

дерево с корнем А, затем В и затем Н. В результате преобразования

упорядоченного леса в бинарное дерево получается полное бинарное

дерево с левым и правым поддеревом.

 

 

(A) (G) (H)

/ │ __ (A)__

(b) (c) (i) /

│ / / │ (b) (G)

(d) (e) (f) (k) (l) (m) /

(d) (c) (H)

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

(e) (i)

(A)─────────(G)────────(H) /

│ │ (f) (k)

(b)──(c) (i)

│ │ │ (l)

(d) (e)──(f) (k)──(l)───(m)

(m)

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

перестройки леса леса в виде 2-го дерева

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

дерево получается полное бинарное дерево с левым и правым подде-

ревом.