For this assignment you are to modify your C++ BST class and add the following f

ID: 3863843 • Letter: F

Question

For this assignment you are to modify your C++ BST class and add the following functionality

- Remove

- Tree Height

- FindMin

- FindMax

Your program will take in a command file called “cmd.txt” which will instruct your program on what operations to run

File Format

Commands

- 1 insert

- 2 in order

- 3 post order

- 4 pre order

- 5 search

- 6 delete

- 7 findHeight

- 8 findMin

- 9 findMax

Example File

1 20

1 30

1 10

1 25

1 29

1 23

1 56

1 89

1 4

1 33

6 20

6 89

Expectations

You should not use any already implemented code such as a library for your linked list

Your code should be well formatted with proper spacing and proper naming

Your code should have well named variables. No a’s b’s or c’s as names unless it is for something like a loop counter

Your code must have the same output formatting you see below

#include <iostream>
using namespace std;

// A generic tree node class
class Node {
    int key;
    Node* left;
    Node* right;
    Node* parent;
public:
    Node() { key=-1; left=NULL; right=NULL; parent = NULL;};
    void setKey(int aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    void setParent(Node* aParent) { parent = aParent; };
    int Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
    Node* Parent() { return parent; };
};

// Binary Search Tree class
class Tree {
    Node* root;
public:
    Tree();
    ~Tree();
    Node* Root() { return root; };
    void addNode(int key);
    Node* findNode(int key, Node* parent);
    void walk(Node* node);
    void deleteNode(int key);
    Node* min(Node* node);
    Node* max(Node* node);
    Node* successor(int key, Node* parent);
    Node* predecessor(int key, Node* parent);
private:
    void addNode(int key, Node* leaf);
    void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
root = NULL;
}

// Destructor
Tree::~Tree() {
freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
        freeNode(leaf->Left());
        freeNode(leaf->Right());
        delete leaf;
    }
}

// Add a node [O(height of tree) on average]
void Tree::addNode(int key)
{
    // No elements. Add the root
    if ( root == NULL ) {
        cout << "add root node ... " << key << endl;
        Node* n = new Node();
        n->setKey(key);
    root = n;
    }
    else {
    cout << "add other node ... " << key << endl;
    addNode(key, root);
    }
}

// Add a node (private)
void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() )
    {
        if ( leaf->Left() != NULL )
            addNode(key, leaf->Left());
        else {
            Node* n = new Node();
            n->setKey(key);
            n->setParent(leaf);
            leaf->setLeft(n);
        }
    }
    else
    {
        if ( leaf->Right() != NULL )
            addNode(key, leaf->Right());
        else {
            Node* n = new Node();
            n->setKey(key);
            n->setParent(leaf);
            leaf->setRight(n);
        }
    }
}

// Find a node [O(height of tree) on average]
Node* Tree::findNode(int key, Node* node)
{
    if ( node == NULL )
        return NULL;
    else if ( node->Key() == key )
        return node;
    else if ( key <= node->Key() )
        findNode(key, node->Left());
    else if ( key > node->Key() )
        findNode(key, node->Right());
    else
        return NULL;
}

// Print the tree
void Tree::walk(Node* node)
{
    if ( node )
    {
        cout << node->Key() << " ";
        walk(node->Left());
        walk(node->Right());
    }
}

// Find the node with min key
// Traverse the left sub-tree recursively
// till left sub-tree is empty to get min
Node* Tree::min(Node* node)
{
if ( node == NULL )
return NULL;

    if ( node->Left() )
        min(node->Left());
    else
        return node;
}

// Find the node with max key
// Traverse the right sub-tree recursively
// till right sub-tree is empty to get max
Node* Tree::max(Node* node)
{
if ( node == NULL )
return NULL;

    if ( node->Right() )
        max(node->Right());
    else
        return node;
}

// Find successor to a node
// Find the node, get the node with max value
// for the right sub-tree to get the successor
Node* Tree::successor(int key, Node *node)
{
    Node* thisKey = findNode(key, node);
    if ( thisKey )
        return max(thisKey->Right());
}

// Find predecessor to a node
// Find the node, get the node with max value
// for the left sub-tree to get the predecessor
Node* Tree::predecessor(int key, Node *node)
{
    Node* thisKey = findNode(key, node);
    if ( thisKey )
        return max(thisKey->Left());
}

// Delete a node
// (1) If leaf just delete
// (2) If only one child delete this node and replace
// with the child
// (3) If 2 children. Find the predecessor (or successor).
// Delete the predecessor (or successor). Replace the
// node to be deleted with the predecessor (or successor).
void Tree::deleteNode(int key)
{
// Find the node.
Node* thisKey = findNode(key, root);

    // (1)
    if ( thisKey->Left() == NULL && thisKey->Right() == NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(NULL);
        else
            thisKey->Parent()->setLeft(NULL);

delete thisKey;
}

    // (2)
    if ( thisKey->Left() == NULL && thisKey->Right() != NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(thisKey->Right());
        else
            thisKey->Parent()->setLeft(thisKey->Right());

        delete thisKey;
    }
    if ( thisKey->Left() != NULL && thisKey->Right() == NULL )
    {
        if ( thisKey->Key() > thisKey->Parent()->Key() )
            thisKey->Parent()->setRight(thisKey->Left());
        else
            thisKey->Parent()->setLeft(thisKey->Left());

delete thisKey;
}

    // (3)
    if ( thisKey->Left() != NULL && thisKey->Right() != NULL )
    {
        Node* sub = predecessor(thisKey->Key(), thisKey);
        if ( sub == NULL )
            sub = successor(thisKey->Key(), thisKey);

        if ( sub->Parent()->Key() <= sub->Key() )
            sub->Parent()->setRight(sub->Right());
        else
            sub->Parent()->setLeft(sub->Left());

        thisKey->setKey(sub->Key());
        delete sub;
    }
}

// Test main program
int main() {
Tree* tree = new Tree();

    // Add nodes
    tree->addNode(300);
    tree->addNode(100);
    tree->addNode(200);
    tree->addNode(400);
    tree->addNode(500);

    // Traverse the tree
    tree->walk(tree->Root());
    cout << endl;

    // Find nodes
    if ( tree->findNode(500, tree->Root()) )
        cout << "Node 500 found" << endl;
    else
        cout << "Node 500 not found" << endl;

    if ( tree->findNode(600, tree->Root()) )
        cout << "Node 600 found" << endl;
    else
        cout << "Node 600 not found" << endl;

    // Min & Max
    cout << "Min=" << tree->min(tree->Root())->Key() << endl;
    cout << "Max=" << tree->max(tree->Root())->Key() << endl;

    // Successor and Predecessor
    cout << "Successor to 300=" <<
            tree->successor(300, tree->Root())->Key() << endl;
    cout << "Predecessor to 300=" <<
            tree->predecessor(300, tree->Root())->Key() << endl;

// Delete a node
tree->deleteNode(300);

    // Traverse the tree
    tree->walk(tree->Root());
    cout << endl;

delete tree;
return 0;
}

Explanation / Answer

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

// Binary Search Tree class
class Tree {
    Node* root;
public:
    Tree();
    ~Tree();
    Node* Root() { return root; };
    void addNode(int key);
    Node* findNode(int key, Node* parent);
    void walk(Node* node);
    void walkPostOrder(Node* node);
    void walkInOrder(Node* node);
    void deleteNode(int key);
    Node* min(Node* node);
    Node* max(Node* node);
    Node* successor(int key, Node* parent);
    Node* predecessor(int key, Node* parent);
    int Height(Node* node);
private:
    void addNode(int key, Node* leaf);
    void freeNode(Node* leaf);
};

// Constructor
Tree::Tree() {
root = NULL;
}

// Destructor
Tree::~Tree() {
freeNode(root);
}

// Free the node
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
        freeNode(leaf->Left());
        freeNode(leaf->Right());
        delete leaf;
    }
}

// Print the tree
void Tree::walk(Node* node)
{
    if ( node )
    {
        cout << node->Key() << " ";
        walk(node->Left());
        walk(node->Right());
    }
}

// Print the tree InOrder
void Tree::walkInOrder(Node* node)
{
    if ( node )
    {
        walk(node->Left());
        cout << node->Key() << " ";
        walk(node->Right());
    }
}
// Print the tree PostOrder
void Tree::walkPostOrder(Node* node)
{
    if ( node )
    {
        walk(node->Left());
        walk(node->Right());
        cout << node->Key() << " ";
    }
}
// Find the node with min key
// Traverse the left sub-tree recursively
// till left sub-tree is empty to get min
Node* Tree::min(Node* node)
{
    if ( node == NULL )
        return NULL;

    if ( node->Left() )
        min(node->Left());
    else
        return node;
}

// Find the node with max key
// Traverse the right sub-tree recursively
// till right sub-tree is empty to get max
Node* Tree::max(Node* node)
{
if ( node == NULL )
return NULL;

    if ( node->Right() )
        max(node->Right());
    else
        return node;
}

delete thisKey;
}

        if ( sub->Parent()->Key() <= sub->Key() )
            sub->Parent()->setRight(sub->Right());
        else
            sub->Parent()->setLeft(sub->Left());

        thisKey->setKey(sub->Key());
        delete sub;
    }

}

int Tree::Height(Node* node)
    {
       if (node==NULL)
           return 0;
       else
       {
           /* compute the Height of each subtree */
           int lDepth = Height(node->Left());
           int rDepth = Height(node->Right());

           /* use the larger one */
           if (lDepth > rDepth)
               return(lDepth+1);
           else return(rDepth+1);
       }
    }
// Test main program
int main() {
    Tree* tree = new Tree();

    // Traverse the tree

    cout << endl;

    // Min & Max
    //cout << "Min=" << tree->min(tree->Root())->Key() << endl;
    //cout << "Max=" << tree->max(tree->Root())->Key() << endl;
    // Successor and Predecessor
    //cout << "Successor to 300=" <<
    //        tree->successor(300, tree->Root())->Key() << endl;
    //cout << "Predecessor to 300=" <<
    //        tree->predecessor(300, tree->Root())->Key() << endl;

    // Traverse the tree
    tree->walk(tree->Root());
    cout << endl;

      string line;
      ifstream myfile ("input.txt");
      int data;
      if (myfile.is_open())
      {
        while ( myfile>>data)
        {
         // cout << data << ' ';
          switch(data){
            case 1:
                myfile>>data;
                cout << "Inserting data "<<data<<" ";
                tree->addNode(data);
                break;
            case 2:
                cout << "In Order Traverse: ";
                tree->walkInOrder(tree->Root());
                cout << " ";
                break;
            case 3:
                cout << "Post Order Traverse: ";
                tree->walkPostOrder(tree->Root());
                cout << " ";
                break;
            case 4:
                cout << "Pre Order Traverse : ";
                tree->walk(tree->Root());
                cout << " ";
                break;
            case 5:
                myfile>>data;
                cout << "Searching Node "<<data<<" ";
                if ( tree->findNode(data, tree->Root()) )
                    cout << "Node "<<data<<" found" << endl;
                else
                    cout << "Node "<<data<<" not found" << endl;
                break;
            case 6:
                myfile>>data;
                cout << "Deleteing Node "<<data<<" ";
                if ( tree->findNode(data, tree->Root()) ){
                    tree->deleteNode(data);
                    cout << "Node Deleted "<<data<< endl;
                }
                else
                    cout << "Can not Delete Node "<<data<<" not found" << endl;
                break;
            case 7:
                cout << "FindHeight ";
                cout << "Height :"<<tree->Height(tree->Root())<<" ";
                break;
            case 8:
                cout << "FindMin ";
                cout << "Min :"<<tree->min(tree->Root())->Key()<<" ";
                break;
            case 9:
                cout << "FindMax ";
                cout << "Max :"<<tree->max(tree->Root())->Key()<<" ";
                break;
            default :
                cout << "Wrong input ";
          }
        }
        myfile.close();
      }

      else cout << "Unable to open file ";

    tree->walk(tree->Root());
    delete tree;
    return 0;
}

Navigate

For this assignment you are to modify your C++ BST class and add the following f

For this assignment you are to write a 3-4 page (not including title page, refer

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

For this assignment you are to modify your C++ BST class and add the following f

Question

Explanation / Answer

Related Questions

Navigate