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

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

Электронный учебный материал для студентов всех специальностей факультета Прикладная информатика Кубанского государственного аграрного университета

• Главная
• Лекции
  • курс лекций для ИСиТ
  • Курс лекций для БИ
  • Курс лекций для ПИ
  • Презентации
  • Темы лабораторных работ
  • Темы курсовых работ
  • Пример выполнения курсовой работы
  • Вопросы к экзамену ПИ
  • Вопросы к экзамену ИСиТ
  • Вопросы к экзамену БИ

  Поиск

  Об авторах

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

  Основные цели сайта

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

  Нелинейные связанные структуры

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

  

  LST1 — указатель на начало первого списка (ориентированного указателемями PTR1). Он линейный и состоит из 5-и элементов.

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

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

  Можно выделить 3 признака отличия нелинейной структуры:

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

  2) На данный элемент структуры может ссылаться любое число других элементов этой структуры.

  3) Ссылки могут иметь вес, то есть подразумевается иерархия ссылок.

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

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

  

  Входной сигнал в систему это X. Реакцией на входной сигнал является выработка выходного сигнала Y и переход в соответствующее состояние.

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

  Для реализации вышесказанного:

  1) должен быть создан список, отображающий состояния системы (1, 2, 3);

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

  Реализация графа в виде нелинейного списка можно представить рисунка ниже:

  

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

  Рекурсивные структуры данных.

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

  Рекурсия — процесс, протекание которого связано с обращением к самому себе (к этому же процессу).

  Пример рекурсивной структуры данных — структура данных, элементы которой являются такими же структурами данных

  

  Деревья

  Дерево — нелинейная связанная структура данных

  Дерево характеризуется следующими признаками:

  — дерево имеет один элемент, на который нет ссылок от других элементов. Этот элемент называется корнем дерева;

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

  — каждый элемент дерева связан только с одним предыдущим элементом.

  Любой узел дерева может быть промежуточным либо терминальным (листом). На рисунке промежуточными являются элементы M1, M2; листьями — A, B, C, D, E. Характерной особенностью терминального узла является отсутствие ветвей.

  Количество ветвей, растущих из узла дерева, называется степенью исхода узла (на рисунке для M1 степень исхода 2, для М2 — 3).

  Для описания связей между узлами дерева применяют также следующую терминологию: М1 — “отец” для элементов А и В. А и В — “сыновья” узла М1.

  1) если максимальная степень исхода равна m, то это — m-арное дерево;

  2) если степень исхода равна либо 0, либо m, то это — полное m-арное дерево;

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

  4) если степень исхода равна либо 0, либо 2, то это — полное бинарное дерево.

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

  

  Бинарные деревья

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

  Бинарные деревья являются наиболее используемой разновидностью деревьев.

  Формат элемента бинарного дерева представлен на рисунке ниже

  

  Функция создания элемента бинарного дерева V = MakeTree (key, rec)

  V — указатель на создаваемый элемент динамической структуры

  Алгоритм функции Maketree(key,rec)

  Операция V = MakeTree(Key, Rec) — создает элемент (узел дерева) с двумя указателями и двумя полями (ключевым и информационным) .

  Упорядочное бинарное дерево

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

  Построим бинарное дерево из следующих элементов: 50, 46, 61, 48, 29, 55, 79.

  

  Получено идеально сбалансированное дерево — дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не более чем на единицу.

  Сведение m-арного дерева к бинарному

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

  2.Соединяются горизонтальными линиями все сыновья одного родителя.

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

  Графическое пояснение алгоритма

  

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

  

  • Лекция 1. Понятие структуры данных. Статические структуры данных
  • Лекция 2. Статические и полустатические структуры данных
  • Лекция 3. Полустатические очереди
  • Лекция 4. Понятие динамических структур данных. Связные списки
  • Лекция 5. Реализация стеков и очередей с помощью односвязных списков
  • Лекция 6. Односвязный список как самостоятельная структура данных.
  • Лекция 7. Нелинейные связанные структуры. Деревья. Бинарные деревья
  • Лекция 8. Основные операции с деревьми
  • Лекция 9. Поиск. Классификация основных видов поиска
  • Лекция 10. Методы оптимизации поиска
  • Лекция 11. Дерево оптимального поиска
  • Лекция 12. Поиск по бинарному дереву со вставкой
  • Лекция 13. Поиск по бинарному дереву с удалением
  • Лекция 14. Понятие сортировки. Внутренняя и внешняя сортировки
  • Лекция 15. Прямые методы сортировки.
  • Лекция 16. Улучшенные методы сортировки. Сортировка Шелла
  • Лекция 17. Быстрая сортировка. Оценка эффективности различных методов сортировки

  Источник

  9. Нелинейные структуры данных

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

  Граф

  Самым привычным примером графа служит карта автодорог, на которой изображены перекрестки и связывающие их дороги. Перекрестки являются вершинами графа, а дороги — его ребрами. Иногда наши графы ориентированы (подобно улицам с односторонним движением) или взвешены — каждой дороге приписана стоимость путешествия по ней (если, например, дороги платные). Граф — это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта. Как многосвязная структура граф обладает следующими свойствами: 1. на каждый элемент (узел, вершину) может быть произвольное количество ссылок; 2. каждый элемент может иметь связь с любым количеством других элементов; 3. каждая связка (ребро, дуга) может иметь направление и вес. Обычно информацию о графах хранят двумя способами: 1. в виде матрицы примыканий (смежностей); 2. в виде списка примыканий (смежностей). Матрица примыканий AdjMat графа G = (V, E) с числом вершин записывается в виде двумерного массива размером N х N. В каждой ячейке [i,j] этого массива записано значение 0 за исключением лишь тех случаев, когда из вершины Vi в вершину Vj ведет ребро, и тогда в ячейке записано значение 1.

  1,		если	v i v j E
  						(9.1).
  AdjMat [ i , j ] =	0,	если	v v	E
  j
  	i

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

  (A)	(B)	(C)	(D)
  A	B	(A)	0	1	0	1
  (B)	1	0	1	1
  D	C	(C)	0	1	0	1
  		(D)	1	1	1	0
  A	B						(A)	(B)	(C)	(D)
  		(A)	0	1	0	0
  (B)	0						0	1	1
  D	C	(C)	0	0	0	1
  (D)	1	0	1	0

  Рисунок 9.1. – Представление графа в виде матрицы примыканий

  50 Список примыканий AdjList графа G = (V,E) с числом вершин V = N записывается в виде одномерного массива длины N, каждый элемент которого представляет собой ссылку на список (см. рис. 9.2).

  B C A C D A B E B E C D

  Бинарное дерево

  Дерево – это граф, который характеризуется следующими свойствами: 1. Существует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент и который называется “корнем”. 2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры. 3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем. Наиболее простой разновидностью деревьев являются бинарные деревья. Это такие деревья, у каждой вершины которых, имеется от 0 до 2 дочерних вершин. В памяти ЭВМ деревья можно представлять с помощью связных списков и массивов (или последовательных списков). Чаще всего используется связное представление деревьев, т.к. оно очень сильно напоминает логическое. Связное хранение состоит в том, что задается связь от родительской вершины к дочерней. У каждого элемента бинарного дерева имеется два указателя, поэтому удобно узел представить в виде трёхэлементной структуры (см. рис. 9.3). Рисунок 9.3. – Структура элемента бинарного дерева

  Задание

  1. Разработайте программу позволяющую хранить информацию об ориентированном графе произвольного размера. Программа должна содержать процедуры: 1. Добавления вершины в граф.

  51 2. Удаления вершины из графа. 3. Вывода информации о составе графа. 4. Сохранения (чтения) данных в файл. Программа должна позволять пользователю выбирать формат хранения данных (матрица примыканий или список примыканий). 2. Разработайте программу позволяющую хранить информацию об иерархической структуре в формате бинарного дерева. Программа должна содержать процедуры: 1. Добавления вершины в произвольное место дерева. 2. Удаления вершины (и всех дочерних элементов) из дерева. 3. Вывода информации о составе дерева. 4. Сохранения (чтения) данных в файл. Примечание : разработанная на данном занятии программа (хранящая информацию об ориентированном графе) будет востребована на лабораторной работе на тему “Алгоритмы на графах”. Поэтому при проектировании формата хранения данных о вершине графа целесообразно предусмотреть дополнительное поле логического типа. В нём мы станем содержать информацию о факте посещения вершины графа при реализации алгоритмов обхода в глубину, обхода по уровням, и т.д. Примечание : при выполнении первого задания вам может помочь компонент TStringGrid . Указанный компонент описан в приложении к данному пособию.

  Источник

  Читайте также:  Домашний цветок долларовое дерево размножение