Programming Project 3

This project will be due by 5 pm, Friday, October 31. To submit your project, save it in the pp3 directory located in your directory under /home/libs/dataStr/students/ on one of the department's Linux machines (this is a shared directory, so you should be able to reach it from any of the machines, including Jupiter).

You may work on this project by yourself or in a group of two or three. If you work in a group, be sure to include everyone's name in the comments at the top of each file. Also, be sure you understand the guidelines for group work listed in the syllabus--the fundamental idea is that everyone in the group should understand what everyone else has done, and be able to recreate it on their own.

The project is to create a program that can manage a simple family tree. The operations you will need to support are: reading the tree from a file, displaying the tree on the screen, and querying family relationships in the tree. Each of these will be described in more detail below.

The simplified family tree we will work with is in fact a binary tree (surprise!). Therefore, each person has at most two children, and each child has only one parent. For the rest of this handout, consider the following example:

$\begin{figure}\begin{center} \sf\bfseries\footnotesize {\color{white}\setlength\... ...pstree{\Toval{Bruce}}{ \Toval{Brittany} \Tn } } }}} \end{center}\end{figure}$

The first operation is reading the tree from a file. Each line of the file will describe one person, in a preorder traversal. That is, the first line will be the root (Helen, in the example), the next line will be the left child (Frank), followed by the left child's descendents; after the entire left subtree (which ends with Susanna in the example), the file ends with the root's right subtree (from Esther to Brittany). You may assume that no name contains spaces. To specify the structure of the tree, each line will also include a number indicating how many children that person has (0, 1, or 2). Therefore, the example above would be represented by the following file:

Helen 2
Frank 2
Alan 0
Brian 2
George 0
Susanna 0
Esther 2
Amy 0
Bruce 1
Brittany 0

The second operation is displaying the tree on the screen. Use the inorder traversal method that I describe in class, where each successive level is indented a few more spaces. For the example, the output should look something like this:

    Alan
  Frank
      George
    Brian
      Susanna
Helen
    Amy
  Esther
      Brittany
    Bruce

Finally, the third operation is to ask the user for a name and search for that name in the tree. If it is found, you should print out the relationship to the root, otherwise print "no relation" (see examples below). You may assume that there are no duplicate names in the family.

For extra credit, you may extend this operation to request two names, and respond with the relationship between the two people (if any); for example, on input Brian and Alan it should say "sibling", while on input Brian and Brittany it should say "first cousin once removed" (talk to me if you want to know the rules for this).

The main program should get a file name, read in the tree, display it, and then enter a loop where it repeatedly asks for a name (or two names, in the extra credit version) and displays the relationship. When the user enters the name "DONE", the program should exit. Here is a sample run (starting after the tree is printed out, as above):

Name? Helen
Relationship: self

Name? Brian
Relationship: grandchild

Name? Esther
Relationship: child

Name? Susanna
Relationship: great grandchild

Name? Eleanor
Relationship: no relation

Name? DONE
Goodbye