Прологическое логическое программирование Предикаты двоичного дерева

Question

Я абсолютный новичок в программировании c и прологе, поэтому проблема в том, что я пытаюсь реализовать двоичное дерево в Прологе, что я сделал так:

tree(-). 
tree(n(X,L,R)):- tree(L), tree(R).

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

count(X,Tree,Res)., которые должны подсчитывать, сколько раз X дается в переданном дереве, и возвращать его в Res.

sum(Tree, Sum)., который должен возвращать сумму всех узлов в переданное дерево, если числовое. Моя идея для этого была примерно такой:

treeSum([],0).
treeSum(tree(X,T1,T2), S) :-
   treeSum(T1,S1),
   treeSum(T2,S2),
   S is X + S1 + S2.

replace(X , Y, TreeIn , TreeOut)., которая должна поменять местами каждый узел, содержащий X, с Y в TreeIn и вернуть TreeOut.

Answer 1

Бинарное дерево - это просто структура данных. Я хотел бы представить его как что-то вроде tree(L,R,V), где

• L - левое поддерево,
• R - правое поддерево, а
• V - это значение этого узла.

Подчеркнув, как списки представлены в Прологе, мы можем использовать атом nil для представления несуществующего поддерева, поэтому листовой узел будет выглядеть следующим образом: tree(nil,nil,123) Итак, для дерева, которое выглядит следующим образом:

     4
    / \
   2   5
  / \   \
 1   3   6

у вас будет такая структура Пролога:

tree(
  tree(
    tree(
      .,
      .,
      1
    ),
    tree(
      .,
      .,
      2
    ),
    3
  ),
  tree(
    .,
    tree(
      .,
      .,
      6
    ),
    5
  ),
  4
)

Тогда просто пройтись по Дерево, чтобы делать то, что вы хотите. Например,

sum( nil         , 0 ).
sum( tree(L,R,V) , S ) :-
  sum( L , SumL ),
  sum( R , SumR ),
  S is V + SumL + SumR
  .

count( _, nil, 0 ). 
count( X, tree(L,R,V), C) :-
  count(X,L,Lefts),
  count(X,R,Rights),
  ( X = V -> N = 1 ; N = 0 ) ,
  C is N  + Lefts + Rights. 

Песочница находится в https://swish.swi-prolog.org/p/ncarey-binary-tree.pl