Лекция №12.2: Алгоритмы на графах и деревьях

страницы: 1 2 3 4 5 6

Содержание

Построение из постфиксной записи

Для простоты предположим, что правильное арифметическое выражение подаётся в одной строке, без пробелов, а каждый операнд записан одной буквой. Кроме того, снова будем считать, что из записи удалены все скобки.

Алгоритм Postfix
  1. Если не достигнут конец строки ввода, прочитать очередной символ, если этот символ — операнд, то занести его в стек1, иначе (символ — операция):
    1. создать новый элемент, записать в него эту операцию;
    2. достать из стека два верхних (последних) элемента, присоединить их в качестве левого и правого операндов в новый элемент;
    3. занести полученный «треугольник» в стек.

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

Реализация

Для того, чтобы упростить работу, добавим в структуру элемента дерева (см. рис. 1.12) дополнительное поле next : ukaz, которое будет служить для связки стека:

stek := nil;
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;

Обходы деревьев и графов

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

Обход дерева — это некоторая последовательность посещения всех его вершин.

Обход графа — это обход некоторого его каркаса.

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

Напомним, что структуру бинарного дерева мы описываем следующим образом:

type ukazatel = ^tree;
  tree = record
    mark : Integer;
    left : ukazatel;
    right : ukazatel;
 end;

Итак, приступим теперь к изучению различных вариантов обхода деревьев и графов.

Прямой обход

Другие названия

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

Обход в глубину «сверху вниз»: название имеет смысл лишь в случае стандартного расположения дерева корнем кверху.

Алгоритм PreOrder
  1. Начать с корня дерева.
  2. Пометить3 текущую вершину.
  3. Совершить прямой обход левого поддерева.
  4. Совершить прямой обход правого поддерева.

Замечание: Этот алгоритм может быть естественным образом распространён и на случай произвольного корневого дерева.

Реализация
procedure preorder(p : ukaz; k : Integer);
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.2.  Последовательность нумерации вершин при прямом обходе дерева

страницы: 1 2 3 4 5 6

Примечания

  1. ^ См. лекцию 9.
  2. ^ Точнее, результатом печати значений, содержащихся в вершинах ДСА.
  3. ^ Вместо простой пометки вершины здесь можно производить выполнение любой осмысленной функции.
Код для вставки: :: :: :: ::
Поделиться: // //