Обход дерева

Прежде чем продолжить рассмотрение того, как создать дерево, давайте

подумаем, что с ним делать, если оно уже есть. Одной из наиболее частых

операций с деревом является исследование всех узлов и обработка их неко-

торым образом, либо поиск некоторого значения, либо поиск всех значений.

Эти процедуры известны как обход дерева. Основной алгоритм для этого сле-

дующий:

1. Если дерево пусто, то ничего не делать.

2. Иначе, обработать текущее значение, затем перейти на левое подде-

рево, затем перейти на правое поддерево.

Как и само дерево, алгоритм является рекурсивным: он обрабатывает

левое и правое поддеревья так же, как и исходное дерево. В Прологе он вы-

ражается двумя предложениями: одно для пустого, а другое для непустого

дерева.

traverse(empty). /* ничего не делать */

traverse(tree(X, Y, Z)) :-

do something with X,

traverse(X),

traverse(Z).

: |

1 |

:. |

.. Cathy

: / \

: / \

2 / \

: / \

: / 5... \

.... Michael : Melody

3 / \ : /: \

: / ....\ : /.6 ...\

Charles : Hazel :Jim : Eleanor

:.....4.: :..: :..7.:

Рис.7.2 Обход дерева с рис. 7.1 "сначала вглубь"

Этот алгоритм известен как поиск "сначала вглубь", так как он спус-

кается по каждой ветви вниз, насколько возможно, прежде чем вернуться

вверх для обхода другой ветви (рис. 7.2). Чтобы посмотреть алгоритм в

действии, взгляните на программу CH07EX09.PRO, которая обходит дерево и

печатает все элементы, которые ей попадаются. Дерево, показанное на ри-

сунках 7.1 и 7.2, CH07EX09.PRO распечатает

Cathy

Michael

Charles

Hazel

Melody

Jim

Eleanor

Конечно, вы можете легко приспособить программу для выполнения ка-

ких-то других операций над элементами, а не печати их.

/* Программа CH07EX09.PRO */

/* Обход дерева "сначала вглубь" и печать каждого элемента, ко-

торый попадается на пути. */

domains

treetype = tree(string, treetype, treetype) ; empty()

predicates

print_all_elements(treetype)

clauses

print_all_elements(empty).

print_all_elements(tree(X, Y, Z)) :-

write(X), nl,

print_all_elements(Y),

print_all_elements(Z).

goal

print_all_elements(tree("Cathy",

tree("Michael",

tree("Charles", empty, empty),

tree("Hazel", empty, empty)),

tree("Melody",

tree("Jim", empty, empty),

tree("Eleanor", empty, empty)))).

Поиск "сначала вглубь" исключительно прост для способа, которым Про-

лог ищет базу знаний. Он организует предложения в дерево и проходит каж-

дое поддерево, пока предложения не закончатся. Если бы вы захотели, то

могли бы описать дерево посредством набора прологовских правил, таких

как:

father_of("Cathy", "Michael").

mother_of("Cathy", "Melody").

father_of("Michael", "Charles").

mother_of("Michael", "Hazel").

...

Это было бы предпочтительнее, если бы дерево предназначалось только

для выражения родственных связей между людьми. Но, такой вид описания де-

лает невозможным обработку всего дерева как единой, сложной структуры

данных. Как вы увидите, комплексные структуры данных бывают весьма полез-

ными, так как они упрощают сложные вычислительные задачи.