Prolog logical programming Binary tree predicates

Question

I am a total beginner to logic programming and Prolog so the problem is that i am trying to implement a binary tree in Prolog which i did like this:

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

now i need to implement the following predicates

count(X,Tree,Res). which should count how many times X is given in the passed tree and return it in Res.

sum(Tree, Sum). which should return the Sum of all Nodes in the passed tree if Numerical. My idea for this one was something like this:

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

replace(X , Y, TreeIn , TreeOut). which should swap every Node containing X with Y in TreeIn and return TreeOut.

Nicholas Carey Nicholas Carey · Accepted Answer · 2020-01-10T00:29:21

A binary tree is just a data structure. I would represent it as something like tree(L,R,V), where

L is the left subtree,
R is the right subtree, and
V is the value of that node.

Taking a cue from how lists are represented in Prolog, we can use an atom nil to represent a non-existent subtree, so a leaf node would look like this tree(nil,nil,123) So, for a tree that looks like this:

you would have this Prolog structure:

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

Then it's a simple matter of walking the tree to do what you want. For instance,

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.

Sandbox is at https://swish.swi-prolog.org/p/ncarey-binary-tree.pl

Prolog logical programming Binary tree predicates

1 Answers