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

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

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

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

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

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

Пусть 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.

Дата добавления: 2015-07-16