Description
VE 280 Lab 8
Task 1: Implementation of N-ary Tree
1.1 Terminology
1.1.1 Descendants
A descendant of a node X is a child of X or a descendant of a child of X.
For instance, the descendants of 2 in the previous figure are 4, 5, 6, 8, and 9.
1.1.2 Subtree
A subtree of the tree T is a tree consists of a node in T and all of this node’s descendants.
For instance, if we name the tree above as T, then the tree rooted in 2 is a subtree of T.
Also, the the tree rooted in 6 is a subtree of T.
1.1.3 Leaf
A node with no child is called a leaf node. For example, node 4, 5, 8, 9 and 7 are leaf nodes.
1.1.4 Path
A path is a sequence of nodes such that a next node in the sequence is a child of the previous one.
For example 2->6->9 is a path and the length of this path is 2.
1.1.5 Height
The height of a node is the length of a longest path from the node to a leaf.
For example, height(1) = 3, height(9) = 0
1.2 Implementation
A node of a tree can be represented by the following class and a tree ADT can be represented by the node corresponding to its root.
class Node {
// OVERVIEW: a node in the n-Ary tree, can also represent a n-ary tree rooted at ‘this’ protected:
int value; // the integer value of this
int child_num; // the number of child of this
int n; // n for this n-Ary tree
Node *parent; // parent node of this, for root node, parent = NULL
Node **children;
// children is an array of pointer to Node. Therefore, children is a pointer of pointer
int height; // height of this node
void addChild(Node *child);
// REQUIRES: n of the child node is the same with n of this
// EFFECTS: add the node child to the children array
// throw an exception tooManyChildren when child_num exceed n bool equal(Node* sub);
// EFFECTS: return true if the tree rooted at ‘this’ and the tree rooted at ‘sub’
// have the same shape and value.
public:
Node(int _value, int _n = 2);
// EFFECTS: create a root node with value and n
~Node();
// EFFECTS: destroy the whole tree rooted at sub
void addChild(int _value);
// EFFECTS: create a child node with value and add it to the children array
// throw an exception tooManyChildren when child_num exceed n
void traverse(vector<int>& traverseValue);
// EFFECTS: insert the value of the nodes into traverseValue using a preorder traversal,
// A pre-order traversal insert the value of the node
// and then traverse its child nodes
// according to the sequence in children array.
// For example, the value of traverseValue of the tree above is
