Нелинейные структуры. Деревья

Одним из важных признаков структуры данных является характер упорядоченности ее элементов. По этому признаку структуры можно делить на линейные и нелинейные. К линейным структурам относятся: векторы, строки, массивы, стеки, очереди, списки. Представителями нелинейных структур являются деревья и графы.

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

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

Формально дерево можно определить следующим образом.

Один узел является деревом, он же является корнем этого дерева.

Пусть n – это узел, а – деревья с корнями соответственно. Можно построить новое дерево, сделав n родителем узлов . В этом дереве n будет корнем, а – поддеревьями этого корня. Узлы называются сыновьями узла n.

Часто в это определение включают понятие нулевого дерева, т.е. дерева без узлов.

Существует несколько способов изображения структуры дерева: вложенные множества; вложенные скобки; с помощью отступов; графически.

В качестве примера рассмотрим оглавление книги и представим его схематически (рис. 13.а, 13.б):

КНИГА

ГЛАВА 1

РАЗДЕЛ 1.1

РАЗДЕЛ 1.2

ГЛАВА 2

РАЗДЕЛ 2.1

РАЗДЕЛ 2.1.1

РАЗДЕЛ 2.1.2

РАЗДЕЛ 2.2

РАЗДЕЛ 2.3

ГЛАВА 3

Рис. 13.а – Первый способ представления структуры в виде дерева

КНИГА

ГЛАВА 1 ГЛАВА 2 ГЛАВА 3

РАЗДЕЛ 1.1 РАЗДЕЛ 1.2 РАЗДЕЛ 2.1 РАЗДЕЛ 2.2 РАЗДЕЛ 2.3

РАЗДЕЛ 2.1.1 РАЗДЕЛ 2.1.2

Рис. 13.б – Второй способ представления структуры в виде дерева

Отношение родитель-сын чаще всего отображается в виде линии. Дерево обычно рисуется сверху вниз, так чтобы родители располагались выше детей.

Корнем дерева на рис. 13 является узел Книга, который имеет три поддерева, соответственно с корнями Глава 1, Глава 2, Глава 3. Узел Книга является родителем узлов Глава1, Глава 2, Глава 3, а эти узлы – сыновьями узла Книга.

Дерево имеет три поддерева. Первое из которых (Глава 1) имеет два поддерева: Раздел 1.1 и Раздел 1.2. Поддерево с корнем Глава 2 имеет трех сыновей: Раздел 2.1, Раздел 2.2, Раздел 2.3. Узел Раздел 2.1 имеет два сына: Раздел 2.1.1 и Раздел 2.1.2. Поддерево с корнем Глава 3, состоит из одного узла и не содержит поддеревьев.

Рассмотренный пример показывает, что дерево – это наилучшая форма представления четко структурированных данных.

Путем из узла в узел называется последовательность узлов , где для всех i, 1£ i £ k, узел является родителем узла .

Длиной пути называется число узлов, составляющих этот путь. Таким образом, путем нулевой длины будет путь из любого узла к самому себе. (В примере на рис. 13 путем длины 2 будет, например, путь от узла Глава 2 к узлу Раздел 2.1.2).

Если на дереве существует путь из узла a в узел b, то в этом случае узел а называется предком узла b, а узел b – потомком узла а. (Например, предками узла Раздел 2.1 являются: сам узел Раздел 2.1, а также узлы Глава 2 и Книга, тогда как потомками этого узла являются: сам узел Раздел 2.1, а также узлы Раздел 2.1.1 и Раздел 2.1.2. Любой узел одновременно является и предком, и потомком самого себя.

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

Высотой узла дерева называется длина самого длинного пути из этого узла до какого либо листа. В нашем примере высота узла Глава 1 равна 1, узла Глава 2 – 2, а узла Глава 3 – 0.

Порядок узлов дерева. Если имеет значение относительный порядок поддеревьев в дереве, то можно говорить, что дерево является упорядоченным; в случае, когда порядок узлов игнорируется, дерево называют неупорядоченным. Сыновья узла обычно упорядочиваются слева направо. Поэтому два дерева на рис. 14 различны, т.к. порядок сыновей узла А различен.

Рис. 14 – Два различных дерева

Упорядочивание сыновей слева направо можно использовать для сопоставления узлов, которые не связаны отношениями предки-потомки. Соответствующее правило звучит следующим образом.

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

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

Обходы дерева

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

Все три способа обхода дерева можно определить рекурсивно следующим образом.

Если дерево Т является нулевым деревом, то в список обхода заносится пустая запись.

Если дерево Т состоит из одного узла, то в список обхода записывается этот узел.

Далее, пусть Т – дерево с корнем n и поддеревьями , тогда для различных способов обхода имеем следующее:

а) при прохождении в прямом порядке (т.е. при прямом упорядочивании) узлов дерева Т сначала посещается корень n, а затем узлы поддерева далее все узлы поддерева и т. д. Последним посещаются узлы поддерева

б) при симметричном обходе узлов дерева Т сначала посещаются в симметричном порядке все узлы поддерева далее корень n, затем последовательно в симметричном порядке все узлы поддеревьев .

в) в случае обхода в обратном порядке сначала посещаются в обратном порядке все узлы поддерева , затем последовательно посещаются все узлы поддеревьев , также в обратном порядке, последним посещается корень n.

Для дерева, изображенного на рис. 15, рассмотрим наброски рекурсивных процедур, реализующих три способа обхода дерева.

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

Рис. 15 – Дерево обхода

Прямой обход дерева:

Procedure СверхуВниз (t: АдрЭлем);

begin

if t <>nil

then begin

P(t); {обработка вершины}

write(t);

СверхуВниз (t^.left);

СверхуВниз (t^. right);

end

end;

Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1

Симметричный обход дерева:

Procedure СлеваНаправо (t: АдрЭлем);

begin

if t <>nil

then begin

СлеваНаправо (t^.left);

P(t); {обработка вершины}

write(t);

СлеваНаправо (t^. right);

end

end;

Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1

Обратный обход дерева:

Procedure СнизуВверх (t: АдрЭлем);

begin

if t <>nil

then begin

СнизуВверх (t^.left);

СнизуВверх (t^. right);

P(t); {обработка вершины}

write(t);

end

end;

Последовательность обработки: 1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1

Лекция 8

План лекции:

1. Бинарное дерево. Построение бинарного дерева.

2. Помеченные деревья и деревья выражения.

3. Реализация деревьев.

Не нашли, что искали? Воспользуйтесь поиском: