Description
Project Objectives
With this project you will construct a representation of a family tree from listings of its nodes in
preorder and postorder, then answer questions about relationships of pairs of individuals (nodes)
in the tree. The objectives of the project are to:
• implement a general tree data structure and the tree ADT operations; and
• gain experience with recursion by writing a recursive procedure to construct the tree from its
preorder and postorder traversals.
Input and Output
Typical input for the project will be:
< D, H, B, G, M, W, F, T, X, Z, C, R, P, Q, N. > G, M, W, F, B, X, Z, T, R, P, C, H, N, Q, D.
? D, H.
? W, T.
? N, F.
With this input, your program will construct a representation of the following tree:
F
D
H Q
C N
R P
T
X Z
B
G M W
CSC 316 – Project 2 2
and print the following output:
D is H’s parent.
W is T’s niece/nephew.
N is F’s 1th cousin 1 times removed.
The first line of the input is always the preorder traversal, beginning with < and ending with a period. The second line is the postorder traversal, beginning with >. The following lines contain
queries, beginning with ?.
Constructing a Tree from its Preorder and Postorder Traversals
Your task is to develop and implement a recursive procedure to construct the tree from its preorder
and postorder traversals. Write all your code in terms of the tree ADT operations For this project,
you may not use built-in Java classes, you need to implement your own classes. Choose
an appropriate implementation for this application from among those discussed in class. Your
program should still work correctly of another implementation is substituted for the one you chose.
Consider an unknown tree with preorder and postorder traversals:
H, B, G, M, W, F, T, X, Z, C, R, P
G, M, W, F, B, X, Z, T, R, P, C, H
We know that the root of the tree is H; it is first in preorder and last in postorder. We also know
that the tree has 12 nodes. So we need to figure out how to break the sequence
B, G, M, W, F, T, X, Z, C, R, P
G, M, W, F, B, X, Z, T, R, P, C
into subtrees. Clearly, B is the root of the leftmost subtree of H; it appears right after the root H in
preorder. Also, B will be the last node in its subtree’s postorder traversal. Therefore, we conclude
that the subtree rooted at B has five (5) nodes and is described by the traversals
B, G, M, W, F
G, M, W, F, B
The remaining subtree(s) are contained in the traversals
T, X, Z, C, R, P
X, Z, T, R, P, C
The next subtree is rooted at T, and is described by the traversals
T, X, Z
X, Z, T
CSC 316 – Project 2 3
The third and final subtree is described by the traversals
C, R, P
R, P, C
In effect, we have taken the problem of constructing a tree from its preorder and postorder traversal
and subdivided it into a number of similar problems on shorter traversals. When the traversals
have length one (1), the answer will be obvious (i.e., the subtree consists of only one node with no
children). Therefore, this approach is the basis of a recursive procedure to construct the tree.
Recursive buildTree() Method
You may assume that the input is correct, and that it corresponds to a real tree. Each character
represents a different node, so no character will be repeated in a single traversal. Since there are
only 256 different characters, this is a bound on the length of the input line.
Read the first two input lines into two global arrays, pretrav and posttrav. Write the following
recursive function:
function buildTree (int size, int prestart, int poststart): reference to Root node of subtree
size is the number of nodes in the subtree to be built
prestart is the place in pretrav where the preorder traversal of this subtree begins
poststart is the place in posttrav where the postorder traversal of this subtree begins
How to Determine Relationships
Include a mark field in each node. One method to determine the relationship of node A to node B
is:
• First, mark all ancestors of A, including A itself.
• Second, search B, B’s parent, B’s grandparent, etc., until the first marked node is found.
This node is the least common ancestor of A and B. The relationship of A to B is determined
from the lengths of the paths from A and B to the least common ancestor, according to the
following table:
CSC 316 – Project 2 4
A’s path length B’s path length Relation of A to B
0 0 A is B
0 1 A is B’s parent
0 2 A is B’s grandparent
0 3 A is B’s great-grandparent
0 k > 3 A is B’s (great)k−2
-grandparent
1 0 A is B’s child
2 0 A is B’s grandchild
k ≥ 3 0 A is B’s (great)k−2
-grandchild
1 1 A is B’s sibling
1 2 A is B’s aunt/uncle
1 k ≥ 2 A is B’s (great)k−2
-aunt/uncle
2 1 A is B’s niece/nephew
k ≥ 2 1 A is B’s (great)k−2
-niece/nephew
k ≥ 2 m ≥ 2 A is B’s (min(m, k) − 1)th cousin |k − m| times removed.
• Finally, do not forget to erase the marks of all nodes before you work on another query.
Level Order Traversal of the Family Tree
Once your program has answered the queries included in the input file, it will print the nodes of
the family three in level-order. As discussed in class, you will need to use a queue to implement
the level-order traversal, and you will have to visit nodes of the same depth in left-to-right order.
Deliverables: Source Code To Be Tested By The TA
You will implement a Java program to perform the operations described above. For your implementation, you may assume that the number of distinct nodes contained in the family tree will not
exceed 256, and similarly, the number of nodes in an input preorder or postorder sequence will not
exceed 256.
The program you submit will prompt the user for the name of the input and output files. Your
program will build the family tree from the preorder and postorder traversals, and then will print
the answers to the queriers following the first two lines of input. Finally, it will print the nodes of
the family tree in level-order.
Submission
Submit all your programs by the due date indicated on the course site.
CSC 316 – Project 2 5
Grading
buildTree 40 Points
Answers to queries 30 Points
Level-order traversal 30 Points
100 Points
Important reminder: Homework is an individual, not a group, project. Students may discuss
approaches to problems together, but each student should write up and fully understand his/her
own solution. Students may be asked to explain solutions orally if necessary.
