Data Structures Project 6

Objectives
1. [50 Points] Create all the methods and fields to implement the parent array implementation of the
multiway data structure (nodes with more than one child). You are required to demonstrate the
working of the following methods for each of the methods by invoking them from a main program.
a. empty constructor
b. non-empty constructor (sets the initial size of the arrays)
c. destructor
d. copy constructor
e. overloaded equal to operator
f. ostream operator – pre order traversal
g. size method
h. height method
i. getChildren
j. preorder traversal method
k. level order traversal method (Bonus: 25 Points) – Print the nodes in level 1, followed by level 2,
followed by level 3 and so on (use the STL queue for this purpose).
2. [20 Points] Read the redirected input and create all the data structures.
3. [20 Points] Demonstrate the working of all the methods.
4. [10 Points] Document your project thoroughly as the examples in the textbook. This includes but not
limited to header comments for all classes/methods, explanatory comments for each section of code,
meaningful variable and method names, and consistent indentation.
Project Description
The input to your project will be as follows: The first line of input will be number of nodes in the tree. Consider
the following input. There are 22 nodes. For node numbered 20 the first number on the line is the number of
children in this case it is 4 numbered 5, 8, 9, and 19.
22
20 4 5 8 9 19
5 2 1 6
1 2 0 2
0 0
2 0
6 0
8 1 7
7 0
9 4 10 11 12 13
10 2 3 4
11 0
12 1 14
14 0
13 0
19 1 21
21 4 15 16 17 18
15 0
16 0
17 0
18 0Class Structures
You are required to implement the following class structure along with the implementation of the methods
associated with each of them.
template <class DT
class ParentMultiTree {
protected:
DT* ParentArray;
int* ChildPosition;
int numNodes;
public:
//All the required methods
};
Constraints
1. In this project, the only header you will use is #include <iostream.
2. None of the projects is a group project.