Description
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.
Pre-order traversal is defined as follows:
1. Check if the current node is empty / null.
2. If not null display the data part of the
root (or current node).
3. Traverse the left subtree by recursively
calling the pre-order function.
4. Traverse the right subtree by recursively
calling the pre-order function.
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