Instructions:
1. Task to alter familyTree.cpp to implement the find and numberOfCousins functions of the class FamilyTree.
2. Code will be evaluated both on its ability to function correctly within the cousins application and on its ability to pass the unit tests provided.
– In the test report, tests 0…1 check the unit tests and tests 2…21 test the cousins application.
Input:
Input will be taken from standard input (cin) if no command line parameters are given, or from a file named in the first command line parameter if such a parameter is supplied. For example, the program could be invoked as
./cousins test0.in
or as
./cousins < test0.in
The input will begin with a single integer, k, where k is the identifier of the particular node for which we wish to count cousins.
This will be followed by the tree, written in a classic format for rendering trees called “s-expressions” The s-expression for a tree node is written within parentheses, with the node identifier immediately following the left parenthesis, followed by the s-expressions for all of its children, then the closing right parenthesis. If a node has no children, however, the parentheses can be omitted, leaving only the identifier. For example, a tree consisting only of a single root node with identifier 21 could be written as:
(21)
or
21
But a tree with a root node containing 21 and having two children 5 and 7 would be
(21 (5) (7))
or
(21 5 7)
The tree in the diagram above, could be written as
(1
(3 8 9)
(4 15)
(5 30 31 32)
)
Blank spaces and line breaks can be inserted as desired to improve the readability.
Every tree will have at least one node, and the node of interest, k, will always be found somewhere within the tree.
The Descriptions:
One of the common places where tree structures occur is in “family trees” that show the relationships within an extended family, children, parents, grandparents, great-grandparents, etc. Consider a family tree in which each node contains a number that serves a unique identifier. That identifier could, in a larger application, serve as an index into a genealogical database holding detailed information about the family members. Each node in the tree will represent a single person or a parental couple. The parent-child relationships in the tree match those in the actual family.
In the tree shown to the right (attached), for ex:, person/couple 1 are grandparents to the people represented by all of the leaf nodes. Person/couple 5 are parents to people 30, 31, & 32. 3, 4, and 5 are siblings, brothers and/or sisters sharing the same parents. Similarly, 30, 31, & 32 are siblings.
A person’s cousins are the children of the siblings of that person’s parents. Alternately, we could say that two nodes are considered to be cousins if they have different parents but the same grandparents.
For example, person 8’s cousins are 15, 30, 31, & 32 (but not 9). 15’s cousins are 8, 9, 30, 31, & 32.
Write a program that, given a tree and the identifier of a person in that tree, prints the number of cousins that person has.
Output:
Output is a single line containing a single integer, indicating the number cousins of node k.
Example:
Given the input
15
(1
(3 8 9)
(4 15)
(5 30 31 32)
)
the output would be
5
Given the input
3
(1
(3 8 9)
(4 15)
(5 30 31 32)
)
the output would be 0
