Визуализация бинарного дерева поиска

Фрагмент работы:

1.4 Описание алгоритмов программы

Данная программа реализует такие операции (рис. А.1 – А.3) над «Бинарным деревом» как:

добавление элемента;

поиск (введенного элемента, минимального элемента, максимального элемента);

удаление элемента.

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

Также программа реализует несколько способов создания «Бинарного дерева»:

создание пустого дерева;

создание дерева с числами, записанными в текстовый файл;

создание дерева со случайными числами.

1.4.1 Создание дерева

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

1.4.2 Добавление элемента

Для того, чтобы иметь возможность вставить элемент в «Бинарное дерево», необходимо выбрать родительский узел, к которому будет присоединён новый узел в качестве дочернего. [2]

Алгоритм добавления в дерево заключается в следующем: если мы имеем пустое дерево, то мы заменим его на дерево с одним корневым узлом и остановимся. Иначе мы сравним введенное значение со значением корневого узла. При этом если введенное значение больше значения корневого узла, то мы рекурсивно добавим введенное значение в правое поддерево. Если значение корневого узла больше, то рекурсивно добавим в левое поддерево. Иначе, если значение коревого узла равно введенному значению, то операция добавления завершается, так как данное значение уже присутствует в «Бинарном дереве». [4]

1.4.3 Поиск элемента

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

Алгоритм поиска элемента в дереве заключается в следующем: если дерево пусто, то сообщить, что узел не найден и остановиться. Иначе сравнить введенное значение со значением корневого узла. Если введенное значение равно значению корневого узла, то вернуть ссылку на этот узел и остановиться. Иначе, если введенное значение больше значения корневого узла, то рекурсивно производится поиск значения в правом поддереве. Если значение корневого узла больше, то рекурсивно производим поиск в левом поддереве. [5]

1.4.4 Поиск минимального элемента

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

1.4.5 Поиск максимального элемента

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

 

1.4.6 Удаление элемента

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

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

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

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

Список использованной литературы:

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

 

Основная

Бакнелл Дж. Фундаментальные алгоритмы и структуры данных в C++. Библиотека программиста. – М.: ООО «ДиаСофтЮП»; СПб Питер, 2006.

Вирт Н. Алгоритмы и структуры данных: Пер. с англ. – М.: Мир, 1980.

Двоичное дерево поиска – Википедия [Электронный ресурс] - ru.wikipedia.org/wiki/Двоичное_дерево_поиска - (дата обращения: 02.05.2017).

Бинарные деревья поиска и рекурсия – это легко [Электронный ресурс] - habrahabr.ru/post/267855/ - (дата обращения: 01.06.2017).

Алгориты и структуры данных для начинающий: двоичное дерево поиска [Электронный ресурс] - https://tproger.ru/translations/binary-search-tree-for-beginners/ - (дата обращения: 25.05.2017).

 

 

Дополнительная

Суворов К.А., Черемных М.Н. Справочник C++. Базовые классы. –СПб:БХВ-Петербург, 2004.

Дарахвелидзе П.Г., Марков Е.П. C++- среда визуального программирования: – СПб.:- Санкт –Петербург, 1996.

Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования. – Харьков: Фолио; Ростов н/Д:Феникс, 1997.

Фаронов В.В. C++ 6. Учебный курс.-М.: Издатель Молгачева С.В.,2001.

Киммел, Пол. Создание приложений в C++. – М.: Издательский дом ”Вильямс”, 2003.

Цена сегодня: 50.00 бел.руб.

---

Вы находитесь на сайте как незарегистрированный пользователь.
Для покупки работы Вам необходимо заполнить все поля ниже: