Лабораторная работа № 5. "БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)"

Лекция

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

Цель работы: исследовать и изучить процедуры, используемые при работе с бинарными (двоичными) деревьями.

Задача работы: овладеть навыками написания программ по исследованию бинарных деревьев .

Порядок работы :

изучить описание лабораторной работы;
по заданию, данному преподавателем, разработать алгоритм программы решения задачи;
написать программу на языке ПАСКАЛЬ;
отладить программу;
решить задачу;
оформить отчет.

Краткая теория

Общие сведения о структуре данных – дерево.

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

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

Каждый узел дерева может быть промежуточным (элементы 2,3,5,7) либо терминальным ("листом" дерева) (элементы 4,9,10,11,8,6). Характерной особенностью терминальных узлов является отсутствие ветвей.

Лабораторная работа № 5. БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)

Элемент Y, находящийся непосредственно ниже элемента X, называется непосредственным потомком X, если X находится на уровне i , то говорят, что Y лежит на уровне i+1.
Считается, что корень лежит на уровне 0.

Число непосредственных потомков элемента называется его степенью исхода, в зависимости от степени исхода узлов деревья классифицируют :

A) Если степень исхода узлов - М, то дерево называется М-арным ;
B) Если степень исхода узлов - М или 0, то - полное М-арное дерево;
C) Если степень исхода узлов дерева равна 2, то дерево называется бинарным ;
D) Если степень исхода равна 2 или 0, то - полное бинарное дерево.

Особенно важную роль играют бинарные деревья , далее мы будем рассматривать их более подробно.

Представление деревьев в памяти ЭВМ

Деревья наиболее удобно представлять в памяти ЭВМ в виде связанных нелинейных списков. Элемент должен содержать INFO-поле, где содержится характеристика узла. Следующее поле определяет степень исхода узла и количество полей указателей равное степени исхода. Каждый указатель элемента ориентирует данный элемент-узел с его сыновьями. Узлы, в которые входят стрелки от исходного элемента, называются его сыновьями.

INFO-поле содержит два поля : поле записи (rec) и поле ключа (key). Ключ задается числом, по ключу определяют место элемента в дереве.

Лабораторная работа № 5. БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)

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

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

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

Старшим сыном в каждом узле полученной структуры будет узел под обрабатываемым узлом.

Лабораторная работа № 5. БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)

Построение бинарных деревьев

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

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

Например, узлы дерева имеют значения 6, 21, 48, 49, 52, 86, 101.

Бинарное дерево будет иметь вид:

Лабораторная работа № 5. БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)

Получили упорядоченное бинарное дерево с минимальным числом уровней.

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

Алгоритм

Процедура создания бинарного дерева

Для построения дерева необходимо создать в памяти ЭВМ элемент следующего типа:

Лабораторная работа № 5. БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)

P, Q - рабочие указатели

V=maketree(key,rec) - процедура, которая создает сегмент ключа и записи

P=getnode - генерация нового элемента

r=rec
k=key
V=P
left=nil
right=nil

tree - указатель на корень дерева

Введем сначала первое значение ключа, потом сгенерируем сам элемент узла дерева процедурой maketree. Об этом говорит сайт https://intellect.icu . Далее идем по циклу до тех пор, пока указатель не передвинется на нулевое значение.

READ(key,rec)
tree=maketree(key,rec)
WHILE not eof DO
READ(key,rec)
V=maketree(key,rec)
WHILE P<>nil DO
Q=P
IF key=k(P)
THEN P=left(P)
ELSE P=right(P)
END IF
END WHILE
IF P=nil
THEN WRITELN(' Это корень');
tree=V
ELSE IF key
THEN left(P)=V
ELSE right(P)=V
END IF
END IF
END WHILE

Процедуры "обхода" дерева

Пусть задано бинарное дерево :

Лабораторная работа № 5. БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)

Существуют три принципа обхода бинарных деревьев. Рассмотрим их на примере заданного дерева :

1) Обход сверху вниз (корень посещается ранее, чем поддеревья) : A, B, C ;
2) Слева направо : B, A, C ;
3) Снизу вверх (корень посещается после поддеревьев) : B, C, A .

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

Рекурсивные процедуры обхода дерева :

1) PROCEDURE pretrave (tree)

IF tree<>nil
THEN PRINT info (tree)
pretrave (left (tree))
pretrave (right (tree))
END IF
RETURN

2) PROCEDURE intrave (tree)

IF tree<>nil
THEN intrave (left (tree))
PRINT info (tree)
intrave (right (tree))
END IF
RETURN

3) PROCEDURE postrave (tree)

IF tree<>nil
THEN postrave (left (tree))
postrave (right (tree))
PRINT info (tree)
END IF
RETURN

Процедура поиска по бинарному дереву

Назначение этой процедуры в том, чтобы по заданному ключу осуществить поиск узла дерева. Длительность операции поиска (число узлов, которое надо перебрать для этой цели) зависит от структуры дерева. Действительно, дерево может быть вырождено в однонаправленный список (иметь единственную ветвь) - такое дерево может возникнуть, если элементы поступали в дерево в порядке возрастания (убывания) их ключей, например :

Лабораторная работа № 5. БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)

В этом случае время поиска будет такое же, как и в однонаправленном списке, т.е. в среднем придется перебрать N/2 элементов.

Наибольший эффект использования дерева достигается в том случае, когда дерево "сбалансировано". В этом случае для поиска придется перебрать не более LOG2N элементов.

Опишем процедуру поиска. Переменной search будет присваиваться указатель на найденное звено :

p=tree
WHILE p<>nil DO
IF key=k (p)
THEN search=p
RETURN
END IF
IF key<>k (p)
THEN p=left (p)
ELSE p=right (p)
END IF
END WHILE
search=nil
RETURN

Процедура включения элемента в дерево

Для включения новой записи в дерево прежде всего нужно найти тот его узел, к которому можно "подвесить" (присоединить) новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Этот узел будет найден в тот момент, когда в качестве очередной ссылки, определяющей ветвь дерева, в которой надо продолжить поиск, окажется ссылка NIL.

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

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

q=nil
p=tree
WHILE p<>nil DO
q=p
IF key=k (p)
THEN search=p
RETURN
END IF
IF key
THEN p=left (p)
ELSE p=right (p)
END IF
END WHILE
{Узел с заданным ключом не найден, требуется вставка элемента. На узел предполагаемого отца указывает q.}
V=maketree (key, rec)
{Нужно выяснить, левым или правым сыном будет вставляемый элемент V.}
IF key
THEN left (q)=V
ELSE right (q)=V
END IF
search=V
RETURN

Процедура удаления элемента из бинарного дерева

Удаление узла не должно нарушать упорядоченность дерева. При удалении элемента из бинарного дерева с заданным ключом различают три случая :

1) удаляемый узел является листом, в этом случае он просто удаляется, не нарушая этим упорядоченность дерева ;

2) если удаляемый узел имеет только одного сына, то сын перемещается на место удаляемого отца ;

если у удаляемого узла 2 сына. В этом случае на место удаляемого отца помещается либо его предшественник в симметричном обходе (обход слева направо), либо его последователь.

Лабораторная работа № 5. БИНАРНЫЕ ДЕРЕВЬЯ(основные процедуры)

Разработаем алгоритм для 3-его случая (вершина-узел имеет 2-х сыновей), вместо удаляемого узла поставим его приемника в симметричном обходе. Предшественником удаляемого узла 12 является самый правый узел левого поддерева - узел 11, а приемником или последователем при симметричном обходе (обход слева направо) является самый левый узел правого поддерева - узел 13.

Будем использовать следующие указатели :

p - рабочий указатель;
q - отстает на один шаг от p;
v - указывает приемника;
t - отстает от v на один шаг;
s - опережает v на один шаг.

1) Процедурой поиска элемента находим удаляемый элемент. Указатель p указывает на удаляемый элемент.

2) Установим указатель v на узел, который будет замещать удаляемый элемент.

IF left (p)=nil
THEN v=right (p)
ELSE IF right (p)=nil
THEN v=left (p)
ELSE t=p
v=right (p)
s=left (v)
WHILE s<>nil
t=v
v=s
s=left (v)
END WHILE
IF t<>p
THEN WRITE (v не является сыном p)
left (t)=right (v)
right (v)=right (p)
END IF
left (v)=left (p)
IF q=nil
THEN WRITE (v корень)
tree=v
RETURN
END IF
IF p=left (q)
THEN left (q)=v
ELSE right (q)=v
END IF
END IF
END IF
FREENODE (p) (процедура создает свободный узел, т.е. очищает ячейку памяти, в которой находится удаленный элемент)
RETURN

Задания

Варианты:

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

a) присваивает параметру Е запись из самого левого листа непустого дерева Т (лист-вершина, из которого не выходит ни одной ветви);
b) определяет число вхождений записи Е в дерево Т.

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

a) вычисляет среднее арифметическое всех вершин дерева;
b) добавляет в дерево вершину со значением, вычисленным в предыдущей процедуре (функции).

3. Записи вершин дерева - вещественные числа. Описать процедуру, которая удаляет все вершины с отрицательными записями.
4. Записи вершин дерева - вещественные числа. Описать процедуру или функцию, которая:

a) находит максимальное или минимальное значение записей вершин непустого дерева;
b) печатает записи из всех листьев дерева.

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

a) определяет, входит ли вершина с записью Е в дерево Т;
b) если такая запись не найдена, то она добавляется.

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

a) находит в непустом дереве Т длину (число ветвей) пути от корня до ближайшей вершины с записью Е; если Е не входит в Т, то за ответ принять -1.
b) определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.

7. Описать процедуру СОРY(Т,Т1), которая строит Т1 - копию дерева Т.

8. Описать процедуру ЕQUAL(T1,T2), проверяющую на равенство деревья Т1 и Т2 (деревья равны, если ключи и записи вершин одного дерева равны соответственно ключам и записям другого дерева).

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

a) печатает узлы непустого дерева при обходе слева направо;
b) удаляет все листья исходного дерева;
c) печатает модифицированное дерево.

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

a) присваивает переменной b типа char значение:

К - если вершина - корень,
П - если вершина - промежуточная вершина,
Л - если вершина - лист;

b) распечатывает атрибуты всех вершин дерева.

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

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

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

а) печатает дерево, встречающееся в дереве один раз;
b) печатает запись, встречающееся в дереве максимальное число раз.

Вау!! 😲 Ты еще не читал? Это зря!

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