Trees in Prolog

Question

I am studying binary trees in Prolog.

I know the structure but I don't understand this code in my slides:

binary_tree(void).
binary_tree(tree(_Element,Left,Right)) :-
  binary_tree(Left), binary_tree(Right).

This would need for recognize the tree structure.

But does "void" represent?

I tried this query

?- binary_tree(a).
false.

and assume that a is one node of a tree.

I'm following this resource for understanding:

https://sites.google.com/site/prologsite/prolog-problems/4

but is different to my slides.

Can anyone clarify this?

Answer 1

void is an atom. It cannot assume any values (other than itself). In addition, a, also an atom, is not a valid tree per your predicate definition. A tree with a as its only node would be represented by the compound term tree(a,void,void):

| ?- binary_tree(tree(a,void,void)).

yes

As another example, a balanced tree with nodes a..g would be represented by the term (written indented just for readability):

   tree(a,
       tree(b,
           tree(d,void,void),
           tree(e,void,void)
       ),
       tree(c,
           tree(f,void,void),
           tree(g,void,void)
       )
    )

You can verify that this term is a tree again using your binary_tree /1 predicate:

| ?- binary_tree(tree(a,tree(b,tree(d,void,void),tree(e,void,void)),tree(c,tree(f,void,void),tree(g,void,void)))).

yes