Правила форума
Лекция №12.2: Алгоритмы на графах и деревьяхСодержание
Построение из постфиксной записи
Для простоты предположим, что правильное арифметическое выражение подаётся в одной строке, без пробелов, а каждый операнд записан одной буквой. Кроме того, снова будем считать, что из записи удалены все скобки.
Алгоритм Postfix
- Если не достигнут конец строки ввода, прочитать очередной символ, если этот символ — операнд, то занести его в стек1, иначе (символ — операция):
- создать новый элемент, записать в него эту операцию;
- достать из стека два верхних (последних) элемента, присоединить их в качестве левого и правого операндов в новый элемент;
- занести полученный «треугольник» в стек.
По окончании работы этого алгоритма в стеке будет содержаться ровно один элемент — указатель на корень построенного дерева.
Реализация
Для того, чтобы упростить работу, добавим в структуру элемента дерева (см. рис. 1.12) дополнительное поле next : ukaz, которое будет служить для связки стека:
while not Eof(f) do
begin
New(p);
Read(f, p^.symbol);
if p^.symbol in ['+', '-', '*', '/'] then
begin
p^.right := stek;
p^.left := stek^.next;
p^.next := stek^.next^.next;
stek := p
end
else
begin
p^.left := nil;
p^.right := nil;
p^.next := stek;
stek := p
end;
end;
Обходы деревьев и графов
Прежде, чем приступить к изложению алгоритмов обхода, дадим пару необходимых определений.
Обход дерева — это некоторая последовательность посещения всех его вершин.
Обход графа — это обход некоторого его каркаса.
В этом разделе будут представлены только алгоритмы обхода бинарных деревьев. Большинство из них может быть с легкостью изменено для случая произвольного корневого дерева, каковым является и каркас произвольного графа.
Напомним, что структуру бинарного дерева мы описываем следующим образом:
tree = record
mark : Integer;
left : ukazatel;
right : ukazatel;
end;
Итак, приступим теперь к изучению различных вариантов обхода деревьев и графов.
Прямой обход
Другие названия
Префиксный обход: результатом прямого обхода2 дерева синтаксического анализа арифметического выражения будет префиксный вариант записи этого выражения.
Обход в глубину «сверху вниз»: название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.
Алгоритм PreOrder
- Начать с корня дерева.
- Пометить3 текущую вершину.
- Совершить прямой обход левого поддерева.
- Совершить прямой обход правого поддерева.
Замечание: Этот алгоритм может быть естественным образом распространён и на случай произвольного корневого дерева.
Реализация
begin
p^.mark := k;
if p^.left <> nil then preorder(p^.left, k + 1);
if p^.right <> nil then preorder(p^.right, k + 1);
end;
begin
{...}
preorder(root, 1); {Вызов из тела программы}
{...}
end.
/12%2D2.gif)
Рис. 12.2. Последовательность нумерации вершин при прямом обходе дерева
::
::
::
