Алгоритмы и структуры данных на С++. Аксёнова Е.А - 53 стр.

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

4.3. Представление лесов деревьев в виде бинарных деревьев 53
Лесом называется конечное (возможно, пустое) множество дере-
вьев. На рисунке 4.2 представлен лес.
Рис. 4.2
Между лесами деревьев и бинарными деревьями можно устано-
вить взаимно однозначное соответствие (см. рис. 4.3).
Пусть дан лес F = (T
1
, T
2
, ..., T
n
). Поставим в соответствие ему
бинарное дерево B(F ), которое определяется следующим образом:
1) если n = 0, то B(F ) пусто;
2) если n > 0, то корнем дерева B(F ) является корень дерева T
1
,
левым поддеревом B(F ) является B(T
11
, T
12
, ..., T
1m
), где T
11
,
T
12
,..., T
1m
– поддеревья корня первого дерева, правым подде-
ревом B(F ) является B(T
2
, ..., T
n
).
Рис. 4.3
Можно определить алгоритм обхода лесов деревьев в прямом по-
рядке (попасть в корень первого дерева, пройти поддеревья первого
4.3.   Представление лесов деревьев в виде бинарных деревьев         53


   Лесом называется конечное (возможно, пустое) множество дере-
вьев. На рисунке 4.2 представлен лес.




                               Рис. 4.2

   Между лесами деревьев и бинарными деревьями можно устано-
вить взаимно однозначное соответствие (см. рис. 4.3).
   Пусть дан лес F = (T1 , T2 , ..., Tn ). Поставим в соответствие ему
бинарное дерево B(F ), которое определяется следующим образом:
  1) если n = 0, то B(F ) пусто;
  2) если n > 0, то корнем дерева B(F ) является корень дерева T1 ,
     левым поддеревом B(F ) является B(T11 , T12 , ..., T1m ), где T11 ,
     T12 ,..., T1m – поддеревья корня первого дерева, правым подде-
     ревом B(F ) является B(T2 , ..., Tn ).




                               Рис. 4.3

   Можно определить алгоритм обхода лесов деревьев в прямом по-
рядке (попасть в корень первого дерева, пройти поддеревья первого

Страницы