Епс1; Епс1;

Упражнение № 29. Деревья

Граф — непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.

Граф называется связным, если любые две его вершины соединены путем.

 

Несвязный граф Связный граф

Связный граф без циклов называется деревом. Пример.

 

Для дальнейшей работы с деревьями необходимо определить ряд понятий.

• Вершина у, находящаяся непосредственно ниже вершины х, называется не­посредственным потомком х, а вершина х называется предком у.

• Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.

• Число непосредственных потомков внутренней вершины называется ее степе­нью.

• Степенью дерева называется максимальная степень всех вершин.

Например:

• вершины Г, Д ^являются непосредственными потомками вершины В;

• вершины Г, Д Е являются листьями;

• вершины С, С, Н — внутренние;

• степень вершины В — 3, а вершины Н — 1;

• степень дерева равна 3.

Двоичное дерево — дерево, в котором из каждой вершины исходит не более двухребер.

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

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

Туре ТгееЫпк =^АТгее; Тгее=Кесог< 1

ЭаЪа: < тип данных>; ЬеП:, К1дЫ:: ТгееЫпк; Епс1;

Корень дерева опишем в разделе описания переменных:

Уаг к< 3: ТгееЫпк;

К основным операциям над деревьями относятся

• занесение элемента в дерево;

• обход дерева;

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

Рассмотрим вставку и обход дерева на примере следующей задачи.

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

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

Ргосес1иге 1пзТгее(п: 1пЪедег; Уаг Ъ: 1: гееИпк);

Ведхп

I Т. 1: =Ы1Ь ТЪеп Ведхп

пем(Ъ);

Вед±п

: =N11.;: =Ы1Ь; йаЪа: =п

Епс1;

Епс!

Е1зе 15 п< =Ь*.йаЪа ТЬеп 1пзТгее (п,. 1е^)

Е1зе 1пзТгее (п,. гхдЪ'Ь);

Епс1/

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

• вывод числа, хранящегося в узле;

• обход левого поддерева;

• обход правого поддерева.

Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:

• прямой вывод (сверху вниз);

• обратный вывод (слева направо);

• концевой вывод (снизу вверх).

Процедура обратного вывода дерева имеет следующий вид:

Ргосейиге Рг±пЪТгее (Ъ: {: гее1л-пк);

Вед±п

ТЪеп

Вед±п

Ле±Ь);. йаЪа: 3); Ргл.п*: Тгее. г±дЪЬ)

Епс1;

Епс1;

Основная программа осуществляет ввод чисел с клавиатуры. Используются пе­ременная пй типа КееИпк — значение указателя на корень дерева; переменная ВщИ типа Ше^ег для хранения очередного введенного числа.

Вед±п {Основная программа}

ДОгИ: е1п (¹ окончание ввода - О¹); кс1: =Ыл_1; Кеай(и±д±Ъ); ■

ГОЪИе В1дл-1: < > 0 Во

Вед±п

1пзТгее (ЭхдИ:, кс!) /

ЭДгл_1: е1п (¹ введите очередное число¹)/ Кеай{В±д±Ь);

Епс1;

Ргл.п'ЬТгее (кс!);

Епс1.

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

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

Правильно организованным деревом считается идеально сбалансированное дере­во, то есть такое, что для каждой его вершины число вершин в левом и правом поддереве различается не более чем на 1.

Пример 59. Сформировать идеально сбалансированное дерево, элементами кото­рого являются N чисел, вводимых с клавиатуры.

Решение. Поскольку требуется построить идеально сбалансированное дерево, то его узлы в процессе построения должны распределяться равномерно. Сформулиру­ем правило равномерного распределения узлов при известном их числе:

• взять один узел в качестве корня;

• построить левое поддерево с числом узлов п\ = N6x^2 тем же способом;

• построить правое поддерево с числом узлов п2 = N — п1 — 1 тем же способом.

Ргодгат Ехатр1е_59; изез Сг" Ь; Туре Р" Ь=^/чЫос1е;

Ыос1е=Кесогс1

Ба" Ьа: 1п" Ьедег; ЪеГ*:, К1дЪ1:: РЪ; Еп< 1; Уаг п: 1п-Ьедег; кс!: Р" Ь; I: Ьех^;

ГипсЬхоп Тгее (п: 1п-Ьедег): р-Ь; Уаг пемпос! е: р" Ь;

х, п1, п2: 1п-Ьедег; Ведхп

II п=0 ТЬеп Тгее: -пИ

Е1зе

Ведхп

п1: =п Ол.V 2; п2: =п-п1-1; Кеа< 1(Г_/х); Ые^ (пе^пос! е); пе^по^е⁷⁴ Во

Ведхп

Ба^а: =х/ Ъе1Ь: =Тгее (п1); К1дЬ1:: =Тгее (п2); Еп< 1;

Тгее: =пе^пос! е; Еп< 1; Еп< 1;

Ргосейиге РгхпЬТгее Ъ: ХпЪедег);

Уаг 1: 1п-Ьедег;

Ведхп

II Ь< > N11 ТЬеп Бо.

Ведхп

Рг1П" ЬТгее (1еГ1:, Ъ+1); Еог 1: = 1 То Ъ Во МгНе (' '); №г11: е1п (ВаЬа: 6); Ргл_п1: Тгее (К1дЫ:, Ъ+1); Еп< 1; Еп< 1; Ведхп

С1гзсг; Азз1дп(Г, ¹ с:.раз ¹);

Кезе^(^); (¹ п= ');

КеасИп (п); кс!: =1: гее (п); рг1п1: 1: гее (кс1, 0); КеасИп;

Епс1.

Пример 60. Задана последовательность слов. Определить частоту вхождения каж­дого из слов в последовательность.

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

Ргодгат Ехатр1е_60;, 11зе5 Сг" Ь; Туре ДОог< 2з=^Л1йогсН: гее; Мо г с! ^ г е е=Ке сог с! с! а1: а: 5" Ьгд.пд; к: 1п-Ьедег; 1 е, г 1 дЫ:: Юогс! з; Епс!;

Уаг п1п1: едег; кс!: 1йогс1з;

х: 5" Ьг1пд; 5: Ъех*;; Ргосес1иге Тгее (х: 5" Ьгд.пд; Уаг р: 1л? огс1з); Ведхп

15 р=ЫИ ТЬеп Вед1п

Ыем (р);

р^л Во

Вед1п

к: =1; ВаЬа: =х; КхдЬ*:: =М1;

Епс!;

Епс!

Е1зе 15 х> р^л.ВаЬа ТЬеп Тгее (х, р^л. Ье: Е{:)

Е1зе 15 х< р^л.с1а^а ТЬеп Тгее (х, р^л. КхдЪ*:) Е1зе 1пс(р^л.к);

Епс1;

Ргосес! иге Ргл_п1: Тгее (1:: 1л? огс1з; Ь: 1п1: едег);

Уаг л_: 1п1: едег;

Ведхп

15 Ь < > пИ ТЬеп Во

Вед1п

Рг1п" ЬТгее (Ъе^_/11+1);

Еог 1: =1 То Ь Во №гл_*: е (¹ ');

1л? г11: е1п (йаЪа, ¹, (', к, ')'); Ргл.п*: Тгее (К1дЪ*:, Ъ+1); Епс1;

Епс1; Ведхп

С1гзсг; Аззхдп (5, ¹ с:. с! ап ¹); Кезе^(^); (¹ п= '); КеасИп (п); М: =Ыл.1;

ШН1е п> 0 Эо Вед1п Кеас1Ьп (5, х); Тгее(х, кс1); с! ес (п); Еп< 1; С1озе (5); Ргхп^Тгее (кс1, 0); КеасИп; Епс1.

Задания для самостоятельной работы

Указатели и ссылки

1. Пусть переменные хп у имеют значения, показанные на рисунке.

^хО-ЧИ ^ЕЗ-ЧЗ

Каковы типы переменных л; и х^А? Что будет выдано на печать в результате вы­полнения следующих операторов:

Уаг х, у: ^А1п1: едег;

х^А: =у^А;

х=у ТЬеп х: =М1 Е1зе И х^А=у^А ТЬеп у: =х; х=у ТЬеп д^А: = 4; ЮгИ: еЬп (ч^А);

2. Имеется программа:

Ргодгат Бупатхк;

Уаг х: ^А1п1: едег; у: 1п1: едег;

Ведхп {а}

Ыем(х); {Ь} х^А: =10; {с} у: =х^А+6; В1зрозе (х); {с! } ЭДг11: еЬп(у) {е} Еп< 1.

а) Какие переменные существуют в каждой из точек а, Ь, с, с1, е и каковы их значения в эти моменты?

б) Можно ли переменной л; присвоить ссылку на переменную у? Можно ли с помощью процедуры В1$ро8в уничтожить переменные хи у?

3. Туре С11а1п=^АЕ1ет;

Е1ет=Кесогс1 Ба1: а: 1п1: едег; Мех1:: СЬахп; Епс1;

Уаг СЬахп;

Привести схемы памяти после выполнения следующих операторов:

а) N6^ (р); р^А.Ба1а: =4; р^А.Ыех1: =ЫИ;

б) N6^ (р); р^А.Ба1: а: =7; р^А^ех1: =р;

в)Ые^(д); д^А.Ба1а: =2; я^А. N6x1:: =N11;

г) ^ю(р); р^А. Ба1а: =1; р^А^ех1:: =д;

д) N6^ (р); р^А. Ба1: а: =5; N6^ (р^А. N6x1); р^А. N0x1^А: =р^А

Линейные списки

1. Какие операции требуется выполнить для вставки элемента списка?

2. Можно ли для построения списка обойтись одной переменной?

3. Сколько элементов может содержать список? Когда прекращать ввод элемен­тов списка?

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

5. Описать рекурсивную и нерекурсивную процедуры или функции проверки наличия в списке заданного числа.

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

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

а) перед каждым вхождением заданного элемента;

б) за каждым вхождением заданного элемента.

8. Опйсать процедуру или функцию, которая:

а) проверяет на равенство списки 11 и 12;

б) определяет, входит ли список 11 в список 12;

в) переносит в конец непустого списка 1 его первый элемент;

г) переносит в начало непустого списка его последний элемент;

д) копирует в список 1 за каждым вхождением заданного элемента все эле­менты списка 11.

9.Описать процедуру, которая объединяет два упорядоченных по неубыванию списка 11 и 12 в один упорядоченный по неубыванию список:

а) построив новый список 1;

б) сменив соответствующим образом ссылки в 11 и 12.

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

11. Описать функцию, подсчитывающую число слов списка, которые:

а) начинаются и оканчиваются одной и той же литерой;

б) начинаются с той же литеры, что и следующее слово.

12. Описать процедуру, которая удаляет:

а) из списка 1 второй элемент, если такой есть;

б) из списка 1 за каждым вхождением элемента Е один элемент, если такой есть и он отличен от Е\

в) из списка Ь первый отрицательный элемент, если такой есть;

г) из списка Ь все отрицательные элементы.

13. Описать процедуру, которая формирует список 1, включив в него по одно­му разу элементы, которые:

а) входят хотя бы в один из списков 11 и 12;

б) входят одновременно в оба списка 11 и 12;

в) входят в список 11, но не входят в список 12;

г) входят в один из списков 11 и 12, но в то же время не входят в другой из них.

14. Многочлен Р(х) = а_пх^п + а_п-_хх^п~^х +... + а_хх + а₀с целыми коэффициен­тами можно представить в виде списка (рис. а), причем если а_{=0, то соответству­ющий элемент не включается в список (на рис. Ь показано представление много­члена $(х) = — 5х^в + Зх² — х + 7).

Описать на Паскале тип данных, соответствующий такому представлению мно­гочленов, определить следующие функции и процедуры для работы с этими спис­ками-многочленами:

а) логическую функцию еяиа1л.1: у (р, я), проверяющую на равенство мно­гочлены р и

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

 

а

-5						-1
									Ш

 

Ъ

в) процедуру асМ (р, ц, г), которая строит многочлен р — сумму много­членов

г) процедуру ргл_п*: (р, V), печатающую многочлен р как многочлен от переменной, однобуквенное имя которой является значением литерного параметра V, например, для указанного выше многочлена 5 процедура рг(з, ¹ х') должна напечатать

-5у^А6 + Зу^А2 - у+7.

15. Используя стек, разработайте программу, которая преобразует обычную форму записи арифметического выражения в обратную польскую запись.

Очереди

16. За один просмотр файла/ элементами которого являются действительные числа, и без использования дополнительных файлов напечатать его элементы так: сначала все числа, меньшие заданного а, затем все числа из отрезка [а, Ь] и все остальные, сохраняя их взаимный порядок в каждой из групп чисел.

Идея решения. Для решения задачи будем последовательно считывать из файла числа. Если очередное число меньше а, то выведем его на экран, если оно принад­лежит отрезку [а, 6], то занесем его в первую очередь, иначе — занесем его во вторую очередь. После того, как все данные будут рассмотрены, выведем на экран обе очереди.

17. Содержимое текстового файла/, разделенного на строки, переписать в тек­стовый файл перенося при этом в конец каждой строки все входящие в него цифры, с сохранением взаимного исходного порядка.

Деревья

18. Описать рекурсивную логическую функцию, проверяющую наличие задан­ного числа в сформированном дереве.

19. Описать рекурсивную числовую функцию, подсчитывающую сумму элемен­тов дерева.

20. Описать функцию, которая находит наибольший элемент непустого дерева.

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

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

23. Описать процедуру, которая:

• каждый элемент дерева возводит в квадрат;

• каждый отрицательный элемент заменяет на его абсолютную величину;

• печатает все элементы дерева по уровням.

24. Описать функцию, которая:

• находит максимальный элемент в дереве Г;

• находит сумму всех элементов дерева;

• подсчитывает число элементов в дереве;

• для заданного числа х находит число его вхождений в дерево.