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

(a (b (d Λ (h Λ Λ)) (e Λ Λ) ) (c (f (i Λ Λ)(j Λ Λ)) (g Λ (k (l Λ Λ) Λ))) ).

                                   a


                        b                               c

                                                            g
               d             e                  f

                    h
                                       i            j               k

                                                                l

                             Рис. 3.4. Бинарное дерево

   Можно упростить скобочную запись бинарного дерева, исключив “лиш-
ние” знаки Λ по правилам:
   1) ( < корень > < непустое БД > Λ) ≡ ( < корень > < непустое БД > ),
   2) ( < корень > Λ Λ) ≡ ( < корень > ).
   Тогда, например, скобочная запись бинарного дерева, изображенного на
рис.3.4, будет иметь вид
                 (a (b (d Λ h) (e)) (c (f (i) (j)) (g Λ (k (l))))).


             3.2. Спецификация дерева, леса, бинарного дерева

    Рассмотрим функциональную спецификацию структуры данных дерева c
узлами типа : Tree of α = Tree ( α ). При этом лес деревьев Forest ( Tree ( α ) )
определим как L_list ( Tree ( α ) ) через уже известную структуру линейного
списка L_list с базовыми функциями Cons, Head, Tail, Null (см.1.6). Базовые
операции с деревом задаются набором функций:
    1) Root : Tree → α;
    2) Listing : Tree → Forest;
    3) ConsTree : α ⊗ Forest → Tree
и аксиомами (∀u: α; ∀f: Forest ( Tree ( α ) ); ∀t: Tree ( α ) ):
    А1) Root ( ConsTree ( u , f ) ) = u;
    А2) Listing ( ConsTree ( u , f ) ) = f;
    А3) ConsTree ( Root ( t ) , Listing ( t ) ) = t.
    Здесь функции Root и Listing - селекторы: Root выделяет корень дерева, а
Listing выделяет лес поддеревьев корня данного дерева. Конструктор ConsTree
порождает дерево из заданных узла и леса деревьев.
    Тот факт, что структура данных Forest явно определена через
L_list ( Tree ), позволяет реализовать структуру дерева (леса) на базе другой

                                           46