The goal of this assignment is to practice manipulating and

Added on - 23 Sep 2019

  • Dissertation


  • 2


  • 977


  • 107


  • 0


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 namesname1andname2, find all common ancestors for every pair of nodes(n1,n2)in = = name2, from the most recent common ancestor tothe least recent common ancestor. In the case thatn1is an ancestor ofn2, thenn1should also bereturned as an ancestor, and similarly for the case thatn2is an ancestor ofn1.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)
You’re reading a preview

To View Complete Document

Become a Desklib Library Member.
Subscribe to our plans

Unlock This Document