Homework SourseNeed help with Java homework please You are to write a progr
Need help with Java homework please!!
You are to write a program that handles a family tree structure. Since there is no restriction on the number of children that any person in the family has, the family tree must be a general tree. The family tree structure keeps track of only one parent of each node (you can think of this as a “descendants view”, in which we are interested only in showing the descendants of a given ancestor). Each node stores 2 pieces of information: a name and a year of birth. Note that there are no restrictions on the number of family members with the same name, or on the number of family members born in the same year; however, for any given node, the year of birth must always be later than the year of birth of its parent.
You may assume that names are strings containing only upper- or lower-case alphabetic characters with no white space. You may also assume that this is strictly a tree, i.e. it is connected and there are no cycles.
You must implement all of the following in your program:
Recursive preorder traversal
Recursive postorder traversal
Breadth-first traversal (does not need to be recursive)
For given names name1 and name2, find all common ancestors for every pair of nodes (n1,n2) in which n1.name = name1 and n2.name = name2, from the most recent common ancestor to the least recent common ancestor. In the case that n1 is an ancestor of n2, then n1 should also be returned as an ancestor, and similarly for the case that n2 is an ancestor of n1. Hint: although it is not a requirement, consider using a pair of stacks in your implementation.
Input: Your program should read from a file; this file has the following format:
The name and year of birth for the root.
For each node in the tree (in preorder):
An integer value indicating that the node has n children
The name and year of birth of the 1st child
<Information for descendants of the 1st child, in preorder>
The name and year of birth of the 2nd child
<Information for descendants of the 2nd child, in preorder>
etc.
An integer value m, specifying the number of common ancestor checks desired.
A sequence of m lines, each containing 2 names for which we wish to find all common ancestors.
Important note: it is possible for the tree to be empty. In this case, either the file is completely empty, or it starts with an integer (since you can assume that all names consist of alphabetical characters only). This is a difficult case to handle but it will be allocated a small number of marks. You are advised to ensure that your program works properly for non-empty trees first, since this will be worth far more marks.
Output: After creating the tree, the following steps should be performed:
Print “Preorder traversal” and print the contents of the nodes, one per line, in preorder
Print “Postorder traversal” and print the contents of the nodes, one per line, in postorder
Print “Breadth-first traversal” and print the contents of the nodes, one per line, in breadth-first order
For each pair of nodes matching each pair of names (name1, name2) print “Common ancestors of (name1, year1) and (name2, year2):” followed by the list of common ancestors in the format shown above.
Solution
There are two classes below: FamilyTree and TreeNode. In the main method of FamilyTree, change the file path and run.
-------------------------------------------
FamilyTree.java
-------------------------------------------
package chegg.tree;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class FamilyTree {
private TreeNode root;
private List<TreeNode> nodesList;
private BufferedReader reader;
public FamilyTree(String path) throws IOException {
reader = new BufferedReader(new FileReader(path));
nodesList = new ArrayList<TreeNode>();
buildTree(null);
}
public TreeNode getRoot() {
return root;
}
public void buildTree(TreeNode parent) throws IOException {
String line = reader.readLine();
TreeNode newnode = null;
if (line != null) {
newnode = TreeNode.parseLine(line);
newnode.setParent(parent);
nodesList.add(newnode);
}
if (root == null && newnode != null)
root = newnode;
if ((line = reader.readLine()) != null) {
for (int i = 0; i < Integer.parseInt(line); i++)
buildTree(newnode);
}
}
public void preorder(TreeNode parent) {
System.out.println(parent.toString());
for (TreeNode child : children(parent))
preorder(child);
}
public void postorder(TreeNode parent) {
for (TreeNode child : children(parent))
postorder(child);
System.out.println(parent);
}
public void breadthfirst() {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
TreeNode currentNode = null;
while ((currentNode = queue.poll()) != null) {
System.out.println(currentNode);
queue.addAll(children(currentNode));
}
}
public List<TreeNode> children(TreeNode parent) {
List<TreeNode> children = new ArrayList<TreeNode>();
for (TreeNode node : nodesList)
if (node.getParent() != null && node.getParent().equals(parent))
children.add(node);
return children;
}
private List<TreeNode> findNodes(String name) {
List<TreeNode> nodes = new ArrayList<TreeNode>();
for (TreeNode node : nodesList)
if (node.getName().equalsIgnoreCase(name))
nodes.add(node);
return nodes;
}
public void findCommonAncestors() throws IOException {
String line = reader.readLine();
int num = 0;
if (line != null)
num = Integer.parseInt(line);
for (int i = 0; i < num; i++) {
String[] splits = reader.readLine().split(\"\\\\s+\");
common(splits[0], splits[1]);
}
}
public void common(String name1, String name2) {
List<TreeNode> namesList1 = findNodes(name1);
List<TreeNode> namesList2 = findNodes(name2);
for (TreeNode node1 : namesList1)
for (TreeNode node2 : namesList2)
common(node1, node2);
}
private void common(TreeNode node1, TreeNode node2) {
System.out.println(\"Common ancestors of (\" + node1 + \") and (\" + node2 + \")\");
List<TreeNode> ancestors1 = ancestors(node1);
List<TreeNode> ancestors2 = ancestors(node2);
ancestors1.retainAll(ancestors2);
for (TreeNode node : ancestors1)
System.out.println(node);
}
private List<TreeNode> ancestors(TreeNode node1) {
List<TreeNode> ancestors = new ArrayList<TreeNode>();
while (node1 != null) {
ancestors.add(node1);
node1 = node1.getParent();
}
return ancestors;
}
public static void main(String[] args) {
try {
FamilyTree tree = new FamilyTree(\"data/family_tree.txt\");
System.out.println(\"Printing family tree in preorder\");
tree.preorder(tree.getRoot());
System.out.println(\"Printing family tree in postorder\");
tree.postorder(tree.getRoot());
System.out.println(\"Printing family tree in breadth first\");
tree.breadthfirst();
tree.findCommonAncestors();
} catch (IOException e) {
e.printStackTrace();
}
}
}
-------------------------------------------
TreeNode.java
-------------------------------------------
package chegg.tree;
public class TreeNode {
private String name;
private int year;
private TreeNode parent;
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getYear() {
return year;
}
public void setYear(int year) {
this.year = year;
}
public static TreeNode parseLine(String line) {
TreeNode node = new TreeNode();
String[] splits = line.split(\"\\\\s+\");
node.setName(splits[0]);
node.setYear(Integer.parseInt(splits[1]));
return node;
}
@Override
public boolean equals(Object obj) {
TreeNode node = (TreeNode) obj;
return this.name.equalsIgnoreCase(node.name) && this.year == node.year;
}
@Override
public String toString() {
return \"Name: \" + name + \" Year: \" + year;
}
}
