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

UptoLike

ВУЗ: 

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

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

Рубрика: 

определение в виде
⎩
⎨
⎧
−+
−
=
ТаТауровень
Та
Тaуровень
i
дерева корень не если ,1) , (
дерева корень если , 1
) , (
где T
i
– поддерево корня дерева T, такое, что a ∈T
i
.
Говорят, что каждый корень является отцом корней своих поддеревьев и
что последние являются сыновьями своего отца и братьями между собой. Го-
ворят также, что узел n – предок узла m (а узел m – потомок узла n), если n –
либо отец m, либо отец некоторого предка m.
Если в определении дерева существен порядок перечисления поддеревьев
Т
1
, Т
2
, ... , Т
m
, то дерево называют упорядоченным и говорят о “пер-
вом” ( Т
1
) , “втором” ( Т
2
) и т.д. поддеревьях данного корня. Далее будем
считать, что все рассматриваемые нами деревья являются упорядоченными,
если явно не оговорено противное. Отметим также, что в терминологии тео-
рии графов определенное ранее упорядоченное дерево более полно называ-
лось бы “конечным ориентированным (корневым) упорядоченным деревом”.
Лес – это множество (обычно упорядоченное), состоящее из некоторого
(быть может, равного нулю) числа непересекающихся деревьев. Используя
понятие леса, пункт б в определении дерева можно было бы сформулировать
так: “узлы дерева, за исключением корня, образуют лес”.
Традиционно дерево изображают графически, например так, как на рис.3.1.
a
d b c
h
j
f
g
k
ei
Рис. 3.1. Графическое изображение дерева
В графическом представлении для изображения структуры дерева суще-
ственно используется двухмерность рисунка. При машинной обработке часто
удобнее использовать текстовое представление дерева. Например, таким
представлением может быть так называемый уступчатый список. Здесь
“двухмерность” проявляется за счет того, что текст разбит на строки и фикси-
руется позиция символа узла в строке. На рис.3.2, а, б представлено в виде ус-
тупчатого списка дерево, изображенное на рис. 3.1.
Другой вид текстового (и принципиально одномерного) представления
дерева - это так называемая “скобочная запись” (ср. с записью иерархических
списков в разд.1.7). Определим скобочное представление дерева и леса:
44
определение в виде

                                                   если а − корень дерева Т
   уровень ( a , Т ) = ⎧⎨
                           1,
                        ⎩ уровень ( а , Т i ) + 1, если а − не корень дерева Т
где Ti – поддерево корня дерева T, такое, что a ∈Ti.
    Говорят, что каждый корень является отцом корней своих поддеревьев и
что последние являются сыновьями своего отца и братьями между собой. Го-
ворят также, что узел n – предок узла m (а узел m – потомок узла n), если n –
либо отец m, либо отец некоторого предка m.
    Если в определении дерева существен порядок перечисления поддеревьев
Т1 , Т2 , ... , Тm, то дерево называют упорядоченным и говорят о “пер-
вом” ( Т1 ) , “втором” ( Т2 ) и т.д. поддеревьях данного корня. Далее будем
считать, что все рассматриваемые нами деревья являются упорядоченными,
если явно не оговорено противное. Отметим также, что в терминологии тео-
рии графов определенное ранее упорядоченное дерево более полно называ-
лось бы “конечным ориентированным (корневым) упорядоченным деревом”.
    Лес – это множество (обычно упорядоченное), состоящее из некоторого
(быть может, равного нулю) числа непересекающихся деревьев. Используя
понятие леса, пункт б в определении дерева можно было бы сформулировать
так: “узлы дерева, за исключением корня, образуют лес”.
    Традиционно дерево изображают графически, например так, как на рис.3.1.

                                    a


                         b          c              d


                     i       j      h        e      f       g


                                                    k

                     Рис. 3.1. Графическое изображение дерева

      В графическом представлении для изображения структуры дерева суще-
ственно используется двухмерность рисунка. При машинной обработке часто
удобнее использовать текстовое представление дерева. Например, таким
представлением может быть так называемый уступчатый список. Здесь
“двухмерность” проявляется за счет того, что текст разбит на строки и фикси-
руется позиция символа узла в строке. На рис.3.2, а, б представлено в виде ус-
тупчатого списка дерево, изображенное на рис. 3.1.
      Другой вид текстового (и принципиально одномерного) представления
дерева - это так называемая “скобочная запись” (ср. с записью иерархических
списков в разд.1.7). Определим скобочное представление дерева и леса:


                                        44

Страницы