Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

{ОЛ, Робот в листе}

обработать;

{ОЛН}

end;

Основной алгоритм:

дано: Робот в корне, листья не обработаны

надо: Робот в корне, листья обработаны

{ОЛ}

вверх_до_упора_и_обработать

{инвариант: ОЛН}

while есть_снизу do begin

if есть_справа then begin {ОЛН, есть справа}

вправо;

{ОЛ}

вверх_до_упора_и_обработать;

end else begin

{ОЛН, не есть_справа, есть_снизу}

вниз;

end;

end;

{ОЛН, Робот в корне => все листья обработаны}

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

{ОЛ, не есть_сверху} обработать {ОЛН} {ОЛ} вверх_налево {ОЛ} {есть_справа, ОЛН} вправо {ОЛ} {не есть_справа, ОЛН} вниз{ОЛН}

Теперь решим задачу об обходе дерева, если мы хотим, чтобы обрабатывались все вершины (не только листья).

Решение. Пусть x - некоторая вершина. Тогда любая вершина y относится к одной из четырех категорий. Рассмотрим путь из корня в y. Он может:

а) быть частью пути из корня в x (y ниже x);

Рекомендуем скачать другие рефераты по теме: 5 баллов рефераты, отчет по производственной практике.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки