Prolog - Tree Traversal.

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

Logic
 Prolog
  Introduction
  Examples

Breadth First Tree Traversal

This program performs breadth-first traversal of a tree, placing the results in a list in that order. It can be run in "reverse" (see also 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. }


Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Friday, 29-Mar-2024 05:19:08 AEDT.