The Problem

        a
     /  |  \
    b   c   d
       / \   \
      e   f   g

is represented as :

node(a,[node(b,[]),node(c,[node(e,[]),node(f,[])]),node(d,[node(g,[])])])

You are to write a Prolog program that builds arbitary trees in this representation, prints out the function representation, prints out the node values in preorder search order, and allows the user to search for values in the tree. The values in the nodes are Prolog atoms. The tree must be stored in a variable, not in the Prolog database (i.e., it cannot be asserted and retracted). Initially the tree is empty, and is represented by nil. Your program must repeatedly offer the user a menu with the options :

B Build a new tree (any existing tree is discarded). The program must prompt for the root node value then recursively build the subtrees by asking for lists of offspring values.

F Print out the function representation.

P Print out the node values in preorder search order.

C Check if a value is in the tree, and if it is, print the node values on the path from the root to that node.

X Exit

Submission

• A print out of your source code [3%]

  Your coding will be examined for

  • Correctness of your internal data structure [1%]

  • Good Prolog programming [1%]

  • Formatting, commenting, meaningful identifiers [1%]

• A print out of a test run of the following sequence [7%]

  | ?- go

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : F

  nil (Print initially empty tree) [0.5%]

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : P

  (Preorder search of an empty tree) [0.5%]

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : B

  Root node value : mat.

  Offspring node values for mat : [].

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : F

  node(mat,[]) (Tree with one node) [0.5%]

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : P

  mat (Preorder search of a tree with one node) [0.5%]

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : B

  Root node value : a.

  Offspring node values for a : [b,c,d].

  Offspring node values for b : [].

  Offspring node values for c : [e,f].

  Offspring node values for e : [].

  Offspring node values for f : [].

  Offspring node values for d : [g].

  Offspring node values for g : [].

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : F

  node(a,[node(b,[]),node(c,[node(e,[]),node(f,[])]),node(d,[node(g,[])])])

  (Example tree) [1.5%]

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : P

  a b c e f d g (Preorder search of example) [1%]

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : C

  Enter search value : f.

  a c f (Check value that is there) [1.5%]

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : C

  Enter search value : hat.

  Value not in tree (Check value that is not there) [1%]

  (B)uild, (F)unction, (P)reorder, (C)heck, e(X)it : X

  Bye