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

Прямой обход

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

Реализация

Для того чтобы упростить работу, добавим в структуру элемента дерева (см. рис. 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;

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

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

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

Дата добавления: 2014-01-03