Tree specifications

Node representation

You may use either a C struct type or a C$++$ class to define the employee node. The key member

of a tree node representation is the children node array. For practicing the pointer use in this

assignment:

$$ You must use a double pointer for specifying the children node array.

o e$.$g$.,$ EmployeeNode $**$ children;

$2|$ P a g e

o Do NOT use any collection data structure from the STL $($standard template

library$),$ such as vector, list, etc.

$$ Violating the above requirement would result in a zero point for a$1$ assignment.

$$ You may add other data members to your node structure as you see needed, such as a

member for employee ID as a string $($use any available string type from libraries for

what you like$),$ node level, etc.

$$ Programming tips:

o Sample code for instantiating a double pointer array,

$$ children $=$ new EmployeeNode$*[$numOfChildren$]$; $//$ C$++$

$$ children $=($struct EmployeeNode$**)$

malloc$($numOfChildren$*$sizeof$($struct EmployeeNode$*))$; $//$ C

o As a best practice, after instantiation, always explicitly initialize all child

pointers to NULL or nullptr. And in C and C$++,$ it is always a best practice to

explicitly initialize all variables before using them.

$$ The $$run in one environment but not in another$$ problem is often

caused by non or improper initializations.

Tree operations

Implement the following tree operations with the specified logic $($Return type and function

name can vary, but pay attention to the requirements below$)$:

$$ First, using iterative or recursive implementation is your choice.

$$ bool addEmployees$($const char $*$employeeIDPath$)$;

o You are required to use const char$*$ for the employee ID path argument, you

need to use C string manipulation to parse and extract information from the

employeeIDPath.

$$ You must not use std::string for parsing this argument in the function.

$$ Violating this requirement would result in a $50\%$ deduction of your a$1$

grade.

$$ You may use std::string in other contexts of your program, e$.$g$.,$ at the

end of the Appendix $($see below$),$ std::string is used for reading in lines

from a text file.

o Note this signature is for a member function in a C$++$ node class; if you are

using C$,$ you would need to add an argument for specifying which node to start

with, e$.$g$.$:

$$ bool addEmployees$($struct EmployeeNode $*$curNode$,$ const char $*$

employeeIDPath$)$;

$$ Similarly, this applies to other functions below.

o Logic:

$$ Starting from the current node, insert employee nodes identified along

the employee ID Path to the tree, stop if the employeeIDPath cannot

be parsed further due to bad format or reaching the end of the path

or reaching beyond the total number of levels specified from the file

for building the org chart $($see below the orgchart.txt file$).$

$$ Inserting an employee node at a child location of a node is to create a

new employee node and assign the newly created node to the location.

$3|$ P a g e

$$ Each employee node should also have an employee ID $($as a string$)$ set

to it$,$ see the sample invocation below on what the employee ID should

be set.

o The employee ID path argument should contain a series of single digit integers

separated by an underscore, e$.$g$.,0\_2\_3,$ with each number representing the

child index at the appropriate level starting from the current node, and they

are zero based.

$$ Each index must be within the max number of children allowed for the

level minus $1,$ as indices are zero based. And assume each index is

within a single digit range $[09]$

$$ The max allowed number of children for each level will be from

the file specified in the first command line argument $($see

below orgchart.txt in compilation and execution section$)$

$$ If an index is outside the allowed range or is not a digit, stop the adding

process and return.

$$ Note the added nodes so far will stay.

o Sample invocation with employee ID path as $0\_2\_3$:

$$ The digits in the path are zero based indices of the child array for the

levels.

$$ Starting from current node, add or insert an employee $($if it is NOT

added yet$)$ as $0$th child of the current node and set its employee ID

string to e$\_0,$ then add an employee as the $2$nd child under employee

e$\_0$ and set its employee ID to e$\_0\_2,$ then add an employee as the $3$rd

direct report under employee e$\_0\_2$ and set its employee ID to

e$\_0\_2\_3$

$$ Note: the head $($root$)$ node of the org chart should always have an

employee ID as e

$$ Always check if the child index is within the child index range for the

level before creating and adding the child employee node.

$$ See above.

$$ Always check if the number levels that is traversed has exceeded the

total number of levels from the org chart file.

$$ When called on the root $/$ head node, employeeIDPath should contain

the full employee ID path to be added.

$$ EmployeeNode$*$ findEmployee$($const char $*$employeeIDPath$)$;

o Logic:

$$ find and return the employee node in the org chart based on an

employee ID path $($e$.$g$.,0\_2\_3)$

$$ See above for the elabora