CS251代写、代做Data Structures、代写Java程序语言、Java代做

日期：2018-12-04 10:19

CS251: Data Structures and Algorithms

Fall 2018

Project 4: Family Trees

Max Points: 100

Deadline: November 30, 2018

Overview:

The purpose of this project is to teach the students how to come up with appropriate data

structure for a given problem statement and how to use relevant algorithms to solve the given

problem. In this project, we are going to work on genealogical data. Genealogical data is often

represented in tree formats. We will implement the functionalities of Family Tree data structure, and

then we will use the data structure to encode family relations. Finally we will be answering queries

about pairs of people in the tree by traversing the tree.

Family Tree:

A family tree is a set of nodes, representing people, stored in a parent-child relationship, with the

following properties:

1. Each node has either 0 or 2 parents listed in the tree.

2. Each node may have any number of children listed in the tree.

3. Node A is a descendant of Node B if B is A's parent or A's grandparent, etc.

4. If Node A is a descendant of Node B, then the distance between them is the number of

generations between them. If B is A's parent, the distance is 1. If B is A's grandparent, the distance

is 2, etc.

5. Node A is an ancestor of Node B if B is a descendant of A.

6. Two nodes are related if they have a common ancestor listed in the tree. According to this

definition, husband and wife are not related.

7. The distance between two related nodes via a common ancestor is the sum of the distances

between each of them and that common ancestor.

Example: Say, A,B,C are three nodes in a family tree. If distance between A & C, dist(A, C) = 4 and

distance between B & C, dist(B, C) = 6, then dist(A, B) = 10

8. The closest common ancestor of two related nodes is a common ancestor who minimizes the

distance between them. Note that two related people may have several closest common ancestors.

For example, if two brothers marry two sisters, their children will have all four grandparents (two in

maternal side, two in paternal side) as closest common ancestors.

Implementation Details:

Part 1: Build the Family Tree

The family tree class should have variables and methods that follows and imposes all the family tree

properties. You have to think of the appropriate data structure to implement this. You will use the

input files (family history records) to create the tree. Each input file corresponds to a different

family tree.

You will implement this part in buildFamilyTree(String inputFile) function where

inputFile is the name or filepath of the input file. Structure of each input file is

explained below in File section.

Part 2: Output the queries

The query files consist of queries about the family. Each line of the file corresponds to a query. Each

query involves two persons. You will implement this in evaluate(String queryFile,String

outputFile) function where queryfile contains the queries about each tree.

You will write all your outputs in outputFile.

Structure of each query file and expected structure of output file is explained below in

File section.

Putting it altogether

There can be multiple number of input files, and for each input files there will be a corresponding

query and output file. For example,

query1.txt holds all the queries that correspond to the family tree for records in input1.txt,

and you should write the query results for queries in query1.txt to out1.txt and so on.

All these are handled in the test cases. If you want to test your input and output use the appropriate

files corresponding to the naming convention that we used i.e, if you use input1.txt, you should use

query1.txt and match the output with out1.txt and so on. And to understand how everything comes

together, you should take a look at the runCase() method in FamilyTreeTest.java.

File Section:

Sample files are attached with the skeleton code.

Input Files:

Input files hold the family history records. The family history records will describe one family in each

line. Each record will occupy one line of input and list two or more names in the order: husband,

wife, their children, if any. Each name is a sequence of alphabetic characters separated by

blanks. End of file marks the termination of inputs.

For each of the input files there is a query file and an output file. See details below.

Query Files:

The query files consist of queries, one per line, each line containing exactly two names separated by

blanks. The query files contain multiple queries about the corresponding family tree. End of file

marks the termination of queries.

Output Files:

For each line in the query files your program will print one of the following lines in the output file:

1. If the two people are unrelated (within the tree), print "unrelated".

2. If one person is a descendant of the other, print

"<name1> is a descendant of <name2>".

<name1> and <name2> should be the two input names. They should be in the order that makes the

statement true. For details see #4 in the definition of Family Tree.

3. If the two people are related (within the tree), but one is not a descendant of the other, then list the

names of all of their closest common ancestors sorted in lexicographical order, each on a separate

line.

For details on lexicographical ordering you can check this link -

https://chortle.ccsu.edu/java5/Notes/chap92/ch92_2.html

You should assume the following for inputs -

1. There are one or more blanks between names and zero or more blanks at the beginning and

end of each line.

2. Lines in the family history section will have at least two names (Husband & Wife, since they

can have 0 or more children).

3. Lines in the query files will have exactly two names.

4. Names appearing in the query files will have appeared in the family history section.

5. Different people in the tree have different names. Names are case sensitive.

** Your program may not use JavaFx classes.