Question: The task is to create a Menu using the templetes to store strings on the tree >>>>>> (The tree is used store strings names) 1.
The task is to create a Menu using the templetes to store strings on the tree >>>>>> (The tree is used store strings names) 1. The program should present the user with a menu as follows: Any other 1. Add a new name 2. Delete a name 3. List the contents in ascending order 4. Display the number of nodes in the tree 5. Display the number of leafs 6. Exit the system)<<<<<<
C++ Create a program that uses this class as follows (The tree is used store strings names) 1. The program should present the user with a menu as follows: Any other 1. Add a new name 2. Delete a name 3. List the contents in ascending order 4. Display the number of nodes in the tree 5. Display the number of leafs 6. Exit the system Please enter your choice 2. Create a function for each option on the menu to handle the request. 3. For choice # 1 (Add a new value), the function should prompt the user to enter a value (a string). If the value is already stored in the tree, you should display a message that indicates that. 4. For choice # 2 (Delete a value), the function should prompt the user to enter a value (a string). Display a message to indicate if the value is found and deleted or if it is not found. 5. Main() should call a function called menu() to display the menu and return users input. Main() should not handle any input or output other than reading and validating users input. 6. You need to submit the class files, main(), and the executable file. Using THAT HEADER FILE
#include
#include
#include
#include
#ifndef genBST_h
#define genBST_h
using namespace std;
struct node
{
int data;
struct node *next;
} *head;
template
class Stack : public stack {
public:
T pop() {
T tmp = pop();
Stack::pop();
return tmp;
}
};
template
class Queue : public queue {
public:
T dequeue() {
T tmp = queue::front();
queue::pop();
return tmp;
}
void enqueue(const T& el) {
push(el);
}
};
template class BST;
template
class BSTNode {
public:
BSTNode() {
left = right = 0;
}
BSTNode(const T& e, BSTNode *l = 0, BSTNode *r = 0) {
el = e; left = l; right = r;
}
T el;
BSTNode *left, *right;
};
template
class BST {
public:
BST() {
root = 0;
}
~BST() {
clear();
}
void clear() {
clear(root);
root = 0;
}
bool isEmpty() const {
return root == 0;
}
void preorder() {
preorder(root);
}
void inorder() {
inorder(root);
}
void postorder() {
postorder(root);
}
void insert(const T&);
void recursiveInsert(const T& el) {
recursiveInsert(root,el);
}
T* search(const T& el) const {
return search(root,el);
}
T* recursiveSearch(const T& el) const {
return recursiveSearch(root,el);
}
void deleteByCopying(BSTNode*&);
void findAndDeleteByCopying(const T&);
void deleteByMerging(BSTNode*&);
void findAndDeleteByMerging(const T&);
void iterativePreorder();
void iterativeInorder();
void iterativePostorder();
void breadthFirst();
void MorrisPreorder();
void MorrisInorder();
void MorrisPostorder();
void balance(T*,int,int);
void AddName(string name);
int nodecount(BSTNode* p);
int leavescount(BSTNode* p);
void Display();
protected:
BSTNode* root;
void clear(BSTNode*);
void recursiveInsert(BSTNode*&, const T&);
T* search(BSTNode*, const T&) const;
T* recursiveSearch(BSTNode*, const T&) const;
void preorder(BSTNode*);
void inorder(BSTNode*);
void postorder(BSTNode*);
//////////////////////////////////////
virtual void visit(BSTNode* p) {
cout << p->el << ' ';
}
};
template
void BST::clear(BSTNode *p) {
if (p != 0) {
clear(p->left);
clear(p->right);
delete p;
}
}
template
void BST::insert(const T& el) {
BSTNode *p = root, *prev = 0;
while (p != 0) { // find a place for inserting new node;
prev = p;
if (el < p->el)
p = p->left;
else p = p->right;
}
if (root == 0) // tree is empty;
root = new BSTNode(el);
else if (el < prev->el)
prev->left = new BSTNode(el);
else prev->right = new BSTNode(el);
}
template
void BST::recursiveInsert(BSTNode*& p, const T& el) {
if (p == 0)
p = new BSTNode(el);
else if (el < p->el)
recursiveInsert(p->left, el);
else recursiveInsert(p->right,el);
}
template
T* BST::search(BSTNode* p, const T& el) const {
while (p != 0)
if (el == p->el)
return &p->el;
else if (el < p->el)
p = p->left;
else p = p->right;
return 0;
}
template
T* BST::recursiveSearch(BSTNode* p, const T& el) const {
if (p != 0)
if (el == p->el)
return &p->el;
else if (el < p->el)
return recursiveSearch(p->left,el);
else return recursiveSearch(p->right,el);
else return 0;
}
template
void BST::inorder(BSTNode *p) {
if (p != 0) {
inorder(p->left);
visit(p);
inorder(p->right);
}
}
template
void BST::preorder(BSTNode *p) {
if (p != 0) {
visit(p);
preorder(p->left);
preorder(p->right);
}
}
template
void BST::postorder(BSTNode* p) {
if (p != 0) {
postorder(p->left);
postorder(p->right);
visit(p);
}
}
template
void BST::deleteByCopying(BSTNode*& node) {
BSTNode *previous, *tmp = node;
if (node->right == 0) // node has no right child;
node = node->left;
else if (node->left == 0) // node has no left child;
node = node->right;
else {
tmp = node->left; // node has both children;
previous = node; // 1.
while (tmp->right != 0) { // 2.
previous = tmp;
tmp = tmp->right;
}
node->el = tmp->el; // 3.
if (previous == node)
previous->left = tmp->left;
else previous->right = tmp->left; // 4.
}
delete tmp; // 5.
}
// findAndDeleteByCopying() searches the tree to locate the node containing
// el. If the node is located, the function DeleteByCopying() is called.
template
void BST::findAndDeleteByCopying(const T& el) {
BSTNode *p = root, *prev = 0;
while (p != 0 && !(p->el == el)) {
prev = p;
if (el < p->el)
p = p->left;
else p = p->right;
}
if (p != 0 && p->el == el)
if (p == root)
deleteByCopying(root);
else if (prev->left == p)
deleteByCopying(prev->left);
else deleteByCopying(prev->right);
else if (root != 0)
cout << "el " << el << " is not in the tree ";
else cout << "the tree is empty ";
}
template
void BST::deleteByMerging(BSTNode*& node) {
BSTNode *tmp = node;
if (node != 0) {
if (!node->right) // node has no right child: its left
node = node->left; // child (if any) is attached to its parent;
else if (node->left == 0) // node has no left child: its right
node = node->right; // child is attached to its parent;
else { // be ready for merging subtrees;
tmp = node->left; // 1. move left
while (tmp->right != 0)// 2. and then right as far as possible;
tmp = tmp->right;
tmp->right = // 3. establish the link between the
node->right; // the rightmost node of the left
// subtree and the right subtree;
tmp = node; // 4.
node = node->left; // 5.
}
delete tmp; // 6.
}
}
template
void BST::findAndDeleteByMerging(const T& el) {
BSTNode *node = root, *prev = 0;
while (node != 0) {
if (node->el == el)
break;
prev = node;
if (el < node->el)
node = node->left;
else node = node->right;
}
if (node != 0 && node->el == el)
if (node == root)
deleteByMerging(root);
else if (prev->left == node)
deleteByMerging(prev->left);
else deleteByMerging(prev->right);
else if (root != 0)
cout << "el " << el << " is not in the tree ";
else cout << "the tree is empty ";
}
template
void BST::iterativePreorder() {
stack*> travStack;
BSTNode *p = root;
if (p != 0) {
travStack.push(p);
while (!travStack.empty()) {
p = travStack.pop();
visit(p);
if (p->right != 0)
travStack.push(p->right);
if (p->left != 0) // left child pushed after right
travStack.push(p->left); // to be on the top of the stack;
}
}
}
template
void BST::iterativeInorder() {
stack*> travStack;
BSTNode *p = root;
while (p != 0) {
while (p != 0) { // stack the right child (if any)
if (p->right) // and the node itself when going
travStack.push(p->right); // to the left;
travStack.push(p);
p = p->left;
}
p = travStack.pop(); // pop a node with no left child
while (!travStack.empty() && p->right == 0) { // visit it and all nodes
visit(p); // with no right child;
p = travStack.pop();
}
visit(p); // visit also the first node with
if (!travStack.empty()) // a right child (if any);
p = travStack.pop();
else p = 0;
}
}
template
void BST::iterativePostorder() {
stack*> travStack;
BSTNode* p = root, *q = root;
while (p != 0) {
for ( ; p->left != 0; p = p->left)
travStack.push(p);
while (p->right == 0 || p->right == q) {
visit(p);
q = p;
if (travStack.empty())
return;
p = travStack.pop();
}
travStack.push(p);
p = p->right;
}
}
template
void BST::breadthFirst() {
Queue*> queue;
BSTNode *p = root;
if (p != 0) {
queue.enqueue(p);
while (!queue.empty()) {
p = queue.dequeue();
visit(p);
if (p->left != 0)
queue.enqueue(p->left);
if (p->right != 0)
queue.enqueue(p->right);
}
}
}
template
void BST::MorrisInorder() {
BSTNode *p = root, *tmp;
while (p != 0)
if (p->left == 0) {
visit(p);
p = p->right;
}
else {
tmp = p->left;
while (tmp->right != 0 &&// go to the rightmost node of
tmp->right != p) // the left subtree or
tmp = tmp->right; // to the temporary parent of p;
if (tmp->right == 0) { // if 'true' rightmost node was
tmp->right = p; // reached, make it a temporary
p = p->left; // parent of the current root,
}
else { // else a temporary parent has been
visit(p); // found; visit node p and then cut
tmp->right = 0; // the right pointer of the current
p = p->right; // parent, whereby it ceases to be
} // a parent;
}
}
template
void BST::MorrisPreorder() {
BSTNode *p = root, *tmp;
while (p != 0) {
if (p->left == 0) {
visit(p);
p = p->right;
}
else {
tmp = p->left;
while (tmp->right != 0 &&// go to the rightmost node of
tmp->right != p) // the left subtree or
tmp = tmp->right; // to the temporary parent of p;
if (tmp->right == 0) { // if 'true' rightmost node was
visit(p); // reached, visit the root and
tmp->right = p; // make the rightmost node a temporary
p = p->left; // parent of the current root,
}
else { // else a temporary parent has been
tmp->right = 0; // found; cut the right pointer of
p = p->right; // the current parent, whereby it ceases
} // to be a parent;
}
}
}
template
void BST::MorrisPostorder() {
BSTNode *p = new BSTNode(), *tmp, *q, *r, *s;
p->left = root;
while (p != 0)
if (p->left == 0)
p = p->right;
else {
tmp = p->left;
while (tmp->right != 0 &&// go to the rightmost node of
tmp->right != p) // the left subtree or
tmp = tmp->right; // to the temporary parent of p;
if (tmp->right == 0) { // if 'true' rightmost node was
tmp->right = p; // reached, make it a temporary
p = p->left; // parent of the current root,
}
else { // else a temporary parent has been found;
// process nodes between p->left (included) and p (excluded)
// extended to the right in modified tree in reverse order;
// the first loop descends this chain of nodes and reverses
// right pointers; the second loop goes back, visits nodes,
// and reverses right pointers again to restore the pointers
// to their original setting;
for (q = p->left, r = q->right, s = r->right;
r != p; q = r, r = s, s = s->right)
r->right = q;
for (s = q->right; q != p->left;
q->right = r, r = q, q = s, s = s->right)
visit(q);
visit(p->left); // visit node p->left and then cut
tmp->right = 0; // the right pointer of the current
p = p->right; // parent, whereby it ceases to be
} // a parent;
}
}
template
void BST::balance (T data[], int first, int last) {
if (first <= last) {
int middle = (first + last)/2;
insert(data[middle]);
balance(data,first,middle-1);
balance(data,middle+1,last);
}
}
////////////////////////////////////
template
int BST::nodecount(BSTNode* p) {
int count=1;
if (p ==NULL){
return 0;
}
else{
count+=nodecount(p->left);
count+=nodecount(p->right);
}
return count;
}
template
int BST::leavescount(BSTNode* p){
if (p==NULL){
return 0;
}
if(p->left==NULL && p->right==NULL){
return 1;
}
else{
return (leafcount(p->left)+ leafcount(p->right));
}
}
file.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help