# Prolog - Tree Traversal.

 home  Bib  Algorithms  Bioinfo  FP  Logic  MML  Prog.Lang and the  mmlist

Logic
Prolog
Introduction
Examples

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.

 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. }

### 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. } ```
 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. }
window on the wide world:
 The Darwin Awards V: Next Evolution

 Linux  Ubuntu free op. sys. OpenOffice free office suite, ver 3.4+ The GIMP ~ free photoshop Firefox web browser FlashBlock like it says!

 © 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 Thursday, 29-Oct-2020 04:32:45 AEDT.