Методы обхода деревьев

Type

Type

Type

Pvertex = ^Tvertex;

Pchild = Array [0..2] Of Pvertex;

Tvertex = Record

Dat: <поля данных>;

CountChild: Integer;

arrPchild: Pchild;

End;

Var Root: Pvertex;

9.2.2 Представление дерева с помощью вектора

Возможно, самым простым представлением дерева будет одномерный массив (вектор), в котором каждый элемент соответствует отдельной вершине и содержит два поля: поле данных и поле курсора родителя. Поле курсора некоторого элемента будет содержать индекс того элемента, который является родителем данного элемента. Если предположить, что поле Dat предназначено для хранения меток вершин дерева, то векторное представление дерева, показанного на рисунке 9.1, может быть представлено рисунком 9.4.

Рисунок 9.4 - Представление дерева с помощью вектора, в котором
каждая вершина содержит курсор на вершину‑родитель в виде его индекса

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

Такой массив для дерева может быть объявлен следующим образом:

Tvertex = Record

Dat: <поля данных>;

РarentCursor: Integer;

End;

Ttree = Array [0..maxVertex] Of Tvertex;

Var Tree: Ttree;

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

TchildCursors = Array [0..maxChild] Of Integer;

Tvertex = Record

Dat: <поля данных>;

РarentCursor: Integer;

ChildCursors: TchildCursors;

End;

Ttree = Array [0..maxVertex] Of Tvertex;

Var Tree: Ttree;

В этом случае логическая структура дерева из рассматриваемого примера, может быть представлена рисунком 9.5.

Рисунок 9.5 - Представление дерева с помощью вектора, в котором каждая
вершина содержит курсоры как на родительские вершины, так и на вершины-сыновья

Очевидно, старшинство сыновей, на которые указывают курсоры, возрастает с увеличением индекса поля-массива ChildCursors. Несуществующим (пустым) ссылкам соответствует значение курсора -1.

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

9.2.3 Представление дерева с использованием списков сыновей

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

На рисунке 9.6 показано, каким способом представить дерево, изображенное на рисунке 9.1. Здесь имеет место индексированный вектор заголовков, в котором размещаются метки, играющие роль полезных данных. Каждый элемент такого вектора, называемый заголовком (header) содержит указатель, являющийся указателем связного списка. Элементы каждого списка являются сыновьями узла, соответствующего элементу заголовка. Например, узлы E и F - сыновья узла B.

Рисунок 9.6 - Представление дерева со списком сыновей

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

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

1) сверху вниз (нисходящий): R, T₁, T₂, …, T_n (здесь R обозначает корень, T₁, T₂, …, T_n - поддеревья);

2) слева направо (смешанный): T₁, R, T₂, …, T_n;

3) снизу вверх (восходящий): T₁, T₂, …, T_n, R.

Рисунок 9.7 - Укрупненная структура дерева

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

1) При нисходящем (прямом) обходе сначала посещается и обрабатывается корень R, затем выполняется нисходящий обход самого левого поддерева T₁, далее - нисходящий обход поддерева T₂, расположенного правее и т. д. Последним обходится нисходящим методом самое правое поддерево T_n. В соответствии с таким определением вершины дерева, изображенного на рисунке 9.1, при нисходящем обходе будут обрабатываться в следующем порядке: A, B, E, H, F, C, D,G.

2) Смешанный обход выполняется следующим образом: смешанный обход самого левого поддерева T₁, обработка корня R, смешанный обход поддерева T₂, расположенного правее T₁, и т. д. В конце смешанным методом обходится самое правое поддерево T_n. Последовательность обработки вершин того же самого дерева следующая: H, E, B, F, A, C, G, D.

3) Во время выполнения восходящего или обратного обхода обходятся восходящим методом все поддеревья в последовательности их расположения слева направо (T₁, T₂, …, T_n), последним обрабатывается корень R. При этом последовательность поступления на обработку вершин того же дерева на рисунке 9.1 будет следующая: H, E, F, B, C, G, D, A.

Существует еще один - четвертый - метод обхода, который называется обходом по уровням, он наиболее прост для визуального представления, но наиболее сложен для программной реализации. Этот алгоритм предполагает обработку каждого из узлов, начиная с корневого, и просмотр вершин сверху вниз, уровень за уровнем. На каждом уровне вершины обрабатываются слева направо. При обходе этим методом дерева на рисунке 10.1 вершины будут обрабатываться в следующем порядке: A, B, C, D, E, F, G, H.

Если во всех вышеприведенных рекурсивных определениях методов обхода поменять местами слово «левый» на «правый» и наоборот, то получим определение трех других методов обхода, называемых соответственно обратным нисходящим, обратным смешанным и обратным восходящим методами.