Got Questions? Try office hours, email or the newsgroup git.cc.class.3411.

Recursive Data Structures

For your first programming assignment this quarter, you will write a collection of  rules for representing and manipulating binary trees in Prolog. You will use Prolog's two primary data structuring mechanisms for this assignment: symbolic structures and lists. Prolog structures are something like records in imperative programming languages but they are more powerful. Prolog lists are similar to lists in Lisp. Both structures and lists are fundamentally recursive. Structures are the more basic mechanism because the Prolog list notation can be viewed as "syntactic sugar" for a more primitive structure-based representation of lists.

Here is a fact represented by a simple Prolog structure:

    book( moby_dick, author( herman, melville ) ).

This fact can be visualized as a binary tree but structures can, in general, have any number of members ("arity"). As usual, things get more interesting when we allow structures to contain logical variables. Structures with self-similar components are easily manipulated by recursive rules so we call them  "recursive structures." Binary trees can be easily represented in Prolog by recursive structures. Here is a simple rule that defines binary trees in Prolog:

   /** binary_tree(Tree) :-
        Tree is a binary tree. */
   binary_tree(void).
   binary_tree(tree(Element,Left,Right)) :-
        binary_tree(Left), binary_tree(Right).

Given our recursive tree definition, we can pretty easily write a rule that determines if a given element appears anywhere in a given binary tree:

/** tree_member(Element,Tree) :-
    Element is an element of the binary tree Tree. */
tree_member(X,tree(X,Left,Right)).
tree_member(X,tree(Y,Left,Right)) :- tree_member(X,Left).
tree_member(X,tree(Y,Left,Right)) :- tree_member(X,Right).

Here is another  recursive rule that implements a preorder traversal of

/** preorder(Tree,Pre) :-
    Pre is a list of elements of Tree accumulated during a
    preorder traversal. */
preorder(tree(X,L,R),Xs) :-
    preorder(L,Ls), preorder(R,Rs), append([X|Ls],Rs,Xs).
preorder(void,[]).

Here is the rule for append:

/** append(Xs,Ys,XsYs) :-
     XsYs is the result of appending the lists Xs and Ys. */
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).

Implement the following rules:

1. inorder(Tree,In) :- In is a list containing an inorder traversal of the elements of Tree.
   
   
2. isotree(Tree1,Tree2) :- Tree1 and Tree2 are isomorphic binary trees.
   Two binary trees are isomorphic if you can derive one from the other by changing the order of the branches.
   
   
3. subtree(S,T) :- S is a subtree of T.
   
   
4. sum_tree(TreeOfIntegers,Sum) :- calculate or verify that Sum is the sum of the integer elements in TreeOfIntegers. (Hint: You will need to use the "is" operator.)
   
   
5. ordered(TreeOfIntegers) :- holds if TreeOfIntegers is a binary search tree without duplicates. That is, for each node in the tree with element e, all the elements in the left subtree are smaller than e and all the elements in the right subtree are larger than e. (Hint: Define two helper rules ordered_right(X, Tree) and ordered_left(X,Tree) that hold if Tree is ordered and also obey the appropriate less than or greater than property.)
   
   
6. path(X,Tree,Path) :- Path is a list containing the elements along the path of nodes from the root of Tree to X. (Note: For arbitrary binary trees there may be more than one such path.)

Create a single file called tree that contains all the facts and rules for the assignment. "Consult" this file each time you start prolog. Begin with VERY SIMPLE RULES and gradually add complexity and more rules. The "development environment" for our version of Prolog is hard to love. Do the best you can with it. Brian has prepared a nice Web page with helpful hints and we will provide additional supporting material, including several demo programs, in the coming weeks.

You will need to use one trick to make life easier while developing your programs. Since typing in complex tree structures is tedious and error prone, you should define a few "named trees" like this at the beginning of your tree module:

/* Define a few trees to work with. */
tree1(tree(a,tree(b,void,void),tree(c,void,void))).
tree2(tree(d,tree(e,void,void),tree(f,void,void))).
tree3(
        tree(   a,
                tree(   b,
                        tree(e,void,void),
                        tree(   f,
                                tree(g,void,void),
                                void
                        )
                ),
                tree(c,void,void)
        )
).

   prolog
    ?- [tree].  /* consult the file containing the tree facts and rules */
    ?- tree2(A), tree_element(e,A). /* does e appear in tree2? */

Helpful Advice

You have 4 weeks to complete this assignment! That's a lot of time but it takes awhile for the "Prolog way of thinking" to sink in. Work steadily and incrementally. Spend a bit of time on a regular basis working with the Prolog interpreter, reading reference material and working through the assignment. Ask questions when strange things happen. Stay-tuned to the newsgroup for turnin details and related assignment announcements.

    Good luck! Start Early! Use Office Hours Often!