Деревья. основные понятия и определения.
Бинарное дерево
Цель: изучить фундаментальную абстрактную
структуру - дерево
Структуры, которые мы прежде обсуждали были
одномерные: в них один элемент следует за другим.
Сегодня мы сосредоточим наше внимание на
двухмерных связанных структурах называемых
деревьями, на которых основаны многие из
наиболее важных алгоритмов. Полное описание
деревьев могло бы занять не одну книгу, потому
что они возникают во многих задачах, даже вне
информатики, и довольно интенсивно изучаются как
математический объект. Сегодня мы рассмотрим
основные определения и терминологию связанную с
деревьями, изучим некоторые их свойства, и
обсудим способы из компьютерной реализации.
Позднее, мы встретим множество алгоритмов
использующих эту структуру данных.
В повседневной жизни мы очень часто встречаем
примеры деревьев, и Вы уже наверняка знакомы с
этой концепцией.
Например, люди часто используют
генеалогическое дерево для изображения
структуры своего рода; как мы увидим, много
терминов, связанных с деревьями, взято именно
отсюда.
Второй пример - это структура большой
организации; использование древообразной
структуры для представления ее "иерархической
структуры" ныне широко используется во многих
компьютерных задачах.
Третий пример - это грамматическое дерево;
изначально оно служило для грамматического
анализа компьютерных программ, а ныне широко
используется и для грамматического анализа
литературного языка.
Мы начнем изучение деревьев с того, что
определим их как некий абстрактный объект и
введем всю связанную с ними терминологию.
Самые простые из деревьев считаются бинарные
деревья.
Бинарное дерево-это конечное множество
элементов, которое либо пусто, либо содержит один
элемент, называемый корнем дерева, а остальные
элементы множества делятся на два
непересекающихся подмножества, каждое из
которых само является бинарным деревом.
Эти подмножества называются левым и правым
поддеревьями исходного дерева.
Каждый элемент бинарного дерева называется
узлом дерева.
На рисунке показан общепринятый способ
изображения бинарного дерева. Это дерево состоит
из девяти узлов, А-корень дерева. Его левое
поддерево имеет корень В, а правое- корень С. Это
изображается двумя ветвями, исходящими из А:
левым - к В и правым - к С. Отсутствие ветви
обозначает пустое поддерево.
Например, левое поддерево бинарного дерева с
корнем С и правое поддерево бинарного дерева с
корнем Е оба пусты. Бинарные деревья с корнями D, G,
Н и I имеют пустые левые и правые поддеревья.
На рисунке приведены некоторые
структуры, не являющиеся бинарными деревьями.
Если А - корень бинарного дерева и В - корень его
левого или правого поддерева, то говорят, что
А-отец В, а В-левый или правый сын А.
Узел, не имеющий сыновей (такие как узлы D, G, Н и
I), называется листом.
Узел nl -предок узла n2 (а n2-потомок nl), если nl-либо
отец n2, либо отец некоторого предка n2. Например, в
дереве из рисунке А-предок G и Н-потомок С, но Е не
является ни предком, ни потомком С.
Узел n2-левый потомок узла n1, если n2 является
либо левым сыном n1, либо потомком левого сына n1.
Похожим образом может быть определен правый
потомок.
Два узла являются братьями, если они сыновья
одного и того же отца.
Если каждый узел бинарного дерева, не являющийся
листом, имеет непустые правые и левые поддеревья,
то дерево называется строго бинарным деревом.
Свойство 1. Строго бинарное
дерево с n листами всегда содержит 2n-1 узлов.
Уровень узла в бинарном дереве может быть
определен следующим образом. Корень дерева имеет
уровень 0, и уровень любого другого узла дерева
имеет уровень на 1 больше уровня своего отца.
Например, в бинарном дереве на первом рисунке
узел Е- узел уровня 2, а узел Н-уровня 3.
Глубина бинарного дерева-это максимальный
уровень листа дерева, что равно длине самого
длинного пути от корня к листу дерева.
Стало быть, глубина дерева на первом рисунке
равна 3.
Полное бинарное дерево уровня n - это дерево, в
котором каждый узел уровня n является листом и
каждый узел уровня меньше n имеет непустые левое
и правое поддеревья
На рисунке приведен пример полного
бинарного дерева уровня 3.
Почти полное бинарное дерево - это
бинарное дерево, для которого существует
неотрицательное целое k такое, что
1. Каждый лист в дереве имеет уровень k или k+1.
2. Если узел дерева имеет правого потомка уровня
k+1, тогда все его левые потомки, являющиеся
листами, также имеют уровень k+1.
Строго бинарное дерево из рис. а не является
почти полным, поскольку оно содержит листы
уровней 1, 2 и 3, нарушая тем самым условие 1.
Строго бинарное дерево на рис. 6 удовлетворяет
условию 1, так как каждый лист имеет уровень 2 или
3. Однако при этом нарушается условие 2, поскольку
А имеет не только правого потомка уровня 3 (J), но
также и левого потомка, являющегося листом
уровня 2 (Е).
Строго бинарное дерево на рис. в удовлетворяет
обоим условиям и, следовательно, является почти
полным бинарным деревом.
Бинарное дерево на рис. г-также почти полное
бинарное дерево, но оно не является строго
бинарным, поскольку узел Е имеет лишь левого
сына.
Узлы почти полного бинарного дерева могут быть
занумерованы так, что корню назначается номер 1,
левому сыну-удвоенный номер его отца, а
правому-удвоенный номер отца плюс единица
(намного проще это понять, если представить эти
числа в двоичной системе).
Есть еще одна разновидность бинарных деревьев,
которая называется упорядоченные бинарные
деревья.
Упорядоченные бинарные деревья - это деревья, в
которых для каждого узла Х выполняется правило: в
левом поддереве - ключи, меньшие Х, в правом
поддереве - большие или равные Х.
Структура бинарного дерева построена из узлов.
Узел дерева содержит поле данных и два поля с
указателями.
Поля указателей называются левым указателем и
правым указателем, поскольку они указывают на
левое и правое поддерево, соответственно.
Значение nil является признаком пустого дерева.
Тогда бинарное дерево можно будет представить
в следующем виде.
Над бинарным деревом есть операция -
его прохождение, т.е. нужно обойти все дерево,
отметив каждый узел один раз.
Существует 3 способа обхода бинарного дерева.
- в прямом порядке
- в симметричном порядке
- в обратном порядке
В прямом порядке:
- Попасть в корень
- Пройти в прямом порядке левое поддерево
- Пройти в прямом порядке правое поддерево
В симметричном порядке:
- Пройти в симметричном порядке левое поддерево
- Попасть в корень
- Пройти в симметричном порядке правое поддерево
В обратном порядке:
- Пройти в обратном порядке левое поддерево
- Пройти в обратном порядке правое поддерево
- Попасть в корень
Давайте для закрепления полученных
знаний напишем программу.
Создается бинарное упорядоченное дерево,
заполняющееся псевдослучайными числами. Затем
осуществляется его вывод при обходе дерева
симметричным порядком.
Const
n = 10; {Поле z (ниже) моделирует любые данные в
записи,}
Type pt=^uzl;
uzl=Record
lson, rson: pt;
kl:byte;
End; {lson (rson) - ссылки на левого(правого) сына узла}
Var
j:word;
y:uzl;
coren:pt;
Procedure Vkl(Var cor:pt; y:uzl); {cor - ссылка на корень}
Var
nov,ss,tt: pt;
b: Boolean;
Begin
New(nov);
nov^:= y; {Порождение и заполнение переменной nov^;}
If cor = Nil Then
cor:= nov {если дерево пусто, делаем ее корнем}
Else {Цикл движения по трассе поиска:}
Begin
tt:= cor;
Repeat
ss:= tt;
b:= y.kl < ss^.kl;
If b Then
tt:= tt^.lson
Else
tt:= tt^.rson
Until tt = Nil;
If b Then
ss^.lson:= nov
Else
ss^.rson:= nov
End {Произошло связыванием нового узла с найденным
отцом ss^}
End;
Procedure Obrab(ss:pt);
Begin
Write(ss^.kl:5)
End;
Procedure Obhod(ss:pt); {Блок обхода БДУ слева}
{Ниже описывается тип элементов стека; в нем поле
sl - ссылка на узел БДУ, ssl - цепная связь в стеке}
Type
pnt=^z;
z=Record
sl:pt;
ssl:pnt
End;
Var
tt: pt;
q,t: pnt; {t - ссылка на верхушку стека}
Begin
t:= Nil; {стек - пуст}
Repeat
While ss <> Nil do
Begin
While ss^.lson <> Nil do {"Левая" трасса}
Begin {Очередной узел включается в стек: }
New(q);
q^.sl:= ss;
q^.ssl:= t;
t:= q;
ss:= ss^.lson{Продвижение по трассе}
End;
Obrab(ss);
ss:= ss^.rson
End;
q:= t;
If t <> Nil Then
Begin
ss:=t^.sl;
t:= t^.ssl; {Взятие ссылки из стека}
Dispose(q); {Освобождение памяти}
Obrab(ss); {Обработка узла как корня поддерева}
ss:= ss^.rson {Начало обхода правого поддерева}
End
Until q = Nil {Если стек опустел, обход БДУ закончен}
End;
BEGIN
Randomize;
coren:= Nil; {Порождено пустое дерево упорядочения}
y.lson:= Nil;
y.rson:= Nil;
For j:= 1 to n do {Цикл включения n записей в дерево}
Begin
y.kl:= Random(50); {Переменная y подготовлена к включению}
Vkl (coren, y) {Включение в ДДУ нового узла -
псевдослучайной записи}
End;
Obhod(coren); {Получение упорядоченной
последовательности ключей}
Readln; { путем обхода дерева и их вывод}
END.
Итак, на сегодняшнем занятии мы познакомились с
деревьями и основными операциями над ними. |
