Ask a question from expert

Family Tree Traversal and Common Ancestors

2 Pages977 Words130 Views

Added on 2019-09-23

About This Document

This program handles a family tree structure and implements recursive preorder traversal, recursive postorder traversal, breadth-first traversal, and finding common ancestors for given names. The program reads from a file containing the family tree structure and the pairs of names for which common ancestors are desired. The output includes the three types of tree traversals and the list of common ancestors for each pair of names.

Family Tree Traversal and Common Ancestors

Added on 2019-09-23

BookmarkRelated Documents

Fred, 1900John, 1925Joan, 1927Mary, 1950John, 1951Fred, 1953Susan, 1949David, 1952Jason, 1972Heather, 1975Michael, 2005Adam, 1982Sarah, 1979Mark, 1977Amy, 1983Hailey, 2005Sydney, 2002Fred, 1980The 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 numberof children that any person in the family has, the family tree must be a general tree. The family treestructure keeps track of only one parent of each node (you can think of this as a “descendants view”, inwhich we are interested only in showing the descendants of a given ancestor). Each node stores 2 piecesof information: a name and a year of birth. Note that there are no restrictions on the number of familymembers with the same name, or on the number of family members born in the same year; however, forany 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 withno 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 tothe least recent common ancestor. In the case that n1 is an ancestor of n2, then n1 should also bereturned as an ancestor, and similarly for the case that n2 is an ancestor of n1. Hint: although it isnot 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”. Ifwe wish to find all common ancestors of “John” and “Fred”, then all of the following must be printed: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)

Family Tree Traversal and Common Ancestors_1

End of preview

Want to access all the pages? Upload your documents or become a member.