Question

help please!!!

In this assignment, we are to make the provided testBST.cpp, an integer BST into a generic template BST to host the following data types:

1. Integer,
2. String,
3. Frac, and
4. FeetInches.

#include "Frac.h"
#include "FeetInches.h"
....

    
template<class T> void test(vector<T> list);

int main() {
    vector<int> intPattern {3,8,1,4,6,25,15,16};
    test(intPattern);

    vector<string> strPattern {
        "how", "many", "apples", "did", "you", "buy"};
    test(strPattern);
}

// test Driver
template<class T>
void test(vector<T> list) {
    BST<T> *b = new BST<T>;
    
    cout << "Insertion sequence for new tree: \n   ";
    bool first = true;
    for(auto x:list) {
        b->insert(x);
        if(first) first = false;
        else cout << ", ";
        cout << x;
    }

    cout << "\n Listing Tree nodes in order: \n   ";
    b->display();            
    cout << "\n Show the Original Tree diagram:\n";
    b->printInOrder();
    cout << "\n Check whether last inserted Node, (" 
    << list[list.size()-1] << ") exists? " 
    << ( (b->find(list[list.size()-1]))?"YES":"NO" ) 
    << "\n Remove fist inserted Node\n   ";
    b->display();
    cout << "\n Show the final result in Diagram:\n";
    b->printInOrder();
}

Test Run Example:

The example shown here contains only Integer and String BST created by combining the starters.  

Your completed work needs to show BST test on all four types: Integer, String, Frac and FeetInches.

Running /home/ubuntu/workspace/somsc200/Week14/testTemplateBST.cpp Insertion sequence for new tree 3, 8, 1, 4, 6, 25, 15, 16 Listing Tree nodes in order: 13468 15 16 25 Show the Original Tree diagram: 25 1 +16 Check whether last inserted Node, (16) exists? YES Remove fist inserted Node 1346 815 16 25 Show the final result in Diagram: +-25 Insertion sequence for new tree how, many, apples, did, you, buy Listing Tree nodes in order: apples buy did how many you Show the Original Tree diagram: +--you +--many +--how I +-did I I +-buy --apples Check whether last inserted Node, (buy) exists? YES Remove fist inserted Node apples buy did how many you Show the final result in Diagram: +--you +--many +--how I +-did I I +-buy --apples Process exited with code: 0

Answer 1

#include <iostream>
#include <vector>
using namespace std;

//lets implement a basic templated tree
template <class T>
class Node {
public:
   T data;
   Node *left, *right, *parent;

   Node() {
       left = right = parent = NULL;
   };

   Node(T &value) {
       data = value;
   };

   ~Node() {
   };
  
   void operator= (const Node<T> &other) {
       data = other.data;
   };

   bool operator< (T &other) {
       return (data < other);
   };
};

//Our tree will contain the Node defined above
template <class T>
class Tree {
public:
   Tree() {
       root = NULL;
   };

   //We will define these all as virtuals for inherited trees (like a Huffman Tree and AVL Tree shown later)
   virtual void insert(T &value) {
       insertNode(root,NULL,value);
   };
   virtual Node<T>* find(T &value) {
       return searchNode(root,value);
   };
   virtual bool remove(T &value) {
       return deleteNode(root,value);
   };
   virtual bool operator< (Tree<T> &other) {
       return (root->data < other.first()->data);
   };
   void operator= (Tree<T> &other) {
       equalNode(root,other.first());
   };
   Node<T>*& first() {
       return root;
   };
   virtual void display()
   {
       displayTree(root);
       cout<<endl;
   }
   virtual void printInorder()
   {
       displayTree(root);
       cout<<endl;
   }

protected:
   //this will be our root node and private functions
   Node<T> *root;
   void displayTree(Node<T> * ptr )
   {
       if(ptr)
   {
       displayTree(ptr->left);
       cout<<ptr->data<<" ";
       displayTree(ptr->right);
   }
   }
   void equalNode(Node<T>*& node, Node<T>* value) {
       if(value != NULL) {
           node = new Node<T>();
           *node = *value;
           if(value->left != NULL)
               equalNode(node->left, value->left);
           if(value->right != NULL)
               equalNode(node->right, value->right);
       }
   }
  
   void insertNode(Node<T> *&node, Node<T> *parent, T &value) {
       if(node == NULL) {
           node = new Node<T>();
           *node = value;
           node->parent = parent;
       } else if(value < node->data) {
           insertNode(node->left,node,value);
       } else
           insertNode(node->right,node,value);
   };
   Node<T>* searchNode(Node<T> *node, T &value) {
       if(node == NULL)
           return NULL;
       else if(value == node->data)
           return node;
       else if(value < node->data)
           return searchNode(node->left,value);
       else
           return searchNode(node->right,value);
   };
   Node<T>* FindMax(Node<T>* root)
{
if(root==NULL)
return NULL;

while(root->right != NULL)
{
root = root->right;
}
return root;
}
   Node<T>* deleteNode(Node<T>* root,T data)
{
if(root==NULL) return root;
else if(data<root->data)
root->left = deleteNode(root->left, data);
else if (data> root->data)
root->right = deleteNode(root->right, data);
else
{
//No child
if(root->right == NULL && root->left == NULL)
{
delete root;
root = NULL;   
}
//One child
else if(root->right == NULL)
{
Node<T>* temp = root;
root= root->left;
delete temp;
}
else if(root->left == NULL)
{
Node<T>* temp = root;
root= root->right;
delete temp;
}
//two child
else
{
Node<T>* temp = FindMax(root->left);
root->data = temp->data;
root->left = deleteNode(root->left, temp->data);
}
}
return root;
};

};
template<class T> void test(vector<T> list);

int main() {
vector<int> intPattern {3,8,1,4,6,25,15,16};
test(intPattern);
vector<string> strPattern {
"how", "many", "apples", "did", "you", "buy"};
test(strPattern);
}

// test Driver
template<class T>
void test(vector<T> list) {
Tree<T> *b = new Tree<T>;
  
cout << "Insertion sequence for new tree: \n ";
bool first = true;
for(auto x:list) {
b->insert(x);
if(first) first = false;
else cout << ", ";
cout << x;
}
cout << "\n Listing Tree nodes in order: \n ";
b->display();
cout << "\n Show the Original Tree diagram:\n";
b->printInorder();
cout << "\n Check whether last inserted Node, ("
<< list[list.size()-1] << ") exists? "
<< ( (b->find(list[list.size()-1]))?"YES":"NO" )
<< "\n Remove fist inserted Node\n ";
b->display();
cout << "\n Show the final result in Diagram:\n";
b->printInorder();
}

/* output:

Insertion sequence for new tree: 
   3, 8, 1, 4, 6, 25, 15, 16
 Listing Tree nodes in order: 
   1 3 4 6 8 15 16 25 

 Show the Original Tree diagram:
1 3 4 6 8 15 16 25 

 Check whether last inserted Node, (16) exists? YES
 Remove fist inserted Node
   1 3 4 6 8 15 16 25 

 Show the final result in Diagram:
1 3 4 6 8 15 16 25 
Insertion sequence for new tree: 
   how, many, apples, did, you, buy
 Listing Tree nodes in order: 
   apples buy did how many you 

 Show the Original Tree diagram:
apples buy did how many you 

 Check whether last inserted Node, (buy) exists? YES
 Remove fist inserted Node
   apples buy did how many you 

 Show the final result in Diagram:
apples buy did how many you 

*/

//Please provide header files for footinch and fact