This program performs breadth-first traversal of a tree,
placing the results in a list in that order.
It can be run in "reverse"
(also see Append)
to find those trees, if any, that would give a particular
list when traversed:
append(nil, B, B).
append(cons(A,As), B, cons(A, AsB))
<= append(As, B, AsB).
bft(nil, nil).
bft(cons(fork(empty, E, empty), Q), cons(E, BFL))
<= bft(Q, BFL).
bft(cons(fork(empty, E, R), Q), cons(E, BFL))
<= append(Q, cons(R,nil), Q2) and bft(Q2, BFL).
bft(cons(fork(L, E, empty), Q), cons(E, BFL))
<= append(Q, cons(L,nil), Q2) and bft(Q2, BFL).
bft(cons(fork(L, E, R), Q), cons(E, BFL))
<= append(Q, cons(L,cons(R,nil)), Q2) and bft(Q2, BFL).
{Query:}
? bft(cons(T,nil), cons(a, cons(b, cons(c, nil)))).
{comment one query out:
? bft(cons(fork(fork(empty,1,empty),
2,
fork(empty,3,empty)), nil), BFL).
}
{Loosely based on csc3030 Programming Paradigms exam Q5 1994}
{have to make the rules exclusive and exhaustive for the toy}
{interpreter - muprolog is cleverer }
{see the muprolog examples directory for the real thing. }
There are, in general, multiple trees that would give the
same breadth-first order to a given list of nodes.
Infix Tree Traversal
A program can easily be written
to perform infix traversal of a binary tree.
However this will not easily run backwards
in a Prolog system with only a simple top-down left-to-right
evaluation strategy.
Either a more complex evaluation strategy is needed
or the program must be modified:
append(c(H,T), L, c(H,T2)) <= append(T, L, T2).
append(nil, L, L).
unground(someUniqueNonsense).
{a hack! eg. unground(X) }
ground(X) <= not unground(X).
{a hack! eg. ground(c( , )) }
{does not consider the possibility of}
{being partially ground.}
{-----------------}
{only if the tree is ground, loops otherwise:}
infix1(fork(L,E,R), INF)
<= infix(L, LI) and infix(R, RI) and
append(LI, c(E,RI), INF) .
{only if the list is ground, loops otherwise:}
infix2(fork(L,E,R), INF)
<= append(LI, c(E,RI), INF) and
infix(L, LI) and infix(R, RI) .
infix(leaf(L), c(L,nil)).
infix(T,L) <= ground(T) and infix1(T,L).
infix(T,L) <= ground(L) and infix2(T,L).
{Query:}
? infix(T, c(1,c(2,c(3,c(4,c(5,nil))))) ).
{other query commented out:
? infix( fork(fork(leaf(1),2,leaf(3)),
4,
fork(leaf(5),6,leaf(7))), L).
}
{ Infix tree traversal, assumes strict top-down }
{ left-to-right search. Loosely based on CSC3030 }
{ Programming Paradigms exam, Q3; June 1993. }
{ Muprolog does not need the hack because it can }
{ dynamically reorder atoms within the query. }
{ The proper (Muprolog) example is in another directory. }