The files RELATE1.DAT, RELATE2.DAT, and RELATE3.DAT contain relationship records involving the ancestors of one person. The name of this person is in the first record in each file; other records (each on one line) have one of two forms

     X mother of Y            or            X father of Y

For your last assignment, write a program that reads in these relationship records and forms a binary tree that shows the first person's genealogy (sort of an up-side-down family tree). The first person should be made the root of the tree, with his/her parents on the second level, his/her grandparents on the third level, etc. The relationship records are in the file such that the "Y" name is always in the tree and the "X" has to be added. For a record such as "X mother of Y", X should be made the left child node of Y in the tree. For a "X father of Y", X should be made the right child node of Y in the tree. For example, consider the tree which is made from the following data.

PAT
WARREN father of PAT 
MORRIS father of WARREN
CAROLINE mother of WARREN        
NANCY mother of PAT  
BEATRICE mother of CAROLINE      
HAROLD father of NANCY
LYDIA mother of MORRIS 

Notice the data; there is one space between the relationship and the names that are before and after it.

Usually, a person's genealogy tree is far from complete. In this example, NANCY's mother is not specified, as are the fathers of CAROLINE and MORRIS. Regardless of how complete the tree is, after all the data is read in, your program must list the people in the tree left to right by generation; that is, by level within the tree. For the example data, the generation listing should look like this for PAT.

 
     Generation     People
          0         PAT
         -1         NANCY       WARREN
         -2         HAROLD      CAROLINE    MORRIS
         -3         BEATRICE    LYDIA

To do this project, you must write a main function, define a binary tree class, and create whatever member functions are needed to accomplish the assigned task. The main function must repeatedly prompt for a file name, read in the relationship records, and then display the genealogy. The program should terminate if the entered file name is STOP. To aid you, the definition and member functions of a Queue class are provided in the file QUEUE2.H. You should find that a queue will be useful in generating the level-by-level listing of the genealogy.

All files mentioned are in O:\JLW\310 in Johnson, L:\JLW\310 in Tompkins, and 310LIB: on the mainframe.

Handin a diskette with your program on it and a printout of the source code.


EXTRA CREDIT: A fourth data file, RELATE4.DAT, contains relationship records but NOT in an order that guarantees that Y is already in the tree for a record such as X father of Y For extra credit, construct the genealogy for the person in RELATE4.DAT and display the tree level by level. You will find that this small change in the data creates several complications in forming the genealogy tree.