The goal of this assignment is to practice manipulating and
Added on -2019-09-23
| 2 pages
| 977 words
| 324 views
Trusted by 2+ million users,
1000+ happy students everyday
Showing pages 1 to 1 of 2 pages
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 traversalRecursive postorder traversalBreadth-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)
Found this document preview useful?
You are reading a preview
Upload your documents to download
or
Become a Desklib member to get accesss
Paid Plans
Free Plan
Single Unlock
Monthly Plan
Yearly Plan