Ирина Эланс

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

Бинарное упорядоченное дерево

Министерство образования и науки Украины

Харьковский государственный университет строительства и архитектуры

Кафедра компьютерного моделирования и информационных технологий

ТЕМА

БИНАРНОЕ УПОРЯДОЧЕННОЕ ДЕРЕВО

Пояснительная записка

по курсовому проекту

по дисциплине

МОДЕЛИ И СТРУКТУРЫ ДАННЫХ

Выполнила: Чернышева М.,

студентка гр.ЭКБ-22

Руководитель: Литвиненко Е.Н.

Харьков 2009

СОДЕРЖАНИЕ:

ВВЕДЕНИЕ……………………………………………………………………….3

ПОСТАНОВКА ЗАДАЧИ……………………………………………………….4

РАЗДЕЛ 1

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

РАЗДЕЛ 2

Алгоритмическая часть…………………………………………………….11

РАЗДЕЛ 3

Техническое задание……………………………………………………….16

РАЗДЕЛ 4

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

3.1.Описание программного обеспечения……………………………...17

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

ВЫВОДЫ………………………………………………………………………..26

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ……………………………27

ПРИЛОЖЕНИЕ А………………………………………………………………28

ВВЕДЕНИЕ

В данной курсовой работе разработана программа для работы с бинарным упорядоченным деревом. Программа была создана в среде Borland Delphi 7.

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

ПОСТАНОВКА ЗАДАЧИ

Написать программу создания, вывода и обработки бинарного дерева Т, которая выполняет следующие функции:

а) определяет, есть ли в дереве Т хотя бы два одинаковых элемента;

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

РАЗДЕЛ 1.Общие сведения о бинарных деревьях

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

Рис.1.1 «Пример бинарного дерева»

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

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

Узел nl -предок узла n2 (а n2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2. Например, в дереве из рисунке А-предок G и Н-потомок С, но Е не является ни предком, ни потомком С.

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

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

Рис.1.2 «Строго бинарное дерево»

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

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

Рис.1.3 «Полное бинарное дерево»

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

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

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

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

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

Начало поиска места

Для записи с ключом «12»

указатель корня

Сюда будет включена запись «12»

Рис.1.4 «Упорядоченное бинарное дерево»

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.1.5.

«Пример обхода бинарного дерева разными способами»

Применение

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

РАЗДЕЛ 2.Алгоритмическая часть

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

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

Да Нет

Нет

Да

Рис. 2.1 «Алгоритм добавления нового элемента в дерево»

2.Удаление элемента. Если узел – лист, просто удаляем его, если узел имеет одного потомка, заменяем узел им, если же узел имеет двух потомков, то реализуется алгоритм, представленный на Рис.2.2, который заменяет удаляемый узел самым правым потомком его левого поддерева.

Да

Нет

Рис. 2.2 «Алгоритм удаления узла, имеющего двух потомков»

да

Нет

Да

Нет

Да

Нет

Да

Нет

Да

Нет

Рис. 2.3 «Алгоритм удаления узла из дерева»

3.Поиск одинаковых элементов. Сперва записываем все элементы дерева в строку, а затем реализуем алгоритм поиска одинаковых элементов в данной строке.

Да

Нет

Да

Да Нет

Рис.2.4 «Поиск одинаковых элементов в дереве»

4.Нахождение длины пути от корня до заданной вершины. Ищем заданный элемент в дереве, увеличивая «счетчик уровня» на 1 при каждом переходе к потомку узла.

Да Нет

Да

Нет

Да

Нет

Рис. 2.5 «Алгоритм нахождения длины пути от корня до заданной вершины»

РАЗДЕЛ 3.Техническое задание

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

Основанием для выполнения данной курсовой работы является учебный план по дисциплине «Модели и структуры данных» ХГТУСА.

3.2.Назначение разработки.

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

3.3.Требования к программному обеспечению.

а) программа должна выполнять следующие операции над бинарным деревом: добавлять в него элементы, удалять элементы, находить длину пути от корня до ближайшей вершины, определять, есть ли в дереве одинаковые элементы, выводить дерево на экран;

б) время ответа <=1 секунды;

в) тип операционной системы: Windows 98/2000/XP;

г) для запуска программы требуется Borland Delphi 7, каких-либо дополнительных приложений для своей работы программа не требует;

д) процессор Pentium или Celeron с тактовой частотой не ниже 166 МГц, оперативной памяти 256 Мбайт;

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

3.4. Этапы разработки.

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

б) разработка алгоритмов реализации операций, необходимых для выполнения данного задания;

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

г) реализация уже готовых алгоритмов на языке программирования Delphi, создание программы;

д) тестирование программы и устранение неполадок.

РАЗДЕЛ 4. Описание программы

4.1.Описание программного обеспечения

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

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

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

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

Prosmotr – метод вывода элементов дерева на экран;

Find – метод поиска длины пути от корня до заданной вершины;

Check – метод проверки дерева на наличие одинаковых элементов;

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

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

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

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

Да Нет

Нет

Да

Рис. 4.1.1 «Блок-схема процедуры Add, добавляющей новый элемент»

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

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

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

Бинарное упорядоченное дерево 📙 Курсовая → 🆔 40130