Description
Project Description
Consider a binary tree with N nodes where each the nodes are given unique numbers in the range 0..N-1.
Such a binary tree can be stored in in an array P of size N, wherein P[k] will indicate the parent of node
numbered k in the binary tree. See the binary tree and the corresponding parent array below.
5
2 6
3
0 4
1
8
9
7
Parent Array P
0 1 2 3 4 5 6 7 8 9
3 6 5 2 3 -1 5 6 7 8
Since 5 does not have a parent with placed a -1.
To recognize if a node is left (0) or right child (1) we have,
0 1 2 3 4 5 6 7 8 9
0 0 0 0 1 -1 1 1 0 1
Examples: Node 0 is a left child of node 3 hence a 0.
Node 6 is a right child of node 5 hence a 1.
The input to your project will be as follows: The first line of input will be number of nodes in the binary tree. If a
node does not have a left or right child we will place a -1 otherwise, we will put the number of the left or right
child. For the above tree, the input is given below.
10
5 2 6
2 3 -1
3 0 4
6 1 7
1 -1 -1
0 -1 -1
8 -1 9
9 -1 -1
4 -1 -1
7 8 -1
Class Structures
You are required to implement the following class structure along with the implementation of the methods
associated with each of them.
template
class ParentBinaryTree {
protected:
DT* ParentArray;
int numNodes;
public:
//All the required methods
};
Constraints
1. In this project, the only header you will use is #include .
2. None of the projects is a group project. Consulting with other members of this class on programming
projects is strictly not allowed and plagiarism charges will be imposed on students who do not follow
this.
