Файл: Динамические структуры данных. Бинарные деревья.pdf

Прямой порядок прохождения означает обход в направлении сверху-вниз, когда после посещения очередного разветвления продолжается прохождение вглубь дерева, пока не пройдены все потомки достигнутого узла. По этой причине прямой порядок прохождения часто называют нисходящим, или прохождением в глубину. Прямой порядок является наиболее естественным способом перечисления узлов дерева в форме вложенных скобок или ступенчатого списка. Если исключить все скобки и запятые, то последовательность узлов в форме вложенных скобок будет соответствовать прямому порядку прохождения дерева^[14].

Если применяется концевой порядок прохождения, то получается обход дерева снизу-вверх, когда в момент посещения любого узла все его потомки уже пройдены, а корень дерева проходится последним. Из-за этой особенности обхода, концевой порядок называют восходящим, или обратным относительно прямого.

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

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

Рисунок 1.4 – Траектория обхода бинарного дерева

Таблица 1.2 – Очередность прохождения узлов дерева

Порядок прохождения	Очередность обработки узлов
Прямой	A B C G D E F
Симметричный	C G B D E A F
Концевой	G C E D B F A

Организация данных с помощью бинарных деревьев позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева^[15].

---

2 Создание программного средства для работы с двоичными деревьями

2.1 Понятие динамической библиотеки

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

DLL – библиотека, в отличие от приложения, не имеет ни стека, ни очереди сообщений. Функции, помещенные в DLL, выполняются в контексте вызывающего приложения, используя его стек. Но эти функции используют сегмент данных, принадлежащий библиотеке, а не копию приложения. Благодаря организации библиотек DLL экономия памяти достигается за счет того, что все запущенные приложения используют один модуль DLL, не считая те или иные стандартные функции в своих модулях. В форме DLL можно создавать отдельные наборы функций, объединенные тем или иным логическим атрибутом, аналогично тому, как концептуально планирование модулей (в смысле единиц) происходит в Pascal. Разница в том, что функции из модулей Pascal связаны статически – на этапе связывания, а функции из DLL связаны динамически, то есть во время выполнения.

Структура файла DLL практически не отличается от обычной структуры модуля в Object Pascal. DLL должна начинаться со слова Library, за которым следует имя библиотеки. Функции и процедуры, которые DLL предоставит другим пользователям (экспорт), перечислены после директивы exports.

Для каждой процедуры или функции можно указать ее номер с помощью директивы Index. Если число отсутствует, компилятор автоматически его проиндексирует. Вместо номера процедуры можно использовать уникальное имя, которое устанавливается с помощью директивы name. Если ни имя функции, ни ее номер не указаны, Delphi примет это как экспорт по имени, которое будет совпадать с именем функции.

Библиотека также может содержать код инициализации, который будет выполняться при загрузке. Он находится между begin и end.

library First_Dll;

uses

  <используемые модули>;

  <объявления и описания функций>

---

  

exports

  <экспортируемые функции>

  <описание процедур и функций>

  

begin

  <инициализационная часть>

end.

Модуль, в котором необходимо использовать процедуры и функции из DLL, должен использовать внешнюю директиву. Существует два способа использования DLL (динамический и статический). В первом случае приложение, вызывающее функцию из DLL, знает имя библиотеки и точку входа в нее, и предполагается, что библиотека не изменяется. Во втором случае перед использованием DLL нужно убедиться, что необходимая библиотека существует и что в ней есть необходимая процедура^[17].

Можно импортировать подпрограмму по ее имени и номеру.

2.2 Создание динамической библиотеки для работы с бинарными деревьями

Описание процедур динамической библиотеки представлено в таблице 2.1, а блок-схемы их алгоритмов – на рисунках 2.1-2.5.

Таблица 2.1 – Описание процедур динамической библиотеки

Процедура	Описание
Tree.Add	Процедура формирования дерева
InLeft	Процедура добавления узла дерева слева
InRight	Процедура добавления узла дерева справа
Del	Процедура удаляет узел, имеющий двух потомков, заменяя его на самый правый узел левого поддерева
Delete	Процедура удаления узла дерева

Рисунок 2.1 – Блок-схема алгоритма добавления узла слева

Рисунок 2.2 – Блок-схема алгоритма добавления узла справа

Рисунок 2.3 – Блок-схема алгоритма формирования дерева

Рисунок 2.4 – Блок-схема алгоритма удаления узла, имеющего двух потомков и замены его на самый правый узел левого поддерева

Рисунок 2.5 – Блок-схема алгоритма удаления узла дерева

Листинг кода динамической библиотеки и основной программы приведен в Приложении.

2.3 Описание работы программы

Программа представляет собой форму с расположенными на ней компонентами: Button, Edit и ListBox [4].

Рис. 3. Основное окно программы

Добавление элементов происходит с помощью процедуры procedure TForm1.AddClick(Sender: TObject) [9];

---

Рис. 3. Построенное дерево

Каждый раз после ввода значения элемента вызывается процедура Tree.Add; Сначала создается корень дерева (procedure IniTree), затем добавляются узлы слева и справа (procedure InLeft и procedure InRight). Далее смотрим направо и, если правый узел не пустой, то обходим справа. Добавляем элемент. Смотрим налево и, если левый узел не пустой, то обходим слева. Добавляем элемент. Повторяем до тех пор, пока значение OK не становится true.

Удаление элементов происходит с помощью процедуры procedure TTree.Del(Key: TInfo);

Рис. 4. Удаление элементов

Процедура удаляет узел, имеющий двух потомков, заменяя его на самый правый узел левого поддерева. Далее обходим дерево справа и заменяем самый правый узел удаляемым. Ищем удаляемый узел. Сохраняем ссылку на удаленный узел. Справа nil и ссылку на узел надо заменить ссылкой на этого потомка. Слева nil и ссылку на узел надо заменить ссылкой на этого потомка. Если узел имеет двух потомков, удаляем левый.

Поиск элемента происходит с помощью процедуры procedure TTree.Exist(Key: TInfo);

Рис. 5. Элемент найден

Сначала идем направо, пока значение элемента больше (if X > P^. Key then Search (P^. Right, X)). Как только значение элемента, который мы ищем становится меньше идем налево (if X < P^. Key then Search (P^. Left, X)

Рис. 5. Элемент не найден

Рис. 5. Элемент не введен

ЗАКЛЮЧЕНИЕ

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

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

Во время написания курсовой ознакомились со всей теорией деревьев, особенное внимание было уделено понятию бинарного дерева, операциям с бинарным деревом.

---

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Алгоритмы. Вводный курс/ Томас Х. Кормен М.: Вильямс, 2015. – 208с.
2. Алгоритмы. Разработка и применение / Дж. Клейнберг Дж., Е. Тардос – СПб.: Питер, 2016. – 800 с.
3. Базовые средства программирования/ В.Н. Шакин. – М.: Форум: НИЦ ИНФРА-М, 2015. – 304 с.
4. Бинарные деревья [Электронный ресурс] – режим доступа: http://www.codenet.ru/progr/alg/btree.php (дата обращения: 05.12.2020)
5. Голицына О.Л. Языки программирования: Учебное пособие / О.Л. Голицына, Т.Л. Партыка, И.И. Попов. – 3-e изд., перераб. и доп. – М.: Форум: ИНФРА-М, 2015. – 400 с.

• Дискретная математика для программистов / Гэри Хаггард, Джон Шлипф, Сью Уайтсайдс – М.: Бином. Лаборатория знаний, 2017. – 632с.

1. Иерархические структуры данных: бинарные деревья / А.В. Никитин, Т.Н. Ничушкина – М.: МГТУ имени Н.Э. Баумана, 2017. – 60 с.
2. Информатика, автоматизированные информационные технологии и системы: Учебник / В.А. Гвоздева. – М.: ИД ФОРУМ: НИЦ ИНФРА-М, 2015. – 544 с.
3. Информатика / В.А.Каймин – 6 изд. -М.: НИЦ ИНФРА-М, 2016 – 285с.

• Кормен Томас  Алгоритмы. Построение и анализ / Томас Кормен, Чарльз Лейзерсон, Рональд Риверст, Клиффорд Штайн – М.: Вильямс, 2016. – 1328с.

1. Программирование на языке высокого уровня. Учебное пособие / Т.И. Немцова; Под ред. Л.Г. Гагариной. – М.: ФОРУМ: ИНФРА-М, 2015. – 496 с.

• Стивенс Род – Алгоритмы. Теория и практическое применение – М.: ЭКСМО, 2016. – 544 с.
• Структуры данных – деревья – [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/682 (дата обращения: 05.12.2020)

Приложение

Текст программы (на языке программирования Object Pascal)

Листинг программы динамической библиотеки Dll

library binarytree;

uses

SysUtils,

Classes, Dialogs;

{$R *.res}

type

TInfo = Byte;

PItem = ^Item;

Item = record

Key: TInfo;

Left, Right: PItem;

end;

procedure InLeft (var P: PItem; X : TInfo); export;//добавление узла слева

var R : PItem;

begin

New(R);

R^.Key := X;

R^.Left := nil;

R^.Right := nil;

P^.Left := R;

end;

procedure InRight (var P: PItem; X : TInfo); export;//добавить узел справа

var R : PItem;

begin

New(R);

R^.Key := X;

R^.Left := nil;

R^.Right := nil;

P^.Right := R;

end;

procedure Tree_Add (P: PItem; X : TInfo); export;

---