Динамические структуры данных. Алексеев А.Ю - 49 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

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

Рубрика: 

a
b
e
c
d
k
i
f g
j
Рис. 3.6. Преобразованный лес
Повернув затем изображение леса из рис. 3.6 на 45
о
, получаем бинарное дере-
во, изображенное на рис. 3.7.
a
b e
c
d
k i
f
g
j
Рис. 3.7. Бинарное дерево, соответствующее лесу из рис. 3.5
Легко видеть, что, выполняя эти действия в обратном порядке, мы полу-
чим
oot ( B ) , F ( Left ( B ) ) ),
Согласно этому опреде ево T
1
леса F образуется из корня
бин
3.4. Обходы бинарных деревьев и леса
Многие алгоритмы работы с бинарными деревьями основаны на последо-
ват
единственный лес, соответствующий данному бинарному дереву. Это об-
ратное преобразование формально описывается следующим образом (здесь F
− лес типа Forest, а B − бинарное дерево типа BT):
F ( B ) ≡
if Null ( B ) then NIL
else Cons ( ConsTree ( R
F ( Right ( B ) ) ).
лению первое дер
арного дерева B и леса поддеревьев, полученного из левого поддерева би-
нарного дерева B. Остальные деревья ( Т
2
... Т
m
) леса F = ( Т
1
Т
2
... Т
m
) со-
ставляют лес, полученный из правого поддерева бинарного дерева B.
ельной (в определенном порядке) обработке узлов дерева. В этом случае
говорят об обходе (прохождении) бинарного дерева. Такой обход порождает
49
                         a                                 e


                b                 c                f       g           k


                d                                          i           j

                             Рис. 3.6. Преобразованный лес

Повернув затем изображение леса из рис. 3.6 на 45о, получаем бинарное дере-
во, изображенное на рис. 3.7.
                                       a

                     b                                                       e
           d                  c                    f

                                                               g

                                                       i               k

                                                                   j
               Рис. 3.7. Бинарное дерево, соответствующее лесу из рис. 3.5

   Легко видеть, что, выполняя эти действия в обратном порядке, мы полу-
чим единственный лес, соответствующий данному бинарному дереву. Это об-
ратное преобразование формально описывается следующим образом (здесь F
− лес типа Forest, а B − бинарное дерево типа BT):
       F ( B ) ≡ if Null ( B ) then NIL
                 else Cons ( ConsTree ( Root ( B ) , F ( Left ( B ) ) ),
                             F ( Right ( B ) ) ).
   Согласно этому определению первое дерево T1 леса F образуется из корня
бинарного дерева B и леса поддеревьев, полученного из левого поддерева би-
нарного дерева B. Остальные деревья ( Т2 ... Тm ) леса F = ( Т1 Т2 ... Тm ) со-
ставляют лес, полученный из правого поддерева бинарного дерева B.


                     3.4. Обходы бинарных деревьев и леса

   Многие алгоритмы работы с бинарными деревьями основаны на последо-
вательной (в определенном порядке) обработке узлов дерева. В этом случае
говорят об обходе (прохождении) бинарного дерева. Такой обход порождает

                                           49

Страницы