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

UptoLike

ВУЗ: 

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

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

Рубрика: 

54 Глава 4. Нелинейные структуры данных
дерева в прямом порядке, пройти оставшиеся деревья в прямом поряд-
ке). Обратный, концевой, другие порядки определяются аналогично
обходам бинарных деревьев.
4.4. Другие представления деревьев
Последовательное представление в обратном порядке
Записываем узлы леса в обратном порядке и задаем степени (чис-
ло выходящих дуг) всех узлов.
B K C A H E J F G D
0 0 1 2 0 1 0 1 0 3
Такое представление удобно для вычисления функции, заданной
на узлах дерева.
Правая скобочная запись
Если корнем дерева T является узел a, с поддеревьями (T
1
, T
2
, ..., T
n
),
то правая скобочная запись определяется следующим образом:
1) r(a) = a;
2) r(T ) = (r(T
1
), ..., r(T
n
))a.
Пусть дано дерево T , изображенное на рисунке 4.4. Его правая
скобочная запись имеет вид r(T ) = ((3, 4)2, ((7, 8, 9)6)5)1).
Рис. 4.4
54                                   Глава 4. Нелинейные структуры данных


дерева в прямом порядке, пройти оставшиеся деревья в прямом поряд-
ке). Обратный, концевой, другие порядки определяются аналогично
обходам бинарных деревьев.


                4.4. Другие представления деревьев
      Последовательное представление в обратном порядке
   Записываем узлы леса в обратном порядке и задаем степени (чис-
ло выходящих дуг) всех узлов.

       B    K     C    A    H    E    J      F   G   D
       0    0     1    2    0    1    0      1   0   3
   Такое представление удобно для вычисления функции, заданной
на узлах дерева.

                           Правая скобочная запись
   Если корнем дерева T является узел a, с поддеревьями (T1 , T2 , ..., Tn ),
то правая скобочная запись определяется следующим образом:
     1) r(a) = a;
     2) r(T ) = (r(T1 ), ..., r(Tn ))a.
   Пусть дано дерево T , изображенное на рисунке 4.4. Его правая
скобочная запись имеет вид r(T ) = ((3, 4)2, ((7, 8, 9)6)5)1).




                                          Рис. 4.4

Страницы