Пример. Напишем предикат, подсчитывающий общее количество вершин дерева . У него будет два параметра. Первый (входной) параметр - дерево , второй (выходной) - количество вершин в дереве .

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

Пишем:

tree_length (empty,0). /* В пустом дереве
                  нет вершин */
tree_length(tr(_,L,R),N):-
        tree_length (L,N1), 
            /* N1 - число вершин 
             левого поддерева */
        tree_length (R,N2), 
            /* N2 - число вершин 
             правого поддерева */
        N=N1+N2+1. /* число вершин 
              исходного дерева 
              получается сложением 
              N1, N2 и единицы */

Пример. Решим еще одну подобную задачу. Разработаем предикат, подсчитывающий не общее количество вершин дерева , а только количество листьев , т.е. вершин, не имеющих сыновей. Предикат будет иметь два параметра. Входной - исходное дерево , выходной - количество листьев дерева , находящегося в первом параметре.

Понятно, что, так как в пустом дереве нет вершин, в нем нет и вершин, являющихся листьями . Это первый базис рекурсии. Второй базис будет заключаться в очевидном факте, что дерево , состоящее из одной вершины, имеет ровно один лист . Шаг: для того, чтобы посчитать количество листьев дерева , нужно просто сложить количество листьев в левом и правом поддереве.

Запишем:

tree_leaves(empty,0). /* в пустом дереве
                  листьев нет */
tree_leaves(tr(_,empty,empty),1):-!. 
          /* в дереве с одним корнем - 
            один лист */
tree_leaves(tr(_,L,R),N):-
        tree_leaves(L,N1), 
          /* N1 - количество листьев 
            в левом поддереве */
        tree_leaves(R,N2), 
          /* N2 - количество листьев 
            в правом поддереве */
        N=N1+N2.

Пример. Создадим предикат, находящий сумму чисел, расположенных в вершинах дерева . Он будет иметь два аргумента. Первый - исходный список, второй - сумма чисел, находящихся в вершинах дерева , расположенного в первом аргументе.

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

На Прологе это записывается следующим образом:

tree_sum (empty,0). /* В пустом дереве
                  вершин нет */
tree_sum(tr(X,L,R),N):-
       tree_sum (L,N1), 
           /* N1 - сумма элементов 
            левого поддерева */
       tree_sum (R,N2), 
           /* N2 - сумма элементов 
            правого поддерева */
       N=N1+N2+X. /* складываем N1, N2 
             и корневое значение */

Пример. Создадим предикат, позволяющий вычислить высоту дерева . Напомним, что высота дерева - это наибольшая длина пути от корня дерева до его листа . Предикат будет иметь два параметра. Первый (входной) - дерево , второй (выходной) - высота дерева , помещенного в первый параметр.

Базис рекурсии будет основан на том, что высота пустого дерева равна нулю. Шаг рекурсии - на том, что для подсчета высоты всего дерева нужно найти высоты левого и правого поддеревьев, взять их максимум и добавить единицу (учесть уровень, на котором находится корень дерева ). Предикат max (или max2), вычисляющий максимум из двух элементов, был разработан нами еще в третьей лекции. Мы воспользуемся им при вычислении высоты дерева .

Получается следующее.

tree_height(empty,0). /* Высота пустого 
          дерева равна нулю */
tree_height(tr(_,L,R),D) :- 
        tree_height(L,D1), 
         /* D1 - высота левого 
               поддерева */ 
        tree_height(R,D2), 
         /* D2 - высота правого
               поддерева */
        max(D1,D2,D_M), 
         /* D_M - максимум из высот 
          левого и правого поддеревьев */
        D=D_M+1. 
         /* D - высота дерева получается 
          путем увеличения числа D_M 
          на единицу*/

Существует особый вид бинарных деревьев - так называемые двоичные справочники . В двоичном справочнике все значения, входящие в левое поддерево, меньше значения, находящегося в корне , а все значения, расположенные в вершинах правого поддерева, больше корневого значения, а левое и правое поддеревья, в свою очередь, также являются двоичными справочниками . Такие деревья еще называют упорядоченными слева направо.

Пример. Усовершенствуем предикат tree_member для проверки принадлежности значения двоичному справочнику . Повысить эффективность этого предиката мы сможем, воспользовавшись тем, что в двоичном справочнике если искомое значение не совпадает с тем, которое хранится в корне , то его имеет смысл искать только в левом поддереве, если оно меньше корневого, и, соответственно, только в правом поддереве, если оно больше корневого значения.

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

tree_member2(X,tr(X,_,_)):-!. /* X - корень
                   дерева */
tree_member2(X,tr(K,L,_)):-
        X<K,!,
        tree_member2(X,L). 
           /* X - принадлежит 
            левому поддереву */
tree_member2(X,tr(K,_,R)):-
        X>K,!,
        tree_member2(X,R). 
           /* X - принадлежит 
            правому поддереву */