Прохождение бинарных деревьев

Объявление элементов бинарного дерева

type

tree = ^node;

node = record

data: char;

left, right: tree;

end;

При таком способе представления дерева следует сохранять в некоторой переменной указатель на узел, являющийся корнем дерева:

var

Root: tree;

Основные операции с деревом (построение, обход, поиск вершин по некоторому условию и др.) реализуются рекурсивными алгоритмами, так как дерево представляет собой рекурсивную структуру данных: каждое поддерево тоже является деревом.

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

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

· попасть в корень;

· обойти в прямом порядке (от предка к потомку до листьев) левое поддерево;

· обойти в прямом порядке правое поддерево.

Рекурсивная процедура добавления последовательно по одному узлу в прямом порядке:

procedure Create(var p: tree); { указатель на созданную вершину – выходной параметр процедуры }

var

c: char;

begin

read(c);

if c <> ’.’ then

begin

new(p);

p^.data:= c;

Create(p^.left); { рекурсивный вызов по левой ветви }

Create(p^.right); { рекурсивный вызов по правой ветви }

end

else

p:= Nil;

end;

Для построения всего дерева обращение к данной процедуре Create должно происходить только один раз в главной программе или другом вызывающем модуле:

Create(Root);

Прохождение бинарного дерева в обратном порядке (обход снизу вверх) можно определить таким описательным рекурсивным алгоритмом

· пройти в обратном порядке (от листьев к узлу, от потомка к предку) левое поддерево;

· пройти в обратном порядке правое поддерево;

· попасть в корень.

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

· пройти в симметричном порядке (от листа к узлу, от узла к листу) левое поддерево;

· попасть в корень;

· пройти в симметричном порядке правое поддерево.

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