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

UptoLike

ВУЗ: 

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

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

Рубрика: 

a ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ а b i
b ▓▓▓▓▓▓▓▓▓▓▓▓▓▓
i ▓▓▓▓▓▓▓▓▓▓ j
j ▓▓▓▓▓▓▓▓▓▓
c ▓▓▓▓▓▓▓▓▓▓▓▓▓▓ c h
h ▓▓▓▓▓▓▓▓▓▓
d ▓▓▓▓▓▓▓▓▓▓▓▓▓▓ d e
e ▓▓▓▓▓▓▓▓▓▓
f ▓▓▓▓▓▓▓▓▓▓ f k
k ▓▓▓▓▓▓▓
g ▓▓▓▓▓▓▓▓▓▓ g
а б
Рис. 3.2. Представление дерева: а – в виде уступчатого списка;
б – в виде “упрощенного” уступчатого списка
< лес > ::= пусто | < дерево > < лес >,
< дерево > ::= ( < корень > < лес > ).
В скобочном представлении дерево, изображенное на рис. 3.1, запишется как
(a (b (i) (j) ) (c (h) ) (d (e) (f (k) ) (g))).
Наиболее важным типом деревьев являются бинарные деревья. Удобно
дать следующее формальное определение. Бинарное дерево − конечное мно-
жество узлов, которое либо пусто, либо состоит из корня и двух непересе-
кающихся бинарных деревьев, называемых правым поддеревом и левым под-
деревом. Так определенное бинарное дерево не является частным случаем
дерева. Например, бинарные деревья, изображенные на рис.3.3, различны ме-
жду собой, так как в одном случае корень имеет пустое правое поддерево, а в
другом случае правое поддерево непусто. Если же их рассматривать как дере-
вья, то они идентичны.
a
Рис. 3.3. Бинарные деревья из двух узлов
Определим скобочное представление бинарного дерева (БД):
< БД > ::= < пусто > | < непустое БД >,
< пусто > ::= Λ,
< непустое БД > ::= ( < корень > < БД > < БД > ).
Здесь пустое дерево имеет специальное обозначение − Λ.
Например, бинарное дерево, изображенное на рис.3.4, имеет скобочное
представление
a
b b
45
    a     ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓                        а      b    i
        b   ▓▓▓▓▓▓▓▓▓▓▓▓▓▓
            i     ▓▓▓▓▓▓▓▓▓▓                                  j
            j     ▓▓▓▓▓▓▓▓▓▓
        c   ▓▓▓▓▓▓▓▓▓▓▓▓▓▓                               c    h
            h     ▓▓▓▓▓▓▓▓▓▓
        d   ▓▓▓▓▓▓▓▓▓▓▓▓▓▓                               d    e
            e     ▓▓▓▓▓▓▓▓▓▓
            f     ▓▓▓▓▓▓▓▓▓▓                                  f      k
                k      ▓▓▓▓▓▓▓
            g     ▓▓▓▓▓▓▓▓▓▓                                  g
                 а                                        б
            Рис. 3.2. Представление дерева: а – в виде уступчатого списка;
                      б – в виде “упрощенного” уступчатого списка

                     < лес > ::= пусто | < дерево > < лес >,
                     < дерево > ::= ( < корень > < лес > ).
В скобочном представлении дерево, изображенное на рис. 3.1, запишется как
                (a (b (i) (j) ) (c (h) ) (d (e) (f (k) ) (g))).
   Наиболее важным типом деревьев являются бинарные деревья. Удобно
дать следующее формальное определение. Бинарное дерево − конечное мно-
жество узлов, которое либо пусто, либо состоит из корня и двух непересе-
кающихся бинарных деревьев, называемых правым поддеревом и левым под-
деревом. Так определенное бинарное дерево не является частным случаем
дерева. Например, бинарные деревья, изображенные на рис.3.3, различны ме-
жду собой, так как в одном случае корень имеет пустое правое поддерево, а в
другом случае правое поддерево непусто. Если же их рассматривать как дере-
вья, то они идентичны.

                             a                           a




                   b                                               b


                        Рис. 3.3. Бинарные деревья из двух узлов

   Определим скобочное представление бинарного дерева (БД):
         < БД > ::= < пусто > | < непустое БД >,
         < пусто > ::= Λ,
         < непустое БД > ::= ( < корень > < БД > < БД > ).
Здесь пустое дерево имеет специальное обозначение − Λ.
   Например, бинарное дерево, изображенное на рис.3.4, имеет скобочное
представление

                                          45

Страницы