Сортировка бинарным деревом реферат

Обновлено: 03.07.2024

Данная работа выполнена в объеме: пояснительная записка на 33 страницах, 26 иллюстрациях, 3 таблицах, 7 источниках, 2 приложениях.

Ключевые слова: автоматизация, автоматизированное рабочее место, информационно-поисковая система, учет записей по всем культурам.

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

В процессе разработки выполнены следующие исследования:

– рассмотрены и применены на практике различные алгоритмы работы с бинарным деревом;

– улучшены навыки пользования различными компонентами среды разработки Visual Studio 2013.

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

Областью возможного практического применения являются: физические лица, нуждающиеся в учете своего урожая. Фермеры, компании, занимающиеся овощеводством.

Основные технико-эксплуатационные показатели: высокая скорость работы с данными, предельно низкие системные требования, а также низкая цена программного продукта.

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

1 Бинарные деревья и их актуальность. 7

1.1 Назначение бинарных деревьев. 7

1.2 Определение бинарного дерева. 7

1.3 Алгоритм бинарного поиска. 8

1.4 Алгоритм вставки узлов. 10

1.5 Алгоритм удаления узлов. 11

2 Методика решения поставленой задачи и обоснование наравления разработки программного продукта. 13

2.1 Обоснование выбранного языка программирования. 13

2.2 Методика решения поставленной задачи. 13

3 Разработка программы.. 16

3.1 Диаграмма классов. 16

3.2 Проектирование интерфейса программы.. 17

3.3 Описание программных модулей. 17

3.4 Разработка, тестирование методов. 18

3.5 Тестирование программы с использованием ложных данных. 22

Список использованых источникав. 24

Приложение А.. 25

Руководство пользователю.. 25

Приложение Б. 29

Листинг программы.. 29

Перечень условных обозначений и сокращений

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

Вырожденное дерево – дерево, в котором левое поддерево пусто на каждом уровне и есть только правые поддеревья (или наоборот).

Граф – совокупность непустого множества вершин и наборов пар вершин.

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

Лист – узел, не имеющий указателя ни на левое поддерево, ни на правое.

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

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

Узел – корень поддерева. Каждый узел может иметь указатель на левое и (или) правое поддерево.

БД – база данных.

ДДП – двоичное дерево поиска.

ООП – объектно-ориентированное программирование.

IP (Internet Protocol) – интернет протокол, адрес.

NET.Framework – программная платформа, основой которой является общеязыковая среда исполнения Common Language Runtime, которая подходит для разных языков программирования.

ВВЕДЕНИЕ

Каждый день мы сталкиваемся с огромными объемами информации: когда читаем книгу, смотрим фильм или же просто сидим в интернете. И с каждым днем этой информации становится все больше. То же самое и в программировании. Современные программы обрабатывают огромные объемы информации за считанные секунды. И это во многом заслуга бинарных деревьев поиска. Бинарное дерево (двоичное дерево) – иерархическая структура данных, в которой каждый узел имеет не более двух потомков [1]. Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками. Для практических целей обычно используют два подвида бинарных деревьев – двоичное дерево поиска и двоичная куча.

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

С помощью бинарных деревьев также можно представлять произвольные арифметические выражения. Каждому листу в таком дереве соответствует операнд, а каждому родительскому узлу – операция. В общем случае дерево при этом может оказаться не бинарным. Однако если число операндов любой операции будет меньше или равно двум, то дерево будет бинарным. Причем если все операции будут иметь два операнда, то нелистовые узлы такого дерева будут всегда иметь по два потомка. Заметим, что 4 основных арифметических операции как раз бинарные. Бинарные деревья могут быть использованы не только для представления выражений, но и для их вычисления. Для того чтобы выражение можно было вычислить, в листьях записываются значения операндов. Затем от листьев к корню производится выполнение операций. В процессе выполнения в узел операции записывается результат ее выполнения. В конце вычислений в корень будет записано значение, которое и будет являться результатом вычисления выражения.

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

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

Бинарные деревья и их актуальность

Назначение бинарных деревьев

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

Часто программам необходимо хранить огромные объемы информации. Это может быть гистограмма уникальных слов в файле, сортировка огромной кучи IP-адресов, с которых были установлены соединения на сокете или просто база данных адресов электронной почты. Ни массивы, ни связные списки не подходит для нужд, описанных выше. То, что нужно – это структура данных, которая хранит данные в отсортированном виде без необходимости совершать дополнительные телодвижения с простыми операциями вставки и удаления, а также эффективным поиском. Ни связный список, ни массивы не обладают такими свойствами, а потому они являются плохими решениями.

Определение бинарного дерева

Двоичным деревом поиска (ДДП) называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя [2]. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине соответствует элемент или несколько элементов, имеющие некие ключевые значения, в дальнейшем именуемые просто ключами. Обычно одной вершине соответствует один элемент, поэтому данные термины можно без потери смысла считать синонимами, хотя и надо помнить, что в некоторых реализациях это не так. Под вставкой вершины понимается добавление вершины с указанным значением элемента и присвоение указателям на родителя и потомков корректных значений. Во всех операциях сравнения элементов используется, так называемый, ключ. Ключ – это уникальное поле, которое идентифицирует конкретнй элемент в бинарном дереве. Ключи используются не только в бинарных деревьях, но и в любой качественной базе данных. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может использоваться часть данных элемента. Ключ также может храниться как отдельное значение. ДДП позволяет выполнять следующие основные операции:

– поиск вершины по ключу;

– определение вершин с минимальным и максимальным значением ключа;

– переход к предыдущей или последующей вершине, в порядке, определяемом ключами;

Двоичное дерево может быть логически разбито на уровни. Корень дерева является нулевым уровнем, потомки корня – первым уровнем, их потомки – вторым, и т.д. Глубина дерева – это его максимальный уровень. Понятие глубины также может быть описано в терминах пути, то есть глубина дерева есть длина самого длинного пути от корня до листа, если следовать от родительской вершины до потомка. Каждую вершину дерева можно рассматривать как корень поддерева, которое определяется данной вершиной и всеми потомками этой вершины, как прямыми, так и косвенными. Поэтому о дереве можно говорить, как о рекурсивной структуре. Эффективность поиска по дереву напрямую связана с его сбалансированностью, то есть с максимальной разницей между глубиной левого и правого поддерева среди всех вершин. Имеется два крайних случая – сбалансированное бинарное дерево (где каждый уровень имеет полный набор вершин) и вырожденное дерево, где на каждый уровень приходится по одной вершине. Вырожденное дерево эквивалентно связанному списку. Время выполнения всех основных операций пропорционально глубине дерева.

Таким образом, скоростные характеристики поиска в ДДП могут варьироваться от O(log₂N) в случае законченного дерева до O(N) – в случае вырожденного.

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

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

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

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

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

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

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

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

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

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

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), называется листом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Казанский Государственный Технический Университет

им. А. Н. Туполева

бинарное упорядоченное несбалансированное дерево

Выполнил: Зверев И. М.

Проверил: Рахматуллин А. И.

Код программы на языках Pascal и С++

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

Описание ведётся для кода на Pascalе, отличия для С++ будут указаны ниже.

В программе основным элементом является класс TTree. Его методы – это основные процедуры работы с деревом:

Create – конструктор класса – процедура, создающая дерево,

Add – метод добавления элемента в дерево,

Del – метод удаления элемента из дерева,

View – метод вывода элементов дерева на экран,

Exist – метод проверки существования элемента с некоторым ключом, по сути поиск элемента,

Destroy – деструктор класса – процедура, удаляющая дерево.

Рассмотрим алгоритмы работы процедур.

Create – создание дерева. Присваивает полю Root (корень) значение nil – указателя, который никуда не указывает.

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

Del – удаление элемента из дерева.

Удаление узла довольно просто если он является листом или имеет одного потомка. Например, если требуется удалить узел с ключом М надо просто заменить правую ссылку узла К на указатель на L. Трудность заключается в удалении узла с двумя потомками, поскольку мы не можем указать одним указателем на два направления.

Например, если просто удалить узел с ключом N, то левый указатель узла с ключом Т должен указывать одновременно на К и R что не возможно. В этом случае удаляемый узел нужно заменить на другой узел из дерева. Возникает вопрос, каким же узлом его заменить? Этот узел должен обладать двумя свойствами: во-первых, он должен иметь не более одного потомка; во-вторых, для сохранения упорядоченности ключей, он должен иметь ключ либо не меньший, чем любой ключ левого поддерева удаляемого узла, либо не больший, чем любой ключ правого поддерева удаляемого узла. Таким свойствам обладают два узла, самый правый узел левого поддерева удаляемого узла и самый левый узел его правого поддерева. Любым из этих узлов им можно заменить удаляемый узел. Например, на рисунке это узлы М и Р.

Необходимо различать три случая:

Узла с ключем, равным х, нет.

Узел с ключем, равным х, имеет не более одного потомка.

Узел с ключем, равным х, имеет двух потомков

Вспомогательная рекурсивная процедура del вызывается только в случае, когда удаляемый узел имеет двух потомков. Она “спускается вдоль” самой правой ветви левого поддерева удаляемого узла q^ (при вызове процедуры ей передается в качестве параметра указатель на левое поддерево) и, затем, заменяет существенную информацию (в нашем случае ключ data) в q^ соответствующим значением самого правого узла r^ этого левого поддерева, после чего от r^ можно освободиться.

View - печать дерева, обходя его справа налево. Чем дальше элемент от корня, тем больше ему будет предшествовать пробелов, т. о. путём несложного алгоритма получается вполне удобно читаемое дерево.

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

Destroy – удаление дерева. Обходя дерево слева направо, удаляет элементы. Сначала удаляются потомки узла, затем сам узел.

Различия между описаниями кодов программах на разных языках относятся в основном к конструкторам и деструкторам. В .pas программах они определяются директивами и вызываются явно как методы класса из программы, а в .cpp конструктор вызывается при создании элемента класса и деструктор автоматически при выходе из программы (для чего объект класса размещается в памяти динамически).

Содержание

Введение 5
1. Общие сведения о бинарных деревьях 6
2.Описание интерфейса программы. 10
Заключение 11
Список использованных источников 12

Прикрепленные файлы: 1 файл

Курсач.doc

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

Учреждение высшего профессионального образования

Кубанский государственный технологический университет

(ФБГОУ ВПО КубГТУ)

Факультет компьютерных технологий и автоматизированных систем

Кафедра информационных систем и программирования

на тему: Исследование алгоритма поиска на бинарном дереве 1

(тема курсового проекта (работы))

Выполнил студент группы 13-СМ-231000 2

Дердерян Андрей Аиквич_____________________

Допущен к защите________________________ _______________________

Руководитель работы О.Б Попова

Защищен _______________________ Оценка _______________________

Члены комиссии а

(подпись, дата, расшифровка подписи)

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное

Учреждение высшего профессионального образования

Кубанский государственный технологический университет

(ФБГОУ ВПО КубГТУ)

Факультет компьютерных технологий и автоматизированных систем

Кафедра информационных систем и программирования

Зав. кафедрой ИСП 1

на курсовую работу

Студенту: Дердерян Андрей Аиквич группы 13-СМ-2310 1 курса

Факультета МИППС 1

Направление 231000 Программная инженерия 1

(шифр и наименование)

Тема проекта: Исследование алгоритма поиска на бинарном дереве.

Содержание задания: Разобрать принцип работы алгоритма поиска на бинарном дереве.

Объем курсовой работы:

а) пояснительная записка 16 с.

Рекомендуемая литература: Информатика Программирование (Т.А. Павловская) Практическое программирование. Приемы создания программ на языке Паскаль 1

Руководитель работы ______________________________ ______ О.Б Попова

Задание принял студент ______________________________ _ Дердерян А.А.

Пояснительная записка курсовой работе 16 с., 8 рис., 5 источника.

ДЕРЕВО, ОБХОД, КОРЕНЬ, УЗЕЛ, ВИДЫ ДЕРЕВЬЕВ, БИНАРНОЕ ДЕРЕВО, ПОИСК В БИНАРНОМ ДЕРЕВЕ, ВИДЫ ОБХОДА, ПРОГРАММИРОВАНИЕ, ЯЗЫКЕ ПРОГРАММИРОВАНИЯ, PASCAL ABC.

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

Цель работы: закрепление основ и углубление знаний в области информатики и программирования, разработка алгоритма обхода дерева, получение дополнительных практических навыков и приемов работы средствами Pascal ABC.

Введение

Построить бинарное дерево поиска целочисленного типа данных. Выполнить обход дерева сверху вниз (корень - левое поддерево - правое поддерево). При обходе подсчитать:

a) количество вершин, имеющих хотя бы одну ненулевую связь;

б) количество вершин, имеющих две ненулевые связи;

в) количество вершин, имеющих не более одной ненулевой связи.

1. Общие сведения о бинарных деревьях

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

Рис.1 "Пример бинарного дерева"

На рисунке показан общепринятый способ изображения бинарного дерева. Это дерево состоит из семи узлов, и А-кореня дерева. Его левое поддерево имеет корень В, а правое - корень С. Это изображается двумя ветвями, исходящими из А: левым - к В и правым - к С. Отсутствие ветви обозначает пустое поддерево. Например, левое поддерево бинарного дерева с корнем С и правое поддерево бинарного дерева с корнем Е оба пусты. Бинарные деревья с корнями D, G, Н и F имеют пустые левые и правые поддеревья.

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

Узел nl - предок узла n2 (а n2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2.

Узел n2-левый потомок узла n1, если n2 является либо левым сыном n1, либо потомком левого сына n1. Похожим образом может быть определен правый потомок.

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

Рис.2 "Строго бинарное дерево"

Уровень узла в бинарном дереве может быть определен следующим образом. Корень дерева имеет уровень 0, и уровень любого другого узла дерева имеет уровень на 1 больше уровня своего отца. Например, в бинарном дереве на первом рисунке узел Е - узел уровня 2, а узел Н-уровня 3. Глубина бинарного дерева - это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева. Стало быть, глубина дерева на первом рисунке равна 3.

Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые левое и правое поддеревья. На рисунке приведен пример полного бинарного дерева.

Рис.3 "Полное бинарное дерево"

Почти полное бинарное дерево - это бинарное дерево, для которого существует неотрицательное целое k такое, что:

1. Каждый лист в дереве имеет уровень k или k+1.

2. Если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.

Есть еще одна разновидность бинарных деревьев, которая называется дерево поиска. Это двоичное дерево организовано так, что для каждой вершины справедливо утверждение, что все ключи левого поддерева меньше ключа , а все ключи правого поддерева больше его, то такое дерево будем называть деревом поиска. В таком дереве легко обнаружить заданный элемент, для этого достаточно, начав с корня, двигаться к левому или правому поддереву на основании лишь одного сравнения с ключом текущей вершины. Дерево поиска для заданной последовательности целых чисел 23, 17, 26, 32, 18, 6, 2, 5, 8, 29, 146 имеет вид:

Рис.4 "Бинарное дерево писка"

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

Существует 3 способа обхода бинарного дерева.

в прямом порядке

в симметричном порядке

в обратном порядке

В прямом порядке:

Попасть в корень

Пройти в прямом порядке левое поддерево

Пройти в прямом порядке правое поддерево

В симметричном порядке:

Пройти в симметричном порядке левое поддерево

Попасть в корень

Пройти в симметричном порядке правое поддерево

В обратном порядке:

Пройти в обратном порядке левое поддерево

Пройти в обратном порядке правое поддерево

Попасть в корень

Рис.5"Пример обхода бинарного дерева разными способами"

Прямой порядок: ABDGCEHIF

Симметричный порядок: DGBAHEICF

Обратный порядок: GDBHIEFCA

бинарное дерево программа поиск

2.Описание интерфейса программы.

При запуске программы пользователь увидит форму с полем для ввода количества элементов дерева (Рис.5).

Рис.6 "Рабочее окно программы"

Затем поочередно вводим необходимые данные (Рис.7).

Рис.7 "Ввод данных"

Рис.8 "Вывод результата работы программы на экран"

После нажатия Enter программа будет выдавать графическое представление дерева, а также искомые величины. (Рис.8)

Заключение

В данной курсовой работе была создана программа в среде Pascal ABC, которая позволяет создавать бинарное дерево и выполнять с ним следующие операции: добавлять элементы дерева, выводить дерево на экран, выполнять обход дерева сверху вниз. При обходе подсчитывать: количество вершин, имеющих хотя бы одну ненулевую связь, количество вершин, имеющих две ненулевые связи, количество вершин, имеющих не более одной ненулевой связи. Были описаны алгоритмы выполнения этих операций. Для решения этой задачи была прочитана соответствующая литература. Я приобрел опыт в работе с компонентами среды Pascal ABC, и познакомилась с некоторыми приемами программирования.

Список использованных источников

1. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2007.

2. Бежанова М. М, Москвина Л.А. Практическое програмирование. Приемы создания программ на языке Паскаль. М. Научный Мир. 2000. - 270 с.

3. Подвальный С.Л., Холопкина Л.В., Носачева М.П. Программирование на языке паскаль: практикум. Воронеж. ГОУВПО ВГТУ. 2008.

Читайте также: