Действия с бинарными деревьями.

Рассматривая действия над деревьями, можно сказать, что для построения дерева необходимо формировать узлы, и, определив предварительно место включения, включать их в дерево. Количество узлов определяется необходимостью. Алгоритм включения должен быть известен и постоянен. Узлы дерева могут быть использованы для хранения какой-либо информации.

Далее необходимо осуществлять поиск заданного узла в дереве. Это можно организовать, например, последовательно обходя узлы дерева, причем каждый узел должен быть просмотрен только один раз.

Может возникнуть задача и уничтожения дерева в тот момент, когда необходимость в нем (в информации, записанной в его элементах) отпадает. В ряде случаев может потребоваться уничтожение поддерева.

Для того, чтобы совокупность узлов образовала дерево, необходимо каким-то образом формировать и использовать связи узлов со своими предками и потомками. Все это очень напоминает действия над элементами списка.

Построение бинарного дерева.

Важным понятием древовидной структуры является понятие двоичного дерева поиска. Правило построения двоичного дерева поиска: элементы, у которых значение некоторого признака меньше, чем у корня, всегда включаются слева от некоторого поддерева, а элементы со значениями, большими, чем у корня - справа. Этот принцип используется и при формировании двоичного дерева, и при поиске в нем элементов. Таким образом, при поиске элемента с некоторым значением признака происходит спуск по дереву, начиная от корня, причем выбор ветви следующего шага - направо или налево согласно значению искомого признака - происходит в каждом очередном узле на этом пути. При поиске элемента результатом будет либо найденный узел с заданным значением признака, либо поиск закончится листом с «нулевой» ссылкой, а требуемый элемент отсутствует на проделанном по дереву пути. Если поиск был проделан для включения очередного узла в дерево, то в результате будет найден узел с пустой ссылкой (пустыми ссылками), к которому справа или слева в соответствии со значением признака и будет присоединен новый узел.

Рассмотрим пример формирования двоичного дерева. Предположим, что нужно сформировать двоичное дерево, узлы (элементы) которого имеют следующие значения признака: 20, 10, 35, 15, 17, 27, 24, 8, 30. В этом же порядке они и будут поступать для включения в двоичное дерево. Первым узлом в дереве (корнем) станет узел со значением 20. Обратить внимание: поиск места подключения очередного элемента всегда начинается с корня. К корню слева подключается элемент 10. К корню справа подключается элемент 35. Далее элемент 15 подключается справа к 10, проходя путь: корень 20 - налево - элемент 10 - направо - подключение, так как дальше пути нет. Процесс продолжается до исчерпания включаемых элементов. Результат представлен на рис. 25.

Рис. 25 Построение бинарного дерева.

Значения элементов дерева: 20, 10, 35, 15, 17, 27, 24, 8, 30

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

Решение задач работы с бинарным деревом.

Элемент дерева используется для хранения какой-либо информации, следовательно, он должен содержать информационные поля, возможно разнотипные. Элемент двоичного дерева связан в общем случае с двумя прямыми потомками, а при необходимости может быть добавлена и третья связь - с непосредственным предком. Отсюда следует, что по структуре элемент дерева (узел) похож на элемент списка и может быть описан так же. Как и в списке, в дереве должна существовать возможность доступа к его «первому» элементу - корню дерева. Она реализуется через необходимую принадлежность дерева - поле ROOT, в котором записывается ссылка на корневой элемент.

Приведем пример описания полей и элементов, необходимых для построения дерева.

Type

Nd = ^ node;

Node = record

Inf1 : integer;

Inf2 : string ;

Left : nd;

Right : nd;

End;

Var

Root, p,q : nd;

Приведенный пример описания показывает, что описание элемента списка и узла дерева по сути ничем не отличаются друг от друга. Различия в технологии действий тоже невелики - основные действия выполняются над ссылками, адресами узлов. Основные различия - в алгоритмах.

При работе с двоичным деревом возможны следующие основные задачи:

1) создание элемента, узла дерева,

2) включение его в дерево по алгоритму двоичного поиска,

3) нахождение в дереве узла с заданным значением ключевого признака,

4) определение максимальной глубины дерева,

5) определение количества узлов дерева,

6) определение количества листьев дерева,

7) ряд других задач.

Приведем примеры процедур, реализующих основные задачи работы с бинарным деревом.

{создание элемента дерева}

Procedure CREATE_EL_T(var q:ND; nf1:integer;

inf2:string);

Begin

new(q);

q^.inf1:=inf1;

q^.inf2:=inf2;

{значения полей передаются в качестве параметров}

q^.right:=nil;

q^.left:=nil;

end;

procedure Insert_el ( p : nd; {адрес включаемого элемента}

var root : nd);

Var

q, t : nd;

Begin

if root = nil then

root := p {элемент стал корнем}

Else

begin { поиск по дереву }

t := root;

q := root;

while ( t < > nil ) do

Begin

if p^.inf1 < t^.inf1 then

Begin

q := t;{ запоминание текущего адреса}

t := t^.left; {уход по левой ветви}

End

Else

if p^.inf1 > t^.inf1 then

Begin

q := t;{ запоминание текущего адреса}

t := t^.right; {уход по правой ветви}

End

Else

Begin

writeln ('найден дубль включаемого элемента');

exit; {завершение работы процедуры}

End

end;

{после выхода из цикла в q - адрес элемента, к которому

должен быть подключен новый элемент}

if p^.inf1 < q^.inf1 then

q^.left := p {подключение слева }

Else

q^.right := p; {подключение справа}

end;

ПРИМЕЧАНИЕ: элемент с дублирующим ключевым признаком в дерево не включается.

Данный алгоритм движения по дереву может быть положен в основу задачи определения максимального уровня (глубины) двоичного дерева, определения, есть ли в дереве элемент с заданным значением ключевого признака и т.д., то есть таких задач, решение которых основывается на алгоритме двоичного поиска по дереву.

Однако не все задачи могут быть решены с применением двоичного поиска, например, подсчет общего числа узлов дерева. Для этого требуется алгоритм, позволяющий однократно посещать каждый узел дерева.

При посещении любого узла возможно однократное выполнение следующих трех действий:

1) обработать узел (конкретный набор действий при этом не важен). Обозначим это действие через О (обработка);

2) перейти по левой ссылке (обозначение - Л);

3) перейти по правой ссылке (обозначение - П).

Можно организовать обход узлов двоичного дерева, однократно выполняя над каждым узлом эту последовательность действий. Действия могут быть скомбинированы в произвольном порядке, но он должен быть постоянным в конкретной задаче обхода дерева.

На примере дерева на рис. 10 проиллюстрируем варианты обхода дерева.

1) Обход вида ОЛП. Такой обход называется «в прямом порядке», «в глубину». Он даст следующий порядок посещения узлов:

20, 10, 8, 15, 17, 35, 27, 24, 30

2) Обход вида ЛОП. Он называется «симметричным» и даст следующий порядок посещения узлов:

8, 10, 15, 17, 20, 24, 27, 30, 35

3) Обход вида ЛПО. Он называется «в обратном порядке» и даст следующий порядок посещения узлов:

8, 17, 15, 10, 24, 30, 27, 35, 20

Если рассматривать задачи, требующие сплошного обхода дерева, то для части из них порядок обхода, в целом, не важен, например, подсчет числа узлов дерева, числа листьев/не листьев, элементов, обладающих заданной информацией и т.д. Однако такая задача, как уничтожение бинарного дерева с освобождением памяти, требует использования только обхода «в обратном порядке».

Рассмотрим средства, с помощью которых можно обеспечить варианты обхода дерева.

При работе с бинарным деревом с точки зрения программирования оптимальным вариантом построения программы является использование рекурсии. Базисный вариант рекурсивной процедуры обхода бинарного дерева очень прост.

{ обход дерева по варианту ЛОП }

Procedure Recurs_Tree ( q : nd );

Begin

If q <> nil Then

Begin

Recurs_Tree( q^.left );{уход по левой ветви-Л}

Work ( q ); { процедура обработки дерева-О}

Recurs_Tree( q^.right );{уход по правой ветви-П}

End;

End;

Рекурсия в этой программе действует точно так же, как и в рекурсивных процедурах работы со списками: создается цепочка процедур, каждая из которых рекурсивно обращается к себе и затем ожидает завершения вызванной процедуры. Потенциально бесконечный процесс рекурсивного вызова останавливается с помощью «ограничителя рекурсии», в данном случае им становится нарушение условия ( q <> nil ), когда при обходе обнаруживается «нулевая» ссылка вместо реального адреса. При этом начинается последовательное завершение вызванных процедур с возвратом управления в вызывающую. Способ обхода меняется с изменением порядка обращений к процедурам.

Для практической проработки действия механизма рекурсии при реализации вариантов обхода дерева можно воспользоваться уже построенным деревом с рис.10.

Пример использования рекурсивной процедуры при решении задачи подсчета листьев двоичного дерева.

Procedure Leafs_Count( q : nd; var k : integer );

Begin

If q <> nil Then

Begin

Leafs_Count( q^.left, k );

If (q^.left = nil) and (q^.right = nil) Then

K := K +1;

Leafs_Count( q^.right, k );

End;

End;

{удаление дерева с освобождением памяти}

Procedure del_tree(q : nd );

Begin

if q<>nil then

Begin

del_tree (q^.left);

del_tree (q^.right);

Dispose(q)

End

end;

В заключение следует сказать о том, что рекурсивный обход дерева применим в большинстве задач, однако необходимо все же различать варианты эффективного применения двоичного поиска и сплошного обхода.

Вопросы к главе 7.

1. Особенности использования статической и динамической памяти.

2. Описание динамических переменных.

3. Использование указателей и ссылочных переменных.

4. Основные процедуры и функции для выделения и освобождения памяти на логическом уровне.

5. Основные процедуры и функции для выделения и освобождения памяти на физическом уровне.

6. Особенности использования динамических переменных.

7. Особенности создания и обработки очередей.

8. Особенности создания и обработки стеков и деков.

9. Особенности создания и обработки однонаправленных списков.

10. Особенности создания и обработки двунаправленных списков.

11. Особенности создания и обработки кольцевых списков.

12. Особенности создания и обработки списков с головными элементами.

13. Особенности создания и обработки мультисписков.

14. Использование рекурсии при работе со списками.

15. Понятия дерева, двоичного дерева поиска.

16. Нерекурсивные способы создания и обработки двоичных деревьев.

17. Рекурсивные способы создания и обработки двоичных деревьев.

Не нашли, что искали? Воспользуйтесь поиском по сайту: