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

UptoLike

ВУЗ: 

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

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

Рубрика: 

F = ( Т
1
Т
2
... Т
m
).
Тогда Head ( F ) − первое дерево Т
1
леса F, а Tail ( F ) − лес остальных деревь-
ев (Т
2
... Т
m
). Если далее в дереве Head ( F ) выделить корень Root ( Head ( F ) )
и лес поддеревьев Listing ( Head ( F ) ),то исходный лес F представляется как
совокупность трех частей:
1) корня первого дерева − Root (Head ( F ) ),
2) леса поддеревьев первого дерева − Listing ( Head ( F ) ),
3) леса остальных деревьев − Tail ( F ).
Из этих трех частей рекурсивно порождается бинарное дерево B ( F ),
представляющее лес F:
B ( F ) ≡
if Null ( F ) then
Λ
else ConsBT ( Root ( Head ( F ) ),
B ( Listing ( Head ( F ) ) ),
B ( Tail ( F ) ) )
Согласно этому определениею корнем бинарного дерева B ( F ) является
корень первого дерева Т
1
в лесу F, левым поддеревом бинарного дерева B ( F )
является бинарное дерево, представляющее лес поддеревьев первого дерева
Т
1
, а правым поддеревом бинарного дерева B ( F ) является бинарное дерево,
представляющее лес остальных (кроме первого) деревьев исходного леса F.
Это формальное определение имеет следующую наглядную интерпрета-
цию. Рассмотрим, для примера, лес из двух деревьев, представленный на
рис. 3.5.
Ошибка!
a
b
e
c
d
k
i
f
g
j
Рис. 3.5. Лес из двух деревьев
Представляющее этот лес бинарное дерево можно получить, если со-
единить последовательно сыновей каждой семьи и убрать все вертикальные
связи, кроме связей, идущих от отцов к их первым сыновьям, как это показано
на рис. 3.6.
48
                                 F = ( Т1 Т2 ... Тm ).
Тогда Head ( F ) − первое дерево Т1 леса F, а Tail ( F ) − лес остальных деревь-
ев (Т2 ... Тm). Если далее в дереве Head ( F ) выделить корень Root ( Head ( F ) )
и лес поддеревьев Listing ( Head ( F ) ),то исходный лес F представляется как
совокупность трех частей:
    1) корня первого дерева − Root (Head ( F ) ),
    2) леса поддеревьев первого дерева − Listing ( Head ( F ) ),
    3) леса остальных деревьев − Tail ( F ).
    Из этих трех частей рекурсивно порождается бинарное дерево B ( F ),
представляющее лес F:

    B ( F ) ≡ if Null ( F ) then Λ
              else ConsBT ( Root ( Head ( F ) ),
                              B ( Listing ( Head ( F ) ) ),
                              B ( Tail ( F ) ) )

    Согласно этому определениею корнем бинарного дерева B ( F ) является
корень первого дерева Т1 в лесу F, левым поддеревом бинарного дерева B ( F )
является бинарное дерево, представляющее лес поддеревьев первого дерева
Т1, а правым поддеревом бинарного дерева B ( F ) является бинарное дерево,
представляющее лес остальных (кроме первого) деревьев исходного леса F.
    Это формальное определение имеет следующую наглядную интерпрета-
цию. Рассмотрим, для примера, лес из двух деревьев, представленный на
рис. 3.5.
                                  Ошибка!
                          a                                    e


                  b                c                     f     g    k


                  d                                            i    j


                              Рис. 3.5. Лес из двух деревьев

      Представляющее этот лес бинарное дерево можно получить, если со-
единить последовательно сыновей каждой семьи и убрать все вертикальные
связи, кроме связей, идущих от отцов к их первым сыновьям, как это показано
на рис. 3.6.




                                           48

Страницы