Динамические структуры данных. Бинарные деревья (Динамические структуры данных)

Содержание:

ВВЕДЕНИЕ

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

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

Эта проблема решается с помощью динамических структур данных.

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

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

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

Объект исследования – структуры данных.

Предмет исследования – динамические структуры данных, бинарные деревья.

Цель исследования заключается в изучении динамических структур данных, а именно – бинарных деревьев.

Задачи исследования формируются исходя из его цели и заключаются в следующем:

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

1 Динамические структуры данных

1.1 Введение в динамические структуры данных

Объект данных имеет динамическую структуру, если его размер изменяется во время выполнения программы или он безразмерен^[1].

Все переменные, которые указаны в программе, размещаются в одной непрерывной области оперативной памяти – сегмент данных. Длина сегмента данных представляет собой область, которая определена архитектурой микропроцессора^[2].

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

Предположим, например, что у вас есть массив из 400 строк по 100 символов. Этот массив требует приблизительно 50K, что меньше максимального значения в 64K. Если остальные переменные помещаются в оставшиеся 14 килобайт, то массив такого размера не представляет проблемы. А если нужны два таких массива, то для этого потребуется 1000K и выделенного сегмента данных в 64 К недостаточно.

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

С другой стороны, объем памяти компьютера ограничен, чтобы успешно решать проблемы с большой размерностью данных. Выход – использование так называемой динамической памяти^[3].

Динамическая память – это оперативная память компьютера, которая предоставляется программе в процессе ее работы, минус сегмент данных (64К), стек (16К) и сам модуль программы. Размер динамической памяти может варьироваться. По умолчанию динамическая память – это вся доступная память компьютера^[4].

Динамическая память фактически является единственным способом обработки широкомасштабных массивов данных. Многие практические проблемы трудно или невозможно решить без использования ДП. Например, при разработке САПР статическое распределение памяти невозможно, поскольку размерность математических моделей в разных проектах может значительно различаться.

По своим адресам вызываются как статические, так и динамические переменные. Без адреса нельзя получить доступ к правильной ячейке памяти, но, если используются статические переменные, адрес напрямую не указывается. Обращение к переменной происходит по имени. Компилятор помещает переменные в память и подставляет нужные адреса в коды команд^[5].

Адресация динамических переменных осуществляется с помощью указателей. Их значения определяют адрес объекта.

Для работы с динамическими переменными в программе необходимо выполнить следующие действия:

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

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

1.2 Классификация динамических структур данных. Бинарные деревья

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

Рисунок 1.1 – Обобщенная классификация данных динамической структуры

Данные динамической структуры включают файлы, несвязанные и связанные динамические данные.

Рассмотрим подробнее такую структуру, как дерево^[7].

Дерево – это конечное множество узлов, такое что:

A) Существует один специальный узел, который называется корнем этого дерева.

B) Другие узлы (кроме корня) содержатся в m≥0 попарно непересекающихся подмножествах , каждое из которых, в свою очередь, является деревом. Деревья называются поддеревьями этого дерева.

Это определение рекурсивное^[8]. Дерево – это множество, которое состоит из корня и присоединенных поддеревьев, которые также являются деревьями. Дерево определяется через себя. Однако это определение имеет смысл, поскольку рекурсия конечна. В каждом поддереве меньше узлов, чем в дереве. В конце поддеревья содержат только один узел.

На рисунке 1.2 показано дерево с семью узлами.

Рисунок 1.2 – Дерево

Узлы, которые не содержат поддеревьев, называются концевыми узлами или листьями. Множество непересекающихся деревьев называется лесом. Например, лес формируется из поддеревьев, которые исходят из одного узла.

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

Бинарное дерево – это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются левым и правым поддеревьями исходного дерева. Каждый элемент бинарного дерева называется узлом дерева^[9].

На рисунке 1.3 показан способ изображения бинарного дерева.

Рисунок 1.3 – Бинарное дерево

Это дерево состоит из шести узлов, 22-корень дерева. Его левое поддерево имеет корень 19, а правое- корень 37. Это изображается двумя ветвями, исходящими из 22: левой – к 19 и правой – к 37. Отсутствие ветви обозначает пустое поддерево. Например, левое поддерево бинарного дерева с корнем 19 пустое. Бинарное дерево с корнем 37 имеет пустые левое и правое поддеревья.

Если А – корень бинарного дерева и В – корень его левого или правого поддерева, то говорят, что А-отец В, а В-левый или правый сын А. Узел, не имеющий сыновей (такие как узлы 8, 24, и 44), называется листом.

Например, в дереве на рисунке 1.3: 22 – предок 19 и 8-потомок 19, но 8 не является ни предком, ни потомком 22.

Два узла являются братьями, если они сыновья одного и того же отца. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правые и левые поддеревья, то дерево называется строго бинарным деревом. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов. В данном случае не строго бинарное дерево.

Упорядоченные бинарные деревья – это деревья, в которых для каждого узла Х выполняется правило: в левом поддереве – ключи, меньшие Х, в правом поддереве – большие или равные Х. Структура бинарного дерева построена из узлов. Узел дерева содержит поле данных и два поля с указателями^[10].

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

1.3 Операции над бинарным деревом

Над бинарным деревом есть операция – его прохождение, т.е. нужно обойти все дерево, отметив каждый узел один раз ^[12].

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

В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами.

Операции над двоичными деревьями поиска^[13]:

• добавление элемента в дерево;
• удаление элемента из дерева;
• обход дерева (для печати элементов и т.д.);
• поиск в дереве.

Прохождение (или обход) бинарного дерева означает систематическое перечисление всех узлов для выполнения необходимой функциональной обработки. Наиболее известны и практически важны 3 способа прохождения, которые отличаются порядком и направлением обхода бинарного дерева [6]:

• в прямом порядке;
• в симметричном порядке;
• в обратном порядке.

Таким образом, можно проходить узлы в прямом порядке (сверху-вниз), в симметричном порядке (слева-направо) и, наконец, в концевом порядке (снизу-вверх).

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

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

Таблица 1.1 – Рекурсивные алгоритмы прохождения бинарного дерева.

Порядок прохождения
Прямой (префиксный)	Симметричный (инфиксный)	Концевой (постфиксный)
Корень поддерева Левое поддерево Правое поддерево	Левое поддерево Корень дерева Правое поддерево	Левое поддерево Правое поддерево Корень дерева

Прямой порядок прохождения означает обход в направлении сверху-вниз, когда после посещения очередного разветвления продолжается прохождение вглубь дерева, пока не пройдены все потомки достигнутого узла. По этой причине прямой порядок прохождения часто называют нисходящим, или прохождением в глубину. Прямой порядок является наиболее естественным способом перечисления узлов дерева в форме вложенных скобок или ступенчатого списка. Если исключить все скобки и запятые, то последовательность узлов в форме вложенных скобок будет соответствовать прямому порядку прохождения дерева^[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;

var OK: Boolean;

begin

OK := false;

while not OK do begin

if X > P^.Key then //посмотреть направо

if P^.Right <> nil //правый узел не nil

then P := P^.Right //обход справа

else begin //правый узел – лист и надо добавить к нему элемент

InRight (P, X); //и конец

OK := true;

end

else //посмотреть налево

if P^.Left <> nil //левый узел не nil

then P := P^.Left //обход слева

else begin //левый узел -лист и надо добавить к нему элемент

InLeft(P, X); //и конец

OK := true

end;

end; //цикла while

end;

procedure Delete (var P: PItem; X: TInfo); export;

var Q: PItem;

procedure Del(var R: PItem);

//процедура удаляет узел, имеющий двух потомков, заменяя его на самый правый

//узел левого поддерева

begin

if R^.Right <> nil then //обойти дерево справа

Del(R^.Right)

else begin

//дошли до самого правого узла

//заменить этим узлом удаляемый

Q^.Key := R^.Key;

Q := R;

R := R^.Left;

end;

end; //Del

begin //Delete

if P <> nil then //искать удаляемый узел

if X < P^.Key then

Delete(P^.Left, X)

else

if X > P^.Key then

Delete(P^.Right, X) //искать в правом поддереве

else begin

//узел найден, надо его удалить

//сохранить ссылку на удаленный узел

Q := P;

if Q^.Right = nil then

//справа nil

//и ссылку на узел надо заменить ссылкой на этого потомка

P := Q^.Left

else

if Q^.Left = nil then

//слева nil

//и ссылку на узел надо заменить ссылкой на этого потомка

P := P^.Right

else //узел имеет двух потомков

Del(Q^.Left);

Dispose(Q);

end

else

MessageDlg('Такого элемента нет в дереве',mtError,[mbOK],0);

end;

exports InLeft,InRight,Tree_Add,Delete;

begin

end.

Листинг основной программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ComCtrls;

type

TInfo = Byte;

PItem = ^Item;

Item = record

Key: TInfo;

Left, Right: PItem;

end;

TTree = class

private

Root: PItem;

public

constructor Create;

procedure Add(Key: TInfo);

procedure Del(Key: TInfo);

procedure View;

procedure Exist(Key: TInfo);

end;

TForm1 = class(TForm)

GroupBox1: TGroupBox;

Edit1: TEdit;

Button2: TButton;

Button3: TButton;

Button5: TButton;

ListBox1: TListBox;

procedure FormCreate(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button5Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Root: PItem;

Tree: TTree;

N: Byte;

err: boolean;

Key: TInfo;

procedure InLeft (var P: PItem; X : TInfo); external 'binarytree.dll'

procedure InRight (var P: PItem; X : TInfo); external 'binarytree.dll'

procedure Tree_Add (P: PItem; X : TInfo);external 'binarytree.dll'

procedure Delete (var P: PItem; X: TInfo); external 'binarytree.dll'

implementation

{$R *.dfm}

constructor TTree.Create;

begin

Root := nil;

end;

procedure TTree.Add(Key: TInfo);

procedure IniTree(var P: PItem; X: TInfo); //создание корня дерева

begin

New(P);

P^.Key :=X;

P^.Left := nil;

P^.Right := nil;

end;

begin

if Root = nil

then IniTree(Root, Key)

else Tree_Add(Root, Key);

end;

procedure TTree.Del(Key: TInfo);

begin

Delete(Root, Key);

end;

procedure TTree.View;

procedure PrintTree(R: PItem; L: Byte);

var i: Byte;

begin

if R <> nil then begin

PrintTree(R^.Right, L + 3);

for i := 1 to L do

Form1.ListBox1.Items[Form1.ListBox1.Count-1]:=Form1.ListBox1.Items[Form1.ListBox1.Count-1]+' ';

Form1.ListBox1.Items[Form1.ListBox1.Count-1]:=Form1.ListBox1.Items[Form1.ListBox1.Count-1]+inttostr(R^.Key);

Form1.ListBox1.Items.Add('');

PrintTree(R^.Left, L + 3);

end;

end;

begin

Form1.ListBox1.Items.Add('');

PrintTree (Root, 1);

end;

procedure TTree.Exist(Key: TInfo);

procedure Search(var P: PItem; X: TInfo);

begin

if P = nil then begin

MessageDlg('Not Found Element',mtError,[mbOK],0);

end else

if X > P^. Key then //ищется в правом поддереве

Search (P^. Right, X)

else

if X < P^. Key then

Search (P^. Left, X)

else

MessageDlg('Found Element', mtCustom,[mbOK],0);

end;

begin

Search(Root, Key);

end;

procedure InputKey(S: String; var Key: TInfo);

begin

WriteLn(S);

ReadLn(Key);

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Tree := TTree.Create;

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

Form1.ListBox1.Clear;

if Edit1.Text = '' then else

Key:=strtoint(Edit1.Text);

Tree.Add(Key);

Tree.View;

Edit1.Clear;

Edit1.SetFocus;

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

Form1.ListBox1.Clear;

if Edit1.Text = '' then else

Key:=strtoint(Edit1.Text);

Tree.Del(Key);

Tree.View;

end;

procedure TForm1.Button5Click(Sender: TObject);

begin

err:=False;

try

Key:=strtoint(Edit1.Text);

err:=False;

except

err:=True;

ShowMessage('Значение узла не введено. Программа завершает работу');

Application.Terminate;

end;

Tree.Exist(Key);

end;

end.

1. Информатика: Уч. / В.А.Каймин - 6 изд. -М.: НИЦ ИНФРА-М, 2016 -285с. ↑

2. Информатика, автоматизированные информационные технологии и системы: Учебник / В.А. Гвоздева. - М.: ИД ФОРУМ: НИЦ ИНФРА-М, 2015. - 544 с. ↑

3. Базовые средства программирования/ В.Н. Шакин. - М.: Форум: НИЦ ИНФРА-М, 2015. - 304 с. ↑

4. Алгоритмы. Вводный курс/ Томас Х. Кормен М.: Вильямс, 2015. – 208с. ↑

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

6. Информатика: Уч. / В.А.Каймин - 6 изд. -М.: НИЦ ИНФРА-М, 2016 -285с. ↑

7. Стивенс Род - Алгоритмы. Теория и практическое применение – М.: ЭКСМО, 2016. – 544 с. ↑

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

9. Иерархические структуры данных: бинарные деревья. Учебное пособие по дисциплине «Информатика» / А.В. Никитин, Т.Н. Ничушкина - М.: МГТУ имени Н.Э. Баумана, 2017. – 60 с. ↑

10. Структуры данных – деревья – [Электронный ресурс] – режим доступа: https://pro-prof.com/archives/682 (дата обращения: 05.12.2020) ↑

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

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

13. Стивенс Род - Алгоритмы. Теория и практическое применение – М.: ЭКСМО, 2016. – 544 с. ↑

14. Иерархические структуры данных: бинарные деревья. Учебное пособие по дисциплине «Информатика» / А.В. Никитин, Т.Н. Ничушкина - М.: МГТУ имени Н.Э. Баумана, 2017. – 60 с. ↑

15. Бинарные деревья [Электронный ресурс] – режим доступа: http://www.codenet.ru/progr/alg/ btree.php (дата обращения: 05.12.2020) ↑

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

17. Голицына О.Л. Языки программирования: Учебное пособие / О.Л. Голицына, Т.Л. Партыка, И.И. Попов. – 3-e изд., перераб. и доп. – М.: Форум: ИНФРА-М, 2015. – 400 с. ↑