Алгоритм обхода в прямом порядке:
Попасть в корень,
Пройти все поддеревья слева на право в прямом порядке.
Данный алгоритм рекурсивен, так как прохождение дерева содержит прохождение поддеревьев, а они в свою очередь проходятся по тому же алгоритму.
В частности для дерева на рис. 3 и 4 прямой обход дает последовательность узлов: A, B, C, D, E, G, H.
Получающаяся последовательность соответствует последовательному слева направо перечислению узлов при представлении дерева с помощью вложенных скобок и в десятичной системе Дьюи, а также проходу сверху вниз при представлении в виде уступчатого списка.
При реализации этого алгоритма на языке программирования попадание в корень соответствует выполнение процедурой или функцией некоторых действий, а прохождение поддеревьев – рекурсивным вызовам самой себя. В частности для бинарного дерева (где из каждого узла исходит не более двух поддеревьев) соответствующая процедура будет выглядеть так:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// Preorder Traversal – английское название для прямого порядка
procedure PreorderTraversal({Аргументы});
begin
//Прохождение корня
DoSomething({Аргументы});
//Прохождение левого поддерева
if {Существует левое поддерево} then
PreorderTransversal({Аргументы 2});
//Прохождение правого поддерева
if {Существует правое поддерево} then
PreorderTransversal({Аргументы 3});
end;
|
То есть сначала процедура производит все действия, а только затем происходят все рекурсивные вызовы.
Алгоритм обхода в обратном порядке:
Пройти левое поддерево,
Попасть в корень,
Пройти следующее за левым поддерево.
Попасть в корень,
и т.д пока не будет пройдено крайнее правое поддерево.
То есть проходятся все поддеревья слева на право, а возвращение в корень располагается между этими прохождениями. Для дерева на рис. 3 и 4 это дает последовательность узлов: B, A, D, C, E, G, F.
В соответствующей рекурсивной процедуре действия будут располагаться в промежутках между рекурсивными вызовами. В частности для бинарного дерева:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// Inorder Traversal – английское название для обратного порядка
procedure InorderTraversal({Аргументы});
begin
//Прохождение левого поддерева
if {Существует левое поддерево} then
InorderTraversal({Аргументы 2});
//Прохождение корня
DoSomething({Аргументы});
//Прохождение правого поддерева
if {Существует правое поддерево} then
InorderTraversal({Аргументы 3});
end;
|
Алгоритм обхода в концевом порядке:
Пройти все поддеревья слева на право,
Попасть в корень.
Для дерева на рис. 3 и 4 это даст последовательность узлов: B, D, E, G, F, C, A.
В соответствующей рекурсивной процедуре действия будут располагаться после рекурсивных вызовов. В частности для бинарного дерева:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// Postorder Traversal – английское название для концевого порядка
procedure PostorderTraversal({Аргументы});
begin
//Прохождение левого поддерева
if {Существует левое поддерево} then
PostorderTraversal({Аргументы 2});
//Прохождение правого поддерева
if {Существует правое поддерево} then
PostorderTraversal({Аргументы 3});
//Прохождение корня
DoSomething({Аргументы});
end;
|
5.3. Представление дерева в памяти компьютера
Если некоторая информация располагается в узлах дерева, то для ее хранения можно использовать соответствующую динамическую структуру данных. На Паскале это делается с помощью переменной типа запись (record), содержащей указатели на поддеревья того же типа. Например, бинарное дерево, где в каждом узле содержится целое число можно сохранить с помощью переменной типа PTree, который описан ниже:
1
2
3
4
5
6
|
type
PTree = ^TTree;
TTree = record
Inf: integer;
LeftSubTree, RightSubTree: PTree;
end;
|
Каждый узел имеет тип PTree. Это указатель, то есть каждый узел необходимо создавать, вызывая для него процедуру New. Если узел является концевым, то его полям LeftSubTree и RightSubTree присваивается значение nil. В противном случае узлы LeftSubTree и RightSubTree также создаются процедурой New.
Схематично одна такая запись изображена на рис. 5.
Рис. 5. Схематичное изображение записи типа TTree. Запись имеет три поля: Inf – некоторое число, LeftSubTree и RightSubTree – указатели на записи того же типа TTree.
Пример дерева, составленного из таких записей, показан на рисунке 6.
Рис. 6. Дерево, составленное из записей типа TTree. Каждая запись хранит число и два указателя, которые могут содержать либо nil, либо адреса других записей того же типа.
Если вы ранее не работали со структурами состоящими из записей, содержащих ссылки на записи того же типа, то рекомендуем ознакомиться с материалом о рекурсивных структурах данных.
6. Примеры рекурсивных алгоритмов
6.1. Рисование дерева
Рассмотрим алгоритм рисования деревца, изображенного на рис. 6. Если каждую линию считать узлом, то данное изображение вполне удовлетворяет определению дерева, данному в предыдущем разделе.
Рис. 6. Деревце.
Рекурсивная процедура, очевидно должна рисовать одну линию (ствол до первого разветвления), а затем вызывать сама себя для рисования двух поддеревьев. Поддеревья отличаются от содержащего их дерева координатами начальной точки, углом поворота, длиной ствола и количеством содержащихся в них разветвлений (на одно меньше). Все эти отличия следует сделать параметрами рекурсивной процедуры.
Пример такой процедуры, написанный на Delphi, представлен ниже:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
procedure Tree(
Canvas: TCanvas; //Canvas, на котором будет рисоваться дерево
x,y: extended; //Координаты корня
Angle: extended; //Угол, под которым растет дерево
TrunkLength: extended; //Длина ствола
n: integer //Количество разветвлений (сколько еще предстоит
//рекурсивных вызовов)
);
var
x2, y2: extended; //Конец ствола (точка разветвления)
begin
x2 := x + TrunkLength * cos(Angle);
y2 := y - TrunkLength * sin(Angle);
Canvas.MoveTo(round(x), round(y));
Canvas.LineTo(round(x2), round(y2));
if n > 1 then
begin
Tree(Canvas, x2, y2, Angle+Pi/4, 0.55*TrunkLength, n-1);
Tree(Canvas, x2, y2, Angle-Pi/4, 0.55*TrunkLength, n-1);
end;
end;
|
Для получения рис. 6 эта процедура была вызвана со следующими параметрами:
1
|
Tree(Image1.Canvas, 175, 325, Pi/2, 120, 15);
|
Заметим, что рисование осуществляется до рекурсивных вызовов, то есть дерево рисуется в прямом порядке.
6.2. Ханойские башни
Согласно легенде в Великом храме города Бенарас, под собором, отмечающим середину мира, находится бронзовый диск, на котором укреплены 3 алмазных стержня, высотой в один локоть и толщиной с пчелу. Давным-давно, в самом начале времен монахи этого монастыря провинились перед богом Брамой. Разгневанный, Брама воздвиг три высоких стержня и на один из них поместил 64 диска из чистого золота, причем так, что каждый меньший диск лежит на большем. Как только все 64 диска будут переложены со стержня, на который Бог Брама сложил их при создании мира, на другой стержень, башня вместе с храмом обратятся в пыль и под громовые раскаты погибнет мир.
В процессе требуется, чтобы больший диск ни разу не оказывался над меньшим. Монахи в затруднении, в какой же последовательности стоит делать перекладывания? Требуется снабдить их софтом для расчета этой последовательности.
Независимо от Брамы данную головоломку в конце 19 века предложил французский математик Эдуард Люка. В продаваемом варианте обычно использовалось 7-8 дисков (рис. 7).
Рис. 7. Головоломка «Ханойские башни».
Предположим, что существует решение для n-1 диска. Тогда для перекладывания n дисков надо действовать следующим образом:
1) Перекладываем n-1 диск.
2) Перекладываем n-й диск на оставшийся свободным штырь.
3) Перекладываем стопку из n-1 диска, полученную в пункте (1) поверх n-го диска.
Поскольку для случая n = 1 алгоритм перекладывания очевиден, то по индукции с помощью выполнения действий (1) – (3) можем переложить произвольное количество дисков.
Создадим рекурсивную процедуру, печатающую всю последовательность перекладываний для заданного количества дисков. Такая процедура при каждом своем вызове должна печатать информацию об одном перекладывании (из пункта 2 алгоритма). Для перекладываний из пунктов (1) и (3) процедура вызовет сама себя с уменьшенным на единицу количеством дисков.
1
2
3
4
5
6
7
8
9
10
11
12
13
|
//n – количество дисков
//a, b, c – номера штырьков. Перекладывание производится со штырька a,
//на штырек b при вспомогательном штырьке c.
procedure Hanoi(n, a, b, c: integer);
begin
if n > 1 then
begin
Hanoi(n-1, a, c, b);
writeln(a, ' -> ', b);
Hanoi(n-1, c, b, a);
end else
writeln(a, ' -> ', b);
end;
|
Заметим, что множество рекурсивно вызванных процедур в данном случае образует дерево, проходимое в обратном порядке.
6.3. Синтаксический анализ арифметических выражений
Задача синтаксического анализа заключается в том, чтобы по имеющейся строке, содержащей арифметическое выражение, и известным значениям, входящих в нее переменных, вычислить значение выражения.
Процесс вычисления арифметических выражений можно представить в виде бинарного дерева. Действительно, каждый из арифметических операторов (+, –, *, /) требует двух операндов, которые также будут являться арифметическими выражениями и, соответственно могут рассматриваться как поддеревья. Рис. 8 показывает пример дерева, соответствующего выражению:
Рис. 8. Синтаксическое дерево, соответствующее арифметическому выражению (6).
В таком дереве концевыми узлами всегда будут переменные (здесь x) или числовые константы, а все внутренние узлы будут содержать арифметические операторы. Чтобы выполнить оператор, надо сначала вычислить его операнды. Таким образом, дерево на рисунке следует обходить в концевом порядке. Соответствующая последовательность узлов
называется обратной польской записью арифметического выражения.
При построении синтаксического дерева следует обратить внимание на следующую особенность. Если есть, например, выражение
и операции сложения и вычитания мы будем считывать слева на право, то правильное синтаксическое дерево будет содержать минус вместо плюса (рис. 9а). По сути, это дерево соответствует выражению  Облегчить составление дерева можно, если анализировать выражение (8) наоборот, справа налево. В этом случае получается дерево с рис. 9б, эквивалентное дереву 8а, но не требующее замены знаков.
Аналогично справа налево нужно анализировать выражения, содержащие операторы умножения и деления.
Рис. 9. Синтаксические деревья для выражения a – b + c при чтении слева направо (а) и справа налево (б).
В файле SynAn.pas приведен пример функции, вычисляющей значения выражений, содержащих только одну переменнуюx. Дадим краткое описание реализованного там алгоритма:
Вычисляющая выражение функция (CalcExpression) находит в строке все знаки «+» и «–», не заключенные в скобки. Эти знаки разбивают выражение на части, содержащие (вне скобок) только операции умножения и деления. Для вычисления значений этих частей вызывается функция CalcMultDiv.
Функция CalcMultDiv находит в строке все знаки «*» и «/», не заключенные в скобки. Эти знаки разбивают выражение на части, содержащие числовые константы, переменную x или выражения в скобках. Для вычисления значений этих частей вызывается функция CalcValuesOrOpenParentheses.
Функция CalcValuesOrOpenParentheses определяет тип попавшего ей на вход выражения. Если это числовая константа или переменная x, то она возвращает их значение. Если это выражение в скобках, то для его вычисления рекурсивно вызывается процедура CalcExpression.
Заметим, что в данном примере вычисления производятся одновременно с анализом строкового выражения. Это приводит к тому, что для некоторых выражений вычисления могут происходить в 100 – 1000 раз медленнее, чем, если бы эти выражения были скомпилированы как часть программы. Если одно и то же выражение требуется вычислить много раз при различных значения переменных, то следует разделить анализ строки и вычисления. Такой подход может позволить ускорить вычисления в сотни раз.
Результатом анализа строки должна быть последовательность узлов дерева в концевом порядке. Каждый узел должен хранить информацию о подузлах и о той операции, которая в нем совершается. Например, узлы можно реализовать в виде записей, одно из полей который имеет процедурный тип. Другой вариант – каждый узел это объект, где операция реализована как виртуальный метод.
6.4. Быстрые сортировки
Простые методы сортировки вроде метода выбора или метода пузырька сортируют массив из n элементов за O(n2) операций. Однако с помощью принципа «разделяй и властвуй» удается построить более быстрые, работающие за O(nlog2 n) алгоритмы. Суть этого принципа в том, что решение получается путем рекурсивного разделения задачи на несколько простые подзадачи того же типа до тех пор, пока они не станут элементарными. Приведем в качестве примеров несколько быстрых алгоритмов такого рода.
|
