Description

Lab 7

Problem Description:
A family tree is a chart illustrating the family relationships in a conventional hierarchical tree structure with nodes and branches connecting to other nodes. Family trees are often presented with the oldest generations at the top and newer generations at the bottom. Family tree can have many relations. Given the family tree and a relation among two family members you need to write a program to print whether the relation is true or false, and nodes traversed in a pre-order.

Assumptions:
1. No name appears more than once in the family tree.
2. Each parent can have at most 2 children.
3. If a person has only one child then the child will be the left child of that node in the family tree.
4. The first string in the data set will be the root element.
Except for the root, nodes can only be added to the tree if the parent is already present in the tree.

Input:
1. The first line contains an integer n (0 < n < 100) followed by ‘n’ data sets.
2. Each data set consists of two strings, separated by space. The first string indicates the parent of the second string. Each string in the data set won’t exceed more than 25 characters.
3. An integer m (0 < m < 100) indicating number of relations for the family.
4. The following ‘m’ lines describe the relation in the family.

Output:
1. For each relation in the data set, your program should output T or F indicating whether the relation is true or false respectively. The output of each relation should be separated by a space, except the last one which will be terminated by a newline character.
2. Any relation with names not appearing in the family tree should result in F.
3. Print the preorder traversal of the tree on the next line with a single space separating each name.
4. The output should be terminated by a new line character without any space before it.

COMP 5481 Programming and problem solving Lab7

Sample Input Output:
Sample Input 1:
8
Motilal Jawahar Jawahar Indira
Motilal Kamala
Indira Sanjay
Sanjay Varun
Indira Rajiv
Rajiv Priyanka
Rajiv Rahul
6
Motilal child Jawahar
Varun descendant Indira
Priyanka sibling Varun
Sanjay child Indira
Sanjay ancestor Varun
Kamala ancestor Rahul

Sample Output 1:
F T F T T F
Motilal Jawahar Indira Sanjay Varun Rajiv Priyanka Rahul Kamala

Sample Input 2:
9
Prithviraj Raj
Shashi Sanjana
Prithviraj Shashi
Raj Randhir
Rishi Ranveer
Randhir Bebo
Randhir Lolo
Raj Rishi
Rishi Ridhima
7
Bebo descendant Shashi
Raj sibling Shashi
Prithviraj ancestor Ridhima
Lolo sibling Ridhima
Bebo ancestor Shashi
Prithviraj ancestor Raj
Rishi descendant Raj

Sample Output 2:
F T T F F T T
Prithviraj Raj Randhir Bebo Lolo Rishi Ridhima Shashi