Добавлен: 29.03.2023
Просмотров: 201
Скачиваний: 4
Листьями дерева называют вершины, в которые входит одна ветвь и не выходит ни одной ветви[16].
Каждое дерево обладает следующими свойствами:
- существует узел, в который не входит ни одной дуги (корень);
- в каждую вершину, кроме корня, входит одна дуга.
Деревья особенно часто используют на практике, чтобы изобразить различные иерархии. Например, популярны генеалогические деревья, которые представлены на рисунке 6[17].
Рисунок 6 – Генеалогические деревья
На рисунке 6 представлено генеалогические деревья, все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама вершина – предком. Для каждого предка может быть выделено несколько.
При этом листьями в дереве являются вершины, имеющие степень нуль. По величине степени дерева различают два типа деревьев, которые показаны на рисунке 7[18]
Типы деревьев
Сильноветвящиеся
Двоичные
Когда степень дерева произвольная
Когда степень дерева не более двух
Рисунок 7 – Типы деревьев
На рисунке 7 показаны два типа деревьев, которые различаются числом степени, в первом типе дерева степень может быть не более двух, а во втором типе произвольное число.
Деревья являются рекурсивными структурами, так как каждое поддерево также является деревом.
Таким образом, дерево можно определить как рекурсивную структуру, в которой каждый элемент является:
- либо пустой структурой;
- либо элементом, с которым связано конечное число поддеревьев.
Действия с рекурсивными структурами удобнее всего описываются с помощью рекурсивных алгоритмов.
Списочное представление деревьев основано на элементах, соответствующих вершинам дерева. Каждый элемент имеет поле данных и два поля указателей:
- указатель на начало списка потомков вершины;
- указатель на следующий элемент в списке потомков текущего уровня[19].
При таком способе представления дерева обязательно следует сохранять указатель на вершину, являющуюся корнем дерева.
Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.
При обходе все вершины дерева должны посещаться в определенном порядке. Существует несколько способов обхода всех вершин дерева. На рисунке 8 представлены наиболее часто используемые способы обхода дерева[20].
Рисунок 8 - Обходы деревьев
Итак, на рисунке 8 представлены три наиболее часто используемых обхода деревьев: прямой, симметричные и обратный, каждый из которых отличается направлениями движения путей.
Существует большое многообразие древовидных структур данных. Выделим самые распространенные из них: бинарные или двоичные деревья; красно-черные деревья; В-деревья; АВЛ-деревья; матричные деревья; смешанные деревья и другие[21].
Бинарное дерево состоит из элементов, каждый из которых содержит информационное поле и не более двух ссылок на различные бинарные поддеревья. На каждый элемент дерева имеется ровно одна ссылка. На рисунке 9 представлено бинарное дерево и его организация[22].
Рисунок 9 –Бинарное дерево и его организация
На рисунке 9 можно рассмотреть структуру бинарного дерева, а также его организацию. Важно отметить, что каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:
-информационное поле (ключ вершины);
-служебное поле (их может быть несколько или ни одного);
-указатель на левое поддерево;
-указатель на правое поддерево.
По степени вершин бинарные деревья делятся на несколько видов, схематически которые изображены на рисунке 10[23].
Рисунок 10 – Виды бинарных деревьев по степени вершин.
На рисунке 10 представлены разновидности бинарных деревьев, которые отличаются по степени вершин. Рассмотрим их более подробно:
- строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);
- нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов).
В общем случае у бинарного дерева на каждом уровне может быть до двух вершин. Бинарное дерево называется полным, если оно содержит только полностью заполненные уровни. В противном случае оно является неполным.
Бинарное дерево может представлять собой пустое множество, а также может выродиться в список, что представлено на рисунке 11[24].
Рисунок 11 – Список как частный случай бинарного дерева
Структура дерева отражается во входном потоке данных так: каждой вводимой пустой связи соответствует условный символ, например, '*' (звездочка). Для структуры бинарного дерева, представленного на рисунке 12, входной поток имеет вид: ABD*G***CE**FH**J**.
Рисунок 12 – Адресация в бинарном дереве
На рисунке 12 представлена адресация в бинарном дереве. Бинарные деревья могут применяться для поиска данных в специально построенных деревьях (базы данных), сортировки данных, вычислений арифметических выражений, кодирования (метод Хаффмана) и так далее.
Таким образом, в данной главе курсовой работы мы определили, что достаточно большое количество задач, которые встречаются в программировании, требуют применение статистических переменных. Такие переменные имеют определенный размер выделенной памяти, которой, при определенных задачах не хватает. В таком случае применяются динамические структуры данных, размер памяти на которые может меняться во время работы.
Во втором параграфе первой главы мы более подробно разобрали классификацию динамической структуры данных, выделили ее необходимость и преимущества, что позволило нам приблизиться к изучению такого вида динамической структуры данных, как дерево.
Далее, мы выделили, что дерево представляет собой структуру данных, характеризующаяся совокупностью элементов и отношений, которые образуют иерархическую структуру этих элементов.
Мы также определили, что бинарное дерево представляет собой динамическую структуру данных, представляющих собой дерево, в котором каждая вершина имеет не более двух потомков. Таким образом, бинарное дерево состоит из элементов, каждый из которых содержит информационное поле и не более двух ссылок на различные бинарные поддеревья.
В следующей главе курсовой работы рассмотрим структуру реализации программ над бинарными деревьями.
2 РЕАЛИЗАЦИЯ ОПЕРАЦИЙ ПО РАБОТЕ С БИНАРНЫМИ ДЕРЕВЬЯМИ
2.1 Операции над бинарными деревьями
В предыдущей главе курсовой работы была определена сущность и характеристика динамической структуры данных.
Также мы разобрали классификацию структуры и выделили один вид для дальнейшего изучения, с двоичной степенью, который называется бинарное дерево.
Рассмотрим операции, которые используют для бинарных деревьев, которые представлены на рисунке 13[25].
Операции над бинарными деревьями
Операция добавления некоторого поддерева в дерево
Операция обхода узлов в определенном порядке
Другие примитивные операции над узлами дерева
Операция исключения некоторого поддерева из дерева
Рисунок 13 – Операции над бинарными деревьями
На рисунке 13 представлены основные операции, которые производят с бинарными деревьями. Рассмотрим более подробно каждую из них. Обход дерева необходим для систематического последовательного просмотра узлов дерева.
Данная операция используется для контроля информации, которая хранится в древовидной структуре и включает в себя следующие шаги:
- обработка или просмотр корня дерева или поддерева;
- обход левого поддерева обработанного корня;
- обход правого поддерева обработанного корня.
Различный порядок выполнения перечисленных выше шагов определяет три процедуры обхода бинарного дерева:
1) обход сверху вниз – сначала обрабатывается корень, затем обходится его левое, затем правое поддеревья (операция UpDownRevision);
2) обход слева направо – сначала обходится левое поддерево корня, затем обрабатывается корень, затем обходится его правое поддерево (операция LeftRightRevision);
3) обход снизу вверх – обходится левое поддерево корня, затем правое, затем обрабатывается корень (операция DownUpRevision)[26].
Примитивные операции над узлами бинарного дерева могут быть следующими. Addr(v) возвращает адрес узла со значении емv. Если p– указатель на узел Node бинарного дерева, то операция Value(p)возвращает значение узла Node. Операции Left(p), Right(p), Father(p), Brother(p) возвращают соответственно указатели на левого сына, правого сына, отца и брата узла Node. Операции IsLeft(p) и IsRight (p)возвращают значение «истина», если Node является соответственно левым или правым сыном некоторого узла дерева, и значение «ложь» – в противном случае.
Дополнительно могут быть определены следующие операции: Create– создание пустого дерева, Clear– удаление всех узлов дерева, WriteTo(f) – вывод дерева в файл f с помощью отступов, Nodes Quantity– определение числа узлов дерева.
Таким образом, для работы с деревьями имеется множество алгоритмов. К наиболее важным относятся задачи построения и обхода деревьев. Для примера, пусть в программе дано описание переменных: var t: ptr; s: integer; c: char; b: boolean.
Тогда двоичное дерево можно построить с помощью следующей рекурсивной процедуры[27]:
Procedure V (var t: ptr) var st: string begin readln (st) if st<>'. 'then begin new (t) t. info: =st V (t. Llink) V (t. Rlink) end else t: =nil end
Структура дерева отражается во входном потоке данных: каждой вводимой пустой связи соответствует условный символ (в данном случае точка).
Существует три основных способа обхода деревьев: в прямом порядке, обратном и концевом. Обход дерева может быть выполнен рекурсивной процедурой и процедурой без рекурсии, который по-другому называется стековым обходом. В приведенной ниже рекурсивной процедуре выполняется обход дерева в обратном порядке.
Нерекурсивный алгоритм обхода дерева в прямом порядке:
Пусть T – указатель на бинарное дерево; А – стек, в который заносятся адреса еще не пройденных вершин; TOP – вершина стека; P – рабочая переменная.
1. Начальная установка: TOP: =0; P: =T.
2. Если P=nil, то перейти на 4. {конец ветви}
3. Вывести P. info. Вершину заносим в стек: TOP: =TOP+1; A [TOP]: =P; шаг по левой ветви: P: =P. llink; перейти на 2.
4. Если TOP=0, то КОНЕЦ.
5. Достаем вершину из стека: P: =A [TOP]; TOP: =TOP-1;
Шаг по правой связи: P: =P. rlink; перейти на 2.
Итак, деревом поиска, или таблицей в виде дерева, называется двоичное дерево в котором слева от любой вершины находятся вершины с элементами, меньшими элемента из этой вершины, а справа - с большими элементами (предполагается, что все элементы дерева попарно различны и что их тип (ТЭД) допускает применение операций сравнения).
Таким образом, в данном параграфе курсовой работы были представлены основные операции, которые могут быть использованы при работе с бинарными деревьями.
Мы выделили четыре основные операции и подробно разобрали их характеристики.
Рассмотрим также описание программ, чтобы более точно конкретизировать сущность и особенности работы с бинарными деревьями, что представлено в следующем параграфе главы курсовой работы.