Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
FILENAME Дин_память_Бинарные_деревья_осень_2013 PAGE 12
Кроме линейных структур существуют и нелинейные, при помощи которых задаются иерархические связи данных. Для этого используются графы, а среди них сетевые и древовидные структуры. Рассмотрим один вид деревьев - бинарное дерево.
Бинарное (двоичное) дерево - это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются правым и левым поддеревьями исходного дерева.
Рис. 23 Двоичное дерево
На рис. 23 показан наиболее часто встречающийся способ представления бинарного дерева. Оно состоит из девяти узлов. Корнем дерева является узел А. Левое поддерево имеет корень В, а правое поддерево - корень С. Они соединяются соответствующими ветвями, исходящими из А. Отсутствие ветви означает пустое поддерево. Например, у поддерева с корнем С нет левого поддерева, оно пусто. Пусто и правое поддерево с корнем Е. Бинарные поддеревья с корнями D, G, H и I имеют пустые левые и правые поддеревья. Узел, имеющий пустые правое и левое поддеревья, называется листом. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правое и левое поддеревья, то дерево называется строго бинарным
Уровень узла в бинарном дереве определяется следующим образом: уровень корня всегда равен нулю, а далее номера уровней при движении по дереву от корня увеличиваются на 1 по отношению к своему непосредственному предку. Глубина бинарного дерева - это максимальный уровень листа дерева, иначе говоря, длина самого длинного пути от корня к листу дерева.
Узлы дерева могут быть пронумерованы по следующей схеме (см. рис. 24)
Рис. 24 Схема нумерации узлов двоичного дерева
Номер корня всегда равен 1, левый потомок получает номер 2, правый - номер 3. Левый потомок узла 2 должен получить номер 4, а правый - 5, левый потомок узла 3 получит номер 6, правый - 7 и т.д. Несуществующие узлы не нумеруются, что, однако, не нарушает указанного порядка, так как их номера не используются. При такой системе нумерации в дереве каждый узел получает уникальный номер. Использование нумерации при решении задач.
Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые правое и левое поддеревья.
Почти полное бинарное дерево определяется как бинарное дерево, для которого существует неотрицательное целое k такое, что:
Рассматривая действия над деревьями, можно сказать, что для построения дерева необходимо
Количество узлов определяется необходимостью. Алгоритм включения должен быть известен и постоянен. Узлы дерева могут быть использованы для хранения какой-либо информации.
Далее необходимо осуществлять поиск заданного узла в дереве. Это можно организовать, например, последовательно обходя узлы дерева, причем каждый узел должен быть просмотрен только один раз.
Может возникнуть задача и уничтожения дерева (освобождения памяти, занятой им) в тот момент, когда необходимость в нем (в информации, записанной в его элементах) отпадает. В ряде случаев может потребоваться уничтожение поддерева.
Для того, чтобы совокупность узлов образовала дерево, необходимо определенным образом формировать и использовать связи узлов со своими предками и потомками. По смыслу всё это (технология работы с адресами, ссылками) аналогично действиям над элементами списка.
Построение бинарного дерева.
Важным понятием древовидной структуры является понятие двоичного дерева поиска.
Правило построения двоичного дерева поиска: первый узел становится корнем дерева; добавляемые элементы, у которых значение некоторого признака меньше, чем у корня, всегда включаются слева от некоторого поддерева, а элементы со значениями, большими, чем у корня - справа.
Этот принцип используется и при формировании двоичного дерева, и при поиске в нем элементов. Таким образом, при поиске элемента с некоторым значением признака происходит спуск по дереву, начиная от корня, причем выбор ветви следующего шага - направо или налево согласно значению искомого признака - происходит в каждом очередном узле на этом пути.
При поиске элемента результатом будет
либо найденный узел с заданным значением признака,
либо поиск закончится листом с «нулевой» ссылкой, когда требуемый элемент отсутствует на проделанном по дереву пути.
Если поиск был проделан для включения очередного узла в дерево, то в результате будет найден узел с пустой ссылкой (пустыми ссылками), к которому справа или слева в соответствии со значением признака и будет присоединен новый узел.
Рассмотрим пример формирования двоичного дерева. Предположим, что нужно сформировать двоичное дерево, узлы (элементы) которого имеют следующие значения признака: 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;
Приведенный пример описания показывает, что описание элемента списка и узла дерева по сути ничем не отличаются друг от друга. Различия в технологии действий тоже невелики - основные действия выполняются над ссылками, адресами узлов. Основные различия - в алгоритмах.
При работе с двоичным деревом возможны следующие основные задачи:
Приведем примеры процедур, реализующих основные задачи работы с бинарным деревом.
{создание элемента дерева}
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 ('найден дубль
включаемого элемента');
readln;
exit; {завершение
работы процедуры}
end
end;
{после выхода из цикла в q - адрес элемента,
к которому должен быть подключен новый элемент}
if p^.inf1 < q^.inf1
then q^.left := p {подключение слева }
else q^.right := p; {подключение справа}
end;
ПРИМЕЧАНИЕ: элемент с дублирующим ключевым признаком в дерево не включается.
Данный алгоритм движения по дереву может быть положен в основу задач
то есть таких задач, решение которых основывается на алгоритме двоичного поиска по дереву.
Однако не все задачи могут быть решены с применением двоичного поиска, например, подсчет общего числа узлов дерева. Для этого требуется алгоритм, позволяющий однократно посещать каждый узел дерева.
При посещении любого узла возможно однократное выполнение следующих трех действий:
Нужно организовать обход узлов двоичного дерева, однократно выполняя над каждым узлом эту последовательность действий. Действия могут быть скомбинированы в произвольном порядке, но этот порядок должен быть постоянным в конкретной задаче обхода дерева.
На примере дерева на рис. 10 проиллюстрируем варианты обхода дерева:
20, 10, 8, 15, 17, 35, 27, 24, 30;
8, 10, 15, 17, 20, 24, 27, 30, 35
8, 17, 15, 10, 24, 30, 27, 35, 20
Если рассматривать задачи, требующие сплошного обхода дерева, то для части из них порядок обхода, в целом, не важен, например, подсчет числа узлов дерева, числа листьев/не листьев, элементов, обладающих заданной информацией и т.д. Однако такая задача, как уничтожение бинарного дерева с освобождением памяти, требует использования только обхода «в обратном порядке».
Рассмотрим средства, с помощью которых можно обеспечить варианты обхода дерева.
При работе с бинарным деревом с точки зрения программирования оптимальным вариантом построения программы является использование рекурсии. Базисный вариант рекурсивной процедуры обхода бинарного дерева очень прост.
{ обход дерева по варианту ОЛП }
Procedure Recurs_Tree ( q : nd );
Begin
If q <> nil { огранчитель рекурсии }
Then begin
Work ( q ); { процедура обработки дерева-О}
Recurs_Tree( q^.left );{уход по левой ветви-Л}
Recurs_Tree( q^.right );{уход по правой ветви-П}
End;
End;
{ обход дерева по варианту ЛОП }
Procedure Recurs_Tree ( q : nd );
Begin
If q <> nil
Then begin
Recurs_Tree( q^.left );{уход по левой ветви-Л}
Work ( q ); { процедура обработки дерева-О}
Recurs_Tree( q^.right );{уход по правой ветви-П}
End;
End;
{ обход дерева по варианту ЛПО }
Procedure Recurs_Tree ( q : nd );
Begin
If q <> nil
Then begin
Recurs_Tree( q^.left );{уход по левой ветви-Л}
Recurs_Tree( q^.right );{уход по правой ветви-П}
Work ( q ); { процедура обработки дерева-О}
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;
В заключение следует сказать о том, что рекурсивный обход дерева применим в большинстве задач, однако необходимо все же различать варианты эффективного применения двоичного поиска и сплошного обхода.
Перечень действий с деревьями
(для каждого варианта)
Стандартные действия.
1. Создание бинарного дерева:
а) из элементов созданного в лабораторной работе списка (см. часть 1);
б) из файла;
в) в диалоге с пользователем.
Способ формирования дерева: алгоритм бинарного поиска.
2. Сохранение дерева в файле.
3. Обход бинарного дерева каждым из трех способов (сверху вниз, снизу вверх, симметричный) с выдачей на экран содержимого информационных полей.
4. Включение элемента в бинарное дерево (согласно алгоритму формирования дерева).
5. Удаление заданного узла из дерева с его поддеревом (возможно удаление собственно узла)
6. Удаление дерева с освобождением памяти
Список дополнительных действий с бинарным деревом.
Определить количество листьев на каждом уровне дерева.
Определить количество узлов (не листьев) бинарного дерева.
Определить количество узлов (не листьев) бинарного дерева, находящихся на заданном уровне.
Определить количество узлов (не листьев) бинарного дерева, находящихся на одном уровне с узлом, заданным значением ключевого признака.
Определить, являются ли два поддерева, заданные своими корнями (с помощью значений ключевого признака) тождественными по структуре.
Определить общее количество узлов, (включая листья и корень), в поддереве данного узла, заданного значением ключевого признака.
Удалить все листья на заданном уровне дерева.
Удалить все листья дерева.
Удалить все узлы с заданным ключом ( вместе с поддеревьями, если есть ).
Отпечатать содержимое всех узлов, лежащих на пути между двумя узлами, заданными своими ключевыми признаками.
Отпечатать количество узлов, лежащих на пути между двумя узлами, заданными своими ключевыми признаками.
Отпечатать количество узлов, имеющих ключевые признаки, равные заданному, и лежащих на пути между двумя узлами, заданными своими ключевыми признаками.
Примечания.
Управление выбором функций организовать с помощью меню (использовать лабораторную работу «Списки_файлы», добавив в меню соответствующие пункты.)
Для целей отладки, а впоследствии и для демонстрации программы на защите одной из первых должна быть реализованы подзадача 1-б общего перечня действий «Формирование дерева из записей файла». Файл, как и дерево, должен содержать легко контролируемую информацию, сформированную для отладки заранее.
Вопросы для повторения