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.