Posted By

FuadMunzerinHossain on 01/14/15

Tagged

Versions (?)

Last Edited at 01/14/15 08:46am

Statistics

Viewed 893 times

Favorited by 0 user(s)

Related snippets

Binary Search Tree of Multi-member Objects

/ Published in: C++

Functions include: insert, find, remove, printall, printprobes, removeall, countactive, updatestatus. These functions take in various arguments. The functions and their commands are inserted by the user.

Highlighted TextExpand

FILE Main.cpp BEGINS

/*
 * Name: Fuad Munzerin Hossain
 * 1 Nov 2014
 */

#include "TreeNode.h"
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <iomanip>

using namespace std;

/*
 * Returns the pointer to the largest node in a tree given a pointer to its root.
 * This function is called when trying to remove a node which has 2 children.
 * A return by reference is necessary here because I want to change the value of the pointer in the function that calls this one.
 */
TreeNode* & returnLargestNodeInThisTree (TreeNode* & previousRoot, TreeNode* & root)
{
    if (root != NULL)
    {
        return(returnLargestNodeInThisTree(root,root->getRight())); //Recursive implementation to get to the largest node.
    }
    
    //Basis case. (Recursive implementation stops when the root becomes NULL)
    else if (root == NULL)
    {
        return previousRoot; //At this point, root is NOT the pointer to the largest node. (previousRoot is)
    }        
}

/*
 * This is a secondary function for deleting a node, which gets called by the main delete function when the largest node in a tree
 * is to be deleted. (In the case of a node having 2 children) Works similarly to the main function for removing a node, except 
 * that it does not print "Success" every time something is deleted successfully, and does not consider the case of the node
 * having two children, because this function is called only to delete the largest node in a tree. (The largest node in a tree 
 * cannot have 2 children)
 */
void deleteTreeNodeInTheBackground (string tempName, TreeNode* & previousRoot, TreeNode* & root)
{
    if (root != NULL)
    {
        //Find and delete the node in the left subtree.
        deleteTreeNodeInTheBackground(tempName,root,root->getLeft());
        //Node to be deleted is found if the following evaluates to true, proceed to appropriately delete.
        if (root->getEntry()->getName() == tempName)
        {
            //Condition to check if this is a leaf node.
            if ((root->getLeft() == NULL) && (root->getRight() == NULL))
            {
                delete root;
                root = NULL;
                return;
            }
            
            //Condition to check if this node only has 1 subtree.
            else if(((root->getLeft() != NULL) && (root->getRight() == NULL)) || ((root->getRight() != NULL) && (root->getLeft() == NULL)))
            {
                //Condition to check whether that 1 subtree is a left subtree
                if ((root->getLeft() != NULL) && (root->getRight() == NULL))
                {
                    TreeNode* toBeDeleted = root;
                    root = root->getLeft();
                    delete toBeDeleted;
                    return;
                }
                
                //Condition to check whether that 1 subtree is a right subtree
                else if ((root->getRight() != NULL) && (root->getLeft() == NULL))
                {
                    TreeNode* toBeDeleted = root;
                    root = root->getRight();
                    delete toBeDeleted;
                    return;
                }
            }
            //Note: no need to check here if node has 2 subtrees, because the largest node in any tree cannot have 2 children.
        }
        //Find and delete the node in the right subtree.
        deleteTreeNodeInTheBackground(tempName,root,root->getRight());
    }
    return;
}

/*
 * This is the main function for removing a node from the tree.
 */
void deleteTreeNode (string tempName, TreeNode* & previousRoot, TreeNode* & root)
{
    if (root != NULL)
    {
        //Find and delete the node in the left subtree
        deleteTreeNode(tempName,root,root->getLeft());
        //Node to be deleted is found if the following evaluates to true, proceed to appropriately delete.
        if (root->getEntry()->getName() == tempName)
        {
            //Condition to check if this is a leaf node.
            if ((root->getLeft() == NULL) && (root->getRight() == NULL))
            {
                delete root;
                root = NULL;
                cout<<"Success\n";
                return;
            }
            //Condition to check if this node only has 1 subtree.
            else if(((root->getLeft() != NULL) && (root->getRight() == NULL)) || ((root->getRight() != NULL) && (root->getLeft() == NULL)))
            {
                if ((root->getLeft() != NULL) && (root->getRight() == NULL))
                {
                    TreeNode* toBeDeleted = root;
                    root = root->getLeft();
                    delete toBeDeleted;
                    cout<<"Success\n";
                    return;
                }
                
                else if ((root->getRight() != NULL) && (root->getLeft() == NULL))
                {
                    TreeNode* toBeDeleted = root;
                    root = root->getRight();
                    delete toBeDeleted;
                    cout<<"Success\n";
                    return;
                }
            }
            //Condition to check if this node has 2 children
            else if ((root->getLeft() != NULL) && (root->getRight() != NULL))
            {
                //Make of copy of the fields of the largest node in the left subtree of the node that is to be deleted.
                string pivotName = ((returnLargestNodeInThisTree(root->getLeft(),root->getLeft()))->getEntry()->getName());
                unsigned int pivotIPaddress = ((returnLargestNodeInThisTree(root->getLeft(),root->getLeft()))->getEntry()->getIPaddress());
                bool pivotActive = ((returnLargestNodeInThisTree(root->getLeft(),root->getLeft()))->getEntry()->getActive());
                
                //Delete the node which was copied from.
                deleteTreeNodeInTheBackground(pivotName,root->getLeft(),root->getLeft());
                
                //Create new TreeNode object based on the field which were copied.
                TreeNode* rootNew = new TreeNode();
                rootNew->getEntry()->setName(pivotName);
                rootNew->getEntry()->setIPaddress(pivotIPaddress);
                rootNew->getEntry()->setActive(pivotActive);
                //Make the new TreeNode point to the same left and right trees which the "to be deleted" node is pointing to.
                rootNew->setLeft(root->getLeft()); 
                rootNew->setRight(root->getRight());
                //Make this pointer to point to the node to be deleted, so it can be deleted.
                TreeNode* rootPrime = root;
                //Make root point to the new node (The copied node)
                root = rootNew;
                //Deletes what root was originally pointing to. (The node that was intended to be deleted)
                delete rootPrime;
                cout<<"Success\n";
                return;                
            }
        }
        //Find and delete the node in the right subtree
        deleteTreeNode(tempName,root,root->getRight());
    }
    return;
}

//Finds a node given a name, and sets its active status.
void updateActive (string tempName, bool active, TreeNode* root)
{
    if (root != NULL)
    {
        //Find the node in the left subtree
        updateActive(tempName,active,root->getLeft());
        //Node is found. Set its active status.
        if (root->getEntry()->getName() == tempName)
        {
            root->getEntry()->setActive(active);
            return;
        }
        //Find the node in the right subtree
        updateActive(tempName,active,root->getRight());
    }
    return;
}

/*
 * This function is called for the removeall command and at the end of main() to delete the entire tree to avoid memory leaks.
 */
void masterDelete (TreeNode* & root)
{
    if (root == NULL)
    {
        return; //Tree is empty.
    }
    
    else if (root != NULL)
    {
        masterDelete(root->getLeft()); //Delete left subtree.
        masterDelete(root->getRight()); //Delete right subtree.
        delete root; 
        root = NULL; //To indicate an empty tree.
        return;
    }
}

//Examines all nodes in the tree, and increases a counter every time a node has its active status as true.
void countActiveTreeNodes(int & activeCount,TreeNode* root)
{
    if (root != NULL)
    {
        countActiveTreeNodes(activeCount,root->getLeft()); //Count in the left subtree
        if (root->getEntry()->getActive() == true) //increase counter if the node that is examined has its active status as true.
        {
            activeCount = activeCount + 1; 
        }
        countActiveTreeNodes(activeCount,root->getRight()); //Count in the right subtree
    }
    return;
}

/* 
 * Finds a node given a name, and increases a counter every time any node is examined.
 * This function is invoked only after checking that the node with such a name already exists.
 * The counter is passed by reference because the increments in each recursive call must be combined.
 */
void printProbes (string tempName, int & probeCount, TreeNode* root)
{
    if (root == NULL)
    {
        return; //No node examined, so just return.
    }
    
    //Node with given name is found, increase the count then print the total count, then return.
    if (root->getEntry()->getName()==tempName)
    {
        probeCount = probeCount + 1;
        cout<<probeCount<<"\n";
        return;
    }
    
    //Node with given name is not found, but counter needs to be increased. Now check in the appropriate subtree.
    else if ((root->getEntry()->getName())<tempName)
    {
        probeCount = probeCount + 1;
        printProbes(tempName,probeCount,root->getRight());
    }
    
    else
    {
        probeCount = probeCount + 1;
        printProbes(tempName,probeCount,root->getLeft());
    }
}

//Finds a node given a name, already checked for existence using another function.
void printTreeNode (string tempName, TreeNode* root)
{
    if (root != NULL)
    {
        printTreeNode(tempName,root->getLeft()); //Find node in the left subtree
        if (root->getEntry()->getName() == tempName) //Node is found. Print the fields.
        {
            cout<<root->getEntry()->getName()<<" : "<<root->getEntry()->getIPaddress()<<" : ";
            if (root->getEntry()->getActive() == true)
            {
                cout<<"active\n";
            }
            else
            {
                cout<<"inactive\n";
            }
        }
        printTreeNode(tempName,root->getRight()); //Find node in the right subtree
    }
    return;
}

//Function for printing every node in the tree, starting with the smallest (left most) node.
void printTree (TreeNode* root)
{
    if (root != NULL)
    {
        printTree(root->getLeft()); //Print the left subtree.
        //Print the fields of the current node.
        cout<<root->getEntry()->getName()<<" : "<<root->getEntry()->getIPaddress()<<" : ";
        if (root->getEntry()->getActive() == true)
        {
            cout<<"active\n";
        }
        else
        {
            cout<<"inactive\n";
        }
        printTree(root->getRight()); //Print the right subtree.
    }
    return;
}

//Goes through the entire tree to check if a node if a given name exists. Returns true if yes.
bool doesTreeNodeExist (string tempName, TreeNode* root)
{
    if (root == NULL) //Empty tree, return false.
    {
        return false; 
    }
    
    if (root->getEntry()->getName()==tempName) //Found the node. Return true.
    {
        return true;
    }
    
    else if ((root->getEntry()->getName())<tempName) //Find the node in the appropriate subtree.
    {
        return doesTreeNodeExist(tempName,root->getRight());
    }
    
    else
    {
        return doesTreeNodeExist(tempName,root->getLeft());
    }
}

//Function for inserting a new node in a tree. This function gets called only if a node with this name does not exist.
void masterInsert (string tempName, unsigned int tempIPaddress, bool active, TreeNode* & root)
{
    if (root == NULL) //If tree is empty.
    {
        root = new TreeNode(); //Create the new node object, then set the fields.
        root->getEntry()->setName(tempName); 
        root->getEntry()->setIPaddress(tempIPaddress);
        root->getEntry()->setActive(active);
        cout<<"Success\n";
        return;
    }
    
    else if ((root->getEntry()->getName())<tempName) //Insert the node into the appropriate subtree.
    {
        masterInsert(tempName,tempIPaddress,active,root->getRight());
        return;
    }
    
    else
    {
        masterInsert(tempName,tempIPaddress,active,root->getLeft());
        return;
    }
}

//The main function
int main ()
{
    //Make the most important and most used pointer in the entire program. (The top node in the tree)
    TreeNode* root = NULL;
    
    string command; //String to hold the command argument entered by the user.
    string tempName=""; //String to hold the name argument entered by the user.
    unsigned int tempIPaddress; //Variable to hold the IP Address entered by the user.
    string tempActive=""; //Helper variable to hold the active status entered by the user.
    string line; //String for the string stream.
    cout<<"> ";
    getline(cin,line); //Gets a single line from the user.
    
    //starts the loop and continues looping until user enters the EOF
    while(!cin.eof())
    {   
        command="";
        tempName="";
        tempActive="";
        
        stringstream myStream(line);
        myStream>>command; //Main Stream

//This layer of if and else statements covers the commands
        if (command == "insert")
        {     
            myStream>>tempName;
            myStream>>tempIPaddress;           
            myStream>>tempActive;          
            
            bool active; //Boolean to pass into a function to set the active status of a node.
            
            if (tempActive == "active")
            {
                active = true;
            }
            
            else if (tempActive == "inactive")
            {
                active = false;
            }
            
            //Checks if node with given name exists already.
            if (doesTreeNodeExist(tempName,root) == true)
            {
                cout<<"Error: entry already exists\n";
            }
            
            //All clear. Insert the node.
            else
            {
                masterInsert(tempName,tempIPaddress,active,root);
            }
                    
        }
             
        else if (command == "find")
        {
            myStream>>tempName;
            
            //Checks if a node with the given name exists.
            if(doesTreeNodeExist(tempName,root) == false)
            {
                cout<<"Error: entry does not exist\n";
            }
            
            //If the node with the given name exists, print the details of the node.
            else
            {
                printTreeNode(tempName,root);
            }
        }
        
        else if (command == "remove")
        {           
            myStream>>tempName;
            
            //Checks if a node with the given name exists.
            if(doesTreeNodeExist(tempName,root) == false)
            {
                cout<<"Error: entry does not exist\n";
            }
            
            //If the node with the given name exists, delete the node.
            else
            {
                deleteTreeNode(tempName,root,root);
            }
        }
        
        else if (command == "printall")
        {      
            //Print the entire tree.
            printTree(root); 
        }
        
        else if (command == "printprobes")
        {                
            myStream>>tempName;
            
            int probeCount = 0;
            
            //Checks if a node with the given name exists.
            if(doesTreeNodeExist(tempName,root) == false)
            {
                cout<<"Error: entry does not exist\n";
            }
            
            //If the node with the given name exists, count the number of nodes examined to get to that node from the top of the tree.
            else
            {
                printProbes(tempName,probeCount,root);
            }
            
        }
        
        else if (command == "removeall")
        {
            //Delete the entire tree. Root is then set to NULL in this function.
            masterDelete(root);
            cout<<"Success\n";
        }
        
        else if (command == "countactive")
        {
            int activeCount = 0; //Count starts at 0. 
            //Examine every node and increment the counter if the node has its active status set as true.
            countActiveTreeNodes(activeCount,root);
            cout<<activeCount<<"\n";
        }
        
        else if (command == "updatestatus")
        {
            myStream>>tempName;
            myStream>>tempActive;
            
            bool active; //Boolean to pass into the updateActive function.
            
            if (tempActive == "active")
            {
                active = true;
            }
            
            else if (tempActive == "inactive")
            {
                active = false;
            }
            
            //Checks if a node with the given name exists.
            if(doesTreeNodeExist(tempName,root) == false)
            {
                cout<<"Error: entry does not exist\n";
            }
            
            //Go find the node and update its status.
            else
            {
                updateActive(tempName,active,root);
                cout<<"Success\n";
            }
        }
                        
        //so that user sees the prompt for next input
        cout<<"> ";
        getline(cin,line);
    }
    
    //Deletes every node in the tree to avoid any memory leaks
    masterDelete(root);
    return 0;
}

FILE Main.cpp ENDS

----------------------------------------------------------------------------------------
FILE DBentry.cpp BEGIN

#include "DBentry.h"

// the default constructor
DBentry::DBentry()
{
    ;
}
DBentry::DBentry (string _name, unsigned int _IPaddress, bool _active)
{
    name = _name;
    IPaddress = _IPaddress;
    active = _active;
}

// the destructor
DBentry::~DBentry()
{
    ;
}

// sets the domain name, which we will use as a key.
void DBentry::setName(string _name)
{
    name = _name;
    return;
}

// sets the IPaddress data.
void DBentry::setIPaddress(unsigned int _IPaddress)
{
    IPaddress = _IPaddress;
    return;
}

// sets whether or not this entry is active.
void DBentry::setActive (bool _active)
{
    active = _active;
    return;
}

// returns the name.
string DBentry::getName() const
{
    return name;
}

// returns the IPaddress data.
unsigned int DBentry::getIPaddress() const
{
    return IPaddress;
}

// returns whether or not this entry is active.
bool DBentry::getActive() const
{
    return active;
}

File DBentry.cpp ENDS
----------------------------------------------------------------------------------------
FILE DBentry.h BEGINS

#ifndef _DBENTRY_H
#define _DBENTRY_H

#include <string>
using namespace std;

class DBentry {
private:
	string name;
	unsigned int IPaddress;
        bool active;

public:
	// the default constructor
	DBentry();
        DBentry (string _name, unsigned int _IPaddress, bool _active);

// the destructor
 	~DBentry();

// sets the domain name, which we will use as a key.
	void setName(string _name);

// sets the IPaddress data.
	void setIPaddress(unsigned int _IPaddress);
    
        // sets whether or not this entry is active.
        void setActive (bool _active);

// returns the name.
	string getName() const;

// returns the IPaddress data.
	unsigned int getIPaddress() const;

// returns whether or not this entry is active.
        bool getActive() const;
};

#endif

FILE DBentry.h ENDS
----------------------------------------------------------------------------------------
FILE TreeNode.cpp BEGINS

#include "TreeNode.h"
#include <iostream>
#include <string>

// Default constructor
TreeNode::TreeNode()
{
    entryPtr = new DBentry();
    left = NULL;
    right = NULL;
}

// A useful constructor
TreeNode::TreeNode(DBentry* _entryPtr)
{
    entryPtr = _entryPtr;
}

// The destructor
TreeNode::~TreeNode()
{
    delete entryPtr;
}

// Sets the left child of the TreeNode.
void TreeNode::setLeft(TreeNode* newLeft)
{
    left = newLeft;
    return;
}

// Sets the right child of the TreeNode.
void TreeNode::setRight(TreeNode* newRight)
{
    right = newRight;
    return;
}

/*
 * Gets the left child of the TreeNode. 
 * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
 */
TreeNode* & TreeNode::getLeft()
{
    return left;
}

/*
 * Gets the right child of the TreeNode. 
 * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
 */
TreeNode* & TreeNode::getRight()
{
    return right;
}

/*
 * Returns the entryPtr of the TreeNode. 
 * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
 */ 
DBentry* & TreeNode::getEntry()
{
    return entryPtr;
}

FILE TreeNode.cpp ENDS
----------------------------------------------------------------------------------------
FILE TreeNode.h BEGINS

#ifndef _TREENODE_H
#define _TREENODE_H

#include "DBentry.h"

class TreeNode {
private:
    DBentry* entryPtr;
    TreeNode* left;
    TreeNode* right;

public:
    // default constructor
    TreeNode();
    
    // A useful constructor
    TreeNode(DBentry* _entryPtr);

// the destructor
    ~TreeNode();

// Sets the left child of the TreeNode.
    void setLeft(TreeNode* newLeft);

// Sets the right child of the TreeNode
    void setRight(TreeNode* newRight);

/*
     * Gets the left child of the TreeNode. 
     * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
     */
    TreeNode* & getLeft();

/*
     * Gets the right child of the TreeNode. 
     * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
     */
    TreeNode* & getRight();

/*
     * Returns the entryPtr of the TreeNode. 
     * Return type must be passed by reference as this pointer will be altered in some functions that call this function.
     */ 
    DBentry* & getEntry();
};

#endif

FILE TreeNode.h ENDS
------------------------------------------------------------------------------------------

Report this snippet Tweet