- •Оглавление
- •Введение
- •Основные понятия и определения
- •Встроенные структуры данных(Pascal/с)
- •Варианты индивидуальных заданий на Pascal
- •Варианты индивидуальных заданий на c
- •Простые типы данных в Pascal
- •Вещественные типы
- •Вещественные типы языка Pascal
- •Сложный тип
- •Простые типы данных в с Целые типы
- •Целые типы языка c
- •Диапазоны значений целых типов языка c
- •Символьный тип
- •Перечисляемый тип
- •Вещественные типы
- •Вещественные типы языка c
- •Структурированные типы данных в Pascal Массив
- •Структура данных типа «запись»
- •Структура данных типа «множество»
- •Структурированные типы данных в c Структура данных типа «массив»
- •Структура данных типа «структура»
- •Производные структуры данных. Структура данных «строка» (Pascal/c)
- •Задание
- •Варианты индивидуальных заданий
- •Варианты задач
- •Варианты форматов
- •Назначение процедур и функций в модулях реализации сд типа строка в Pascal
- •Назначение процедур и функций в модулях реализации сд типа «строка» в c
- •Сравнительный анализ методов сортировки (Pascal/c)
- •1. Изучить временные характеристики алгоритмов.
- •6. Выводы по работе.
- •1. Выбираем элемент массива в качестве разделителя (например, первый).
- •Массив м
- •Массив м
- •Примеры программной реализации алгоритмов сортировки на языке Pascal
- •Примеры программной реализации алгоритмов сортировки на языке c
- •Сравнительный анализ алгоритмов поиска (Pascal/c)
- •Максимальное количество операций сравнения
- •Среднее количество операций сравнения
- •Алгоритмы поиска в неупорядоченных массивах Алгоритм линейного поиска
- •Алгоритм быстрого линейного поиска
- •Анализ алгоритмов линейного поиска
- •Алгоритмы поиска в упорядоченных массивах Алгоритм быстрого линейного поиска
- •Алгоритм бинарного поиска
- •Анализ алгоритма бинарного поиска
- •Алгоритм блочного поиска
- •Анализ алгоритма блочного поиска
- •Структуры данных «линейные списки» (Pascal/с)
- •Варианты индивидуальных заданий
- •Назначение процедур и функций
- •Структуры данных «стек» и «очередь» (Pascal/с)
- •Результаты работы программы
- •Варианты индивидуальных заданий
- •Варианты задач
- •Модули для реализации стека
- •Модули для реализации очереди
- •Очередь
- •Структуры данных «дерево» (Pascal/с)
- •Варианты индивидуальных заданий
- •Варианты задач
- •Назначение процедур и функций:
- •Принципы размещения бинарного дерева в памяти эвм
- •Алгоритмы обхода бинарного дерева
- •Обход бинарного дерева «в глубину» (в прямом порядке)
- •Обход бинарного дерева «в ширину» (по уровням)
- •Обход бинарного дерева в симметричном порядке
- •Обход бинарного дерева в обратном порядке
- •Алгоритмы формирования бинарного дерева
- •Рекурсивный алгоритм формирования бинарного дерева «в глубину»
- •Итеративный алгоритм формирования бинарного дерева «в глубину»
- •Алгоритм формирования бинарного дерева «в ширину»
- •Алгоритм формирования бинарного дерева «снизу вверх»
- •Рекурсивный алгоритм формирования бинарного дерева
- •Итеративный алгоритм формирования бинарного дерева
- •Алгоритм формирования бинарного дерева минимальной высоты
- •Итеративный алгоритм формирования сбалансированного бинарного дерева
- •Представление алгебраических выражений бинарными деревьями
- •Алгоритм формирования бинарного дерева по прямой польской записи
- •Алгоритм формирования бинарного дерева по обратной польской записи
- •Структуры данных «таблица» (Pascal/с)
- •Варианты индивидуальных заданий
- •Библиографический список
Алгоритмы формирования бинарного дерева
Для того, чтобы сформировать в памяти ЭВМ БД, необходимо представить его в виде последовательности информационных частей вершин БД. Такую последовательность можно получить в результате обхода БД. Последовательность, полученная в результате обхода, неоднозначно определяет БД, т.к. не содержит информации о наличии сыновей у вершин БД. Чтобы получить такую информацию, введем в БД фиктивные вершины (с символом «.» в информационной части). Такие вершины соответствуют несуществующим сыновьям вершин БД. БД (см. рис.21) с фиктивными вершинами представлено на рис.25.
уровень 0
уровень 1
. уровень 2
. . уровень 3
. . . . . . . . уровень 4
Рис.25. БД с фиктивными вершинами
При обходе БД (см. рис.25) в прямом порядке получим последовательность: ABCD..E..F..G.HI..J.. Из полученной последовательности следует, что вершины A,B,C,D и H имеют по два сына, причем левый сын записан непосредственно за отцом, вершины D,E,F,I и J — листья (за ними следуют две точки), вершина G не имеет левого сына (одна точка за этой вершиной), а правый сын — H.
Сформировать БД исходя из данной последовательности можно рекурсивным и итеративным способом, причем БД будет строиться «в глубину».
Рекурсивный алгоритм формирования бинарного дерева «в глубину»
1. Прочитать очередной символ последовательности.
2. Если прочитанный символ точка, то БД пустое, иначе создать корень, записать в него символ, построить левое поддерево, построить правое
поддерево.
Итеративный алгоритм формирования бинарного дерева «в глубину»
1. Инициализировать стек.
2. Прочитать очередной символ последовательности.
3. Если прочитанный символ точка, то БД пустое, иначе создать корень, записать в него символ, корень поместить в стек.
4. Пока стек не пуст, выполнять п.5.
5. Прочитать символ, извлечь вершину из стека. Если для вершины левое поддерево не построено, то построить его в соответствии с п.6, если не построено правое поддерево, то построить его в соответствии с п.7.
6. Если символ точка, то левое поддерево пустое, вернуть вершину в стек, иначе создать корень левого поддерева, записать в него символ, вернуть в стек вершину, созданный корень поместить в стек.
7. Если символ точка, то правое поддерево пустое, иначе создать корень правого поддерева, записать в него символ, созданный корень поместить в стек.
Если при прохождении БД (см. рис.21) в прямом порядке сначала дерево, а потом все поддеревья заключать в скобки, то получим скобочное представление БД:
(A(B(C(D()())(E()()))(F()()))(G()(H(I()())(J()())))
Скобочное представление БД можно использовать в качестве исходных данных для формирования БД «в глубину», если пару символов ‘()’ считать точкой, а остальные скобки игнорировать.
При обходе БД (см. рис.25) «в ширину» получим последовательность: ABGCF.HDE..IJ. . . . . . . .
Используя эту последовательность в качестве исходных данных можно сформировать БД, применив алгоритм формирования БД «в ширину».