Обход дерева

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

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

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

Как и само дерево, алгоритм является рекурсивным: он обрабатывает левое и правое поддеревья так же, как и исходное дерево. В Прологе он выражается двумя предложениями: одно для пустого, а другое для непустого дерева.

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

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

do_something_with_X,

traverse(Y),

traverse(Z).

Этот алгоритм известен как поиск "сначала – вглубь", т.к. он спускается по каждой ветви вниз, насколько возможно, прежде чем вернуться вверх для обхода другой ветви (рисунок 2). Он организует предложения в дерево и проходит каждое поддерево, пока предложения не закончатся. Вымогли бы описать дерево посредством набора правил Пролога, таких как:

father_of("Cathy", "Michael").

mother_of("Cathy", "Melody").

…

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