Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Code tree, explain code, explain functions #include #include #include #include #include using namespace std; template class Node { protected: T *data; public: Node() { data
Code tree, explain code, explain functions
#include
#include
#include
#include
#include
using namespace std;
template
class Node
{
protected:
T *data;
public:
Node()
{
data = new T;
}
Node(T d)
{
data = new T;
(*data) = d;
}
Node &operator=(T d)
{
(*data) = d;
return *this;
}
friend ostream &operator<<(ostream &out, Node n)
{
out << *(n.data);
return out;
}
friend ostream &operator<<(ostream &out, Node *n)
{
out << *(n->data);
return out;
}
void setData(T d)
{
*data = d;
}
T &getData() const
{
return *data;
}
};
template
class ListNode : public Node
{
private:
ListNode *prev, *next;
public:
ListNode() : Node()
{
prev = NULL;
next = NULL;
}
ListNode(T d) : Node(d)
{
prev = NULL;
next = NULL;
}
ListNode(ListNode *p, ListNode *n) : Node()
{
prev = p;
next = n;
}
ListNode(T d, ListNode *p, ListNode *n) : Node(d)
{
prev = p;
next = n;
}
ListNode *getNext() const
{
return next;
}
ListNode *getPrev() const
{
return prev;
}
void setNext(ListNode *n)
{
next = n;
}
void setPrev(ListNode *p)
{
prev = p;
}
ListNode &operator=(T d)
{
this -> setData(d);
return *this;
}
};
template
class LinkList
{
public:
LinkList()
{
head = NULL;
tail = NULL;
}
void addFromHead(T d)
{
ListNode *node = new ListNode(d);
if (head != NULL)
{
head -> setPrev(node);
}
node -> setNext(head);
head = node;
if (tail == NULL) tail = node;
}
void addFromTail(T d)
{
ListNode *node = new ListNode(d);
if (tail != NULL)
{
tail -> setNext(node);
}
node -> setPrev(tail);
tail = node;
if (head == NULL) head = node;
}
void addAfter(ListNode *at, T d)
{
if (!exist(at)) return;
ListNode *node = new ListNode(d);
if (at->getNext() != NULL) at -> getNext() -> setPrev(node);
node -> setNext(at->getNext());
at -> setNext(node);
node -> setPrev(at);
if (node -> getNext() == NULL) tail = node;
}
ListNode *removeFromHead()
{
ListNode *n = head;
if (head != NULL)
{
head = head -> getNext();
if (head != NULL)
{
head->setPrev(NULL);
}
else
{
tail = NULL;
}
n -> setNext(NULL);
}
return n;
}
ListNode *removeFromTail()
{
ListNode *n = tail;
if (tail != NULL)
{
tail = tail -> getPrev();
if (tail != NULL)
{
tail->setNext(NULL);
}
else
{
head = NULL;
}
n -> setPrev(NULL);
}
return n;
}
ListNode *remove(ListNode *n)
{
if (!exist(n)) return NULL;
if (n == head) return removeFromHead();
if (n == tail) return removeFromTail();
n -> getPrev() -> setNext(n -> getNext());
n -> getNext() -> setPrev(n -> getPrev());
n -> setNext(NULL);
n -> setPrev(NULL);
return n;
}
ListNode *exist(T d)
{
ListNode *j = head;
while (j != NULL)
{
if (j -> getData() == d) return j;
j = j -> getNext();
}
return NULL;
}
bool exist(ListNode *n)
{
ListNode *j = head;
while (j != NULL)
{
if (j == n) return true;
j = j->getNext();
}
return false;
}
ListNode &operator[](int i)
{
ListNode *j = head;
for (int k = 0; k < i && j != NULL; k++)
{
j = j -> getNext();
}
if (j == NULL) throw std::invalid_argument("index does not exist.");
return *j;
}
void print() const
{
ListNode *j;
j = head;
while (j != NULL)
{
cout << (*j) << " ";
j = j -> getNext();
}
cout << endl;
}
protected:
ListNode *head, *tail;
};
/*
Please finish the TreeNode class, TreeNode class represent a node in a general tree.
A general tree is different from binary tree, every node in binary tree have at most two child node, but a node in general tree may have more than two child node.
*/
template
class TreeNode : public Node
{
public:
TreeNode() : Node()
{
child = new LinkList *>();
}
TreeNode(T d) : Node(d)
{
child = new LinkList *>();
this->setData(d);
}
/*
Add a child to this node.
*/
void addChild(TreeNode *n)
{
child->addFromTail(n); // uses LinkedList method to add many children
}
/*
Add a child to this node.
*/
void addChild(T d)
{
child->addFromTail(new TreeNode(d)); // same as above diferent ata type
}
/*
Return the nth child of the node.
*/
TreeNode *operator[](int n)
{
//return child->operator[](n).getData();
return (*child)[n].getData(); // gets the nth data at that nth child
}
private:
LinkList *> *child;
};
/*
Please finish the Tree class. Tree class represent a general tree, that means node on this tree may have more than two child node.
*/
template
class Tree
{
public:
Tree()
{
root = NULL;
}
/*
return the nth node on this tree with level order.
*/
TreeNode *operator[](int n)
{
if (root == NULL) return NULL;
//queue of tree nodes
queue*> q;
q.push(root);
//pointing at the treenode on the front
TreeNode *cur = q.front();
q.pop();
//starts at 0
for (int i = 0; i < n; i++)
{
for(int j=0;1;j++)
{
try
{
//pushes every child node in order
//(of the actual node)
TreeNode *t = (*cur)[j];
q.push(t);
}
catch(invalid_argument e){break;}
}
//moves to the next one on the front (first child?)
cur = q.front();
//pops the first one
q.pop();
}
//Ok, goes after all until it gets to the n node
return cur;
}
/*
return the number of nodes on this tree.
*/
int count()
{
if (root == NULL) return 0;
queue*> q;
q.push(root);
int counter = 0;
//q.pop()
while (!q.empty())
{
//adds the size of the queue to the count
int size = q.size();
counter += size;
//Goes for every node adding the childs to the queue
for (int i = 0; i < size; i++)
{
TreeNode *cur = q.front();
q.pop();
for(int j=0;1;j++)
{
try
{
TreeNode *t = (*cur)[j];
q.push(t);
}
catch(invalid_argument e){break;}
}
}
}
return counter;
}
/*
print all the node on this tree with level order.
*/
void levelOrder()
{
if (root == NULL) return;
cout << "LevelOrder: ";
queue*> q;
q.push(root);
while (!q.empty())
{
int size = q.size();
for (int i = 0; i < size; i++)
{
TreeNode *cur = q.front();
q.pop();
cout << cur << " ";
for(int j=0;1;j++)
{
try
{
TreeNode *t = (*cur)[j];
q.push(t);
}
catch(invalid_argument e){break;} // if there is no data to be pushed - end of children
}
}
}
cout << endl;
}
/*
print all the node on this tree with preorder.
*/
void preorder()
{
cout << "PreOrder: ";
preorder(root);
cout<
}
/*
print all the node on this tree with postorder.
*/
void postorder()
{
cout << "PostOrder: ";
postorder(root);
cout<
}
/*
set the root of this tree.
*/
void setRoot(T d)
{
root = new TreeNode(d);
}
TreeNode *getRoot()
{
return root;
}
private:
TreeNode *root;
void preorder(TreeNode *r)
{
if (r == NULL) return;
//visits node
cout << r << " ";
//then visits childs from left to right
for (int i = 0;1; i++)
{
try
{
preorder((*r)[i]);
}
catch(invalid_argument e){break;} //
}
}
void postorder(TreeNode *r)
{
if (r == NULL) return;
int j = 0;
//visits child from left to right
for (int i = 0;1; i++)
{
try
{
postorder((*r)[j]);
}
catch(invalid_argument e){break;}
j++;
}
//then visits node
cout << r << " ";
}
};
int main()
{
Tree *tree = new Tree();
srand(0);
int j, k, i;
for(j = 0;j < 20;j ++)
{
if(tree->count() == 0)
tree->setRoot(rand() % 100);
else
{
k = rand() % tree->count();
(*tree)[k]->addChild(rand() % 100);
}
}
tree->levelOrder();
tree->preorder();
tree->postorder();
}
Online Judge Footer
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Web Database Development Step By Step
Authors: Jim Buyens
1st Edition
0735609667, 978-0735609662
