Материал: АиСД. Практикум (in dev)
снизу вверх: AB+CD-* (концевой порядок).
Рис.3. Бинарное дерево
Ниже приведены программы для создания в памяти ПЭВМ списковой структуры бинарного дерева (процедура CREATE) и обхода его узлов в порядке сверху вниз. (процедура PREORDER)
-
Формирование бинарного дерева
Листинг 1.
ТУРЕ { ОПИСАНИЕ ДЕРЕВА }
NODE = ^TREE; { ТИП УКАЗАТЕЛЯ УЗЛА ДЕРЕВА }
TREE = RECORD { СТРУКТУРА УЗЛА БИНАРНОГО ДЕРЕВА }
LEFT :^TREE; { УКАЗАТЕЛЬ ЛЕВОГО ПОДДЕРЕВА }
RIGHT :^TREE; { УКАЗАТЕЛЬ ПРАВОГО ПОДДЕРЕВА }
IDENT : CHAR; { ИДЕНТИФИКАТОР УЗЛА ПЕРЕВА }
END; PROCEDURE CREATE(VAR A:NODE);
{ РЕКУРСИВНАЯ ПРОЦЕДУРА СОЗДАНИЯ В ОПЕРАТИВНОЙ ПАМЯТИ
СТРУКТУРЫ БИНАРНОГО ДЕРЕВА В ПЕРЕМЕННОЙ "А" ФОРМИРУЕТСЯ АДРЕС КОРНЯ ПОЛУЧЕННОГО ДЕРЕВА ИЛИ ПОДДЕРЕВА }
VAR
В : NODE; { АДРЕС ПОДДЕРЕВА ДАННОГО УЗЛА }
R : CHAR; { РАБОЧАЯ ПЕРЕМЕННАЯ }
BEGIN
NEW(A); { РЕЗЕРВИРОВАНИЕ ПАМЯТИ ДЛЯ НОВОГО УЗЛА ДЕРЕВА } WRITE(‘ ВВЕДИТЕ ИМЯ УЗЛА> ’);
READLN(A^.IDENT);
WRITE(‘ ЕСТЬ ЛЕВОЕ ПОДДЕРЕВО У УЗЛА ‘,А^.IDENT,’ ? (Y/N) ‘);
READLN(R); IF (R='Y') THEN
BEGIN
CREATE(B); { ФОРМИРОВАНИЕ ЛЕВОГО ПОДДЕРЕВА УЗЛА }
A^.LEFT:=B;
END ELSE
A^.LEFT:=NIL; { У ДАННОГО УЗЛА НЕТ ЛЕВОГО ПОДДЕРЕВА }
WRITE(‘ ЕСТЬ ПРАВОЕ ПОДДЕРЕВО У УЗЛА ’,A^.IDENT,’ ? (Y/N) ‘);
READLN(R);
IF (R='Y') THEN BEGIN
CREATE(В); { ФОРМИРОВАНИЕ ПРАВОГО ПОДДЕРЕВА УЗЛА }
A^.RIGHT:=B; END ELSE
A^.RIGHT:=NIL; { У ДАННОГО УЗЛА НЕТ ПРАВОГО ПОДДЕРЕВА } END;
-
Рекурсивная процедура обхода узлов дерева сверху-вниз
Листинг 2.
PROCEDURE PREORDER(A:NODE);
BEGIN
IF A<>NIL THEN BEGIN
WRITE(A^.IDENT:2); { ПЕЧАТЬ ИДЕНТИФИКАТОРА УЗЛА } PREORDER(A^.LEFT); { ОБХОД ЛЕВОГО ПОДДЕРЕВА }
PREOROER(A^.RIGHT); { ОБХОД ПРАВОГО ПОДДЕРЕВА }
END; END;
В процедуре CREATE функция NEW(A) резервирует в памяти ПЭВМ область для размещения записи типа TREE. В операторе вводится идентификатор текущего узла дерева (один символ) и заносится в поле IDENT записи, адрес которой в данный момент хранятся в переменной A. Далее на экран выдается запрос, есть ли левое поддерево у данного узла. Если в ответ введён символ Y (да), то рекурсивно вызывается процедура CREATE для формирования левого поддерева. После ее завершения в переменной B возвращается адрес узла – корня левого поддерева и он запоминается в поле LEFT текущей записи.
Аналогично формируется правое поддерево. Выход из рекурсии происходит при обработке концевых вершин дерева. В записи, представляющей эти узлы, в поля LEFT и RIGHT заносится константа NIL - неопределенный адрес.
Если проанализировать последовательность прохождения узлов в порядке сверху вниз, то можно установить следующее. Для любого узла, например *, сначала фиксируется факт прохождения через данный узел, затем просматриваются все узлы, входящие в его левое поддерево, а в последнюю очередь просматриваются узлы,
составляющие его правое поддерево. Тогда алгоритм обхода бинарного дерева в порядке сверху вниз имеет следующий вид.
Шаг I. Посетить корень дерева (напечатать его идентификатор),
Шаг 2. Пройти сверху вниз левое поддерево корневого узла.
Шаг 3. Пройти сверху вниз правое поддерево.
Описанный алгоритм реализуется в приведенном примере рекурсивной процедурой. Условие A ≠ NIL позволяет обнаружить концевые вершены дерева и обеспечивает выход из рекурсии.
В основной программе выполняется последовательное обращение к описанным выше подпрограммам создания и обхода бинарного дерева. Заметим, что начальное значение переменной указателя ROOT определяется в процедуре CREATE. Это значение используется для указания адреса корневого узла сформированного бинарного дерева при обращении к процедуре обхода его узлов в порядке сверху вниз.
-
Лабораторное задание
Для проведения лабораторной работы необходимо выполнить следующие действия.
I). Исследовать работу стека, очереди и дека , определив алгоритмы работы указанных структур данных . Результаты записать в тетрадь.
Используя программу DataStruct , задать исходное множество элементов, содержащее
12- 15 элементов.
Система работает в диалоговом режиме с использованием “меню”. Вся необходимая информация во время работы системы отображается на экране дисплея и не требует специальных пояснений.
2). сформировать бинарные деревья , содержащие 8, 10 , 12 элементов и выполнить для каждого из них три вида обхода дерева.
3). Составить и отладить программу итеративного и рекурсивного алгоритмов вычисления суммы.
n
∑ i
i=1
аналогично программам вычисления факториала.
Задание выполняется при домашней подготовке. Для определения времени выполнения программы (в секундах) необходимо воспользоваться стандартной встроенной функцией GETTIME .
Сравнить время выполнения этих алгоритмов.
4. Используя программу TREE_WD , сформировать бинарные деревья , содержащие 9, 10 ,11 элементов и выполнить для каждого из них балансировку.
-
Требования к отчету
Отчет должен содержать:
1)конспект лабораторной работы;
2)три вида обхода дерева для своего варианта;
3)программу итеративного рекурсивного вычисления суммы;
4)результаты выполнения работы;
5)вывода по работе.
-
Контрольные вопросы
1.Что понимается под рекурсией и итерацией в математике?
2.Каковы особенности итеративного алгоритма?
3.Каковы особенности рекурсивного алгоритма?
4.В чем состоит методика анализа рекурсивного алгоритма?
5.В каких случаях целесообразно использовать рекурсивный или итеративный алгоритм
6.Приведите примеры итерации и рекурсии.
7.Все ли языки программирования дают возможность рекурсивного вызова процедур?
8.Приведите пример рекурсивной структуры данных.
9.Что такое указатели и динамические переменные в языке Паскаль?
-
Литература
1. Т. Кормен, Ч. Лейзерсон, Р. Ривест «Алгоритмы: построение и анализ».
М.: МЦНМО, 2000.
2. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.
3. Полосухин Б.М., Поддубная Л.М. Рекурсивные функции и алгоритмы. М.: МИЭТ, 1985.
4. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учеб.
пособие. М : Финансы и статистика, 2004.
-
Лабораторная работа - Алгоритмы построения остовного дерева сети
Цель работы: ознакомление с алгоритмами построения остовного дерева графа
( сети) и методикой оценки их эффективности.
Продолжительность работы: - 2 часа.
-
Теоретические сведения
Предположим, что необходимо принять решение, связанное с организацией сети компьютеров в различных территориальных пунктах. Это решение является довольно сложным и зависит от большого количества факторов, которые включают в себя вычислительные ресурсы, доступные в каждом пункте, соответствующие уровни потребностей, пиковые нагрузки на систему, возможное неэффективное использование основного ресурса в системе и, кроме того, стоимость предлагаемой сети. В эту стоимость входят приобретение оборудования, прокладка линий связи, обслуживание системы и т.д. Необходимо определить стоимость такой сети.
Нетрудно видеть, что сформулированная здесь задача имеет много других аналогов. Например, требуется соединить несколько населенных пунктов линиями телефонной связи таким образом, чтобы все эти пункты были связаны в сеть, и чтобы стоимость прокладки коммуникаций была минимальной. Вместо телефонных линий можно говорить о прокладке водопроводных коммуникаций, о строительстве дорог и т. д. Решение подобных задач возможно с использованием теории графов (сетей).
Пусть G=(V,E) - связный неориентированный граф, содержащий циклы, т.е. замкнутые маршруты, где V – множество вершин, а E – множество ребер. Остовным (покрывающим) деревом называется подграф, не содержащий циклов, включающий все вершины исходного графа, для которого сумма весов ребер минимальна.
Введем понятие цикломатического числа (γ) показывающего, сколько ребер на графе нужно удалить, чтобы в нём не осталось ни одного цикла. Цикломатическое число равно, увеличенной на единицу разности между количеством ребер и количеством вершин графа.
γ = n - m +1, где n – количество ребер , m – количество вершин,
Например, для графа, изображенного на рисунке, цикломатическое число равно
γ = n - m +1 = 7-5+1=3
3 5
2 4