QuestionQuestion

Transcribed TextTranscribed Text

Advanced Data Structures The goal of this assignment is to practice manipulating and traversing trees. 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. Note that when printing the information for a given node, both name and year of birth must be printed. Example: In this example, there are three family members with the name “Fred” and two with the name “John”. If we wish to find all common ancestors of “John” and “Fred”, then all of the following must be printed: Fred, 1900 John, 1925 Joan, 1927 Mary, 1950 John, 1951 Fred, 1953 Susan, 1949 David, 1952 Jason, 1972 Heather, 1975 Amy, 1983 Mark, 1977 Sarah, 1979 Adam, 1982 Fred, 1980 Sydney, 2002 Hailey, 2005 Michael, 2005 Common ancestors of (John, 1925) and (Fred, 1900): (Fred, 1900) Common ancestors of (John, 1925) and (Fred, 1953): (John, 1925), (Fred, 1900) Common ancestors of (John, 1925) and (Fred, 1980): (Fred, 1900) Common ancestors of (John, 1951) and (Fred, 1900): (Fred, 1900) Common ancestors of (John, 1951) and (Fred, 1953): (John, 1925), (Fred, 1900) Common ancestors of (John, 1951) and (Fred, 1980): (Fred, 1900) 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 case must be handled and 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 PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class FamilyTree {

    private Name root;
    //height of the root = 0
    //so when it is empty, the height = -1
    private int heightOfTree = -1;
    private int countFirst = 0;
    private int countSecond = 0;

    public FamilyTree() {
       super();
    }

    //make the root of the tree
    //Fred,1900
    public void root(Name root) {
       this.root = root;
    }
    //get root

    public Name getRoot() {
       return this.root;
    }

    //find the height of tree
    //traverse from the root to find the height of the tree
    public boolean heightOfTree(Name currentName, int check) {
       int test = 0;
       //if the current height is more than what we find before
       //update height of the tree to the bigger one(current height)
       /*
    * before it runs currentName = -1
    * and then it's going to the root which heightOfTree = 0
    * then currentName>heightTree, update currentName.height = 0
    * recursive this to find the biggest number which is the height of the tree...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$30.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats