CODEWITHSUNDEEP
c++tree
jmramoutar1
jmramoutar1

Reputation: 23

Searching binary tree of objects for a single class member

So I'm working on a program that will use a binary tree template class I've created to hold a set of EmployeeInfo objects which is another class I've created. The EmployeeInfo class has two data members, one to hold the employee's ID number and one to hold the employees name. In the main program, I create the binary tree of 5 employeeinfo objects and I'm now trying to figure out how to search the binary tree for JUST an employee ID number and if the number is there, I must print the number along with the name associated with the number onto the screen. This is where I'm running into trouble. My search function returns a bool, so I'm unsure on how to get it to display the name associated with the ID number if it is found.

Here is my Binary Tree template class:

// Specification file for the BinaryTree Class
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
using namespace std;

// BinaryTree template
template <class T>
class BinaryTree
{
private:
    struct TreeNode
    {
        T value;
        TreeNode *left;
        TreeNode *right;
    };

    TreeNode *root;

    // Private functions
    void insert(TreeNode *&, TreeNode *&);
    void destroySubTree(TreeNode *);
    void deleteNode(T, TreeNode *&);
    void makeDeletion(TreeNode *&);
    void displayInOrder(TreeNode *) const;
    void displayPreOrder(TreeNode *) const;
    void displayPostOrder(TreeNode *) const;
    int findHeight(TreeNode *root);
    int count1(TreeNode *);
    int countLeft(TreeNode *);

public:
    // Constructor
    BinaryTree()
    {
        root = nullptr;
    }

    // Destructor
    ~BinaryTree()
    {
        destroySubTree(root);
    }

    // Binary Tree Operations
    void insertNode(T);
    bool searchNode(T);
    void remove(T);
    int displayCount()
    {
        return count1(root);
    }
    int displayLeftCount()
    {
        return countLeft(root);
    }
    int displayHeight()
    {
        return findHeight(root);
    }


    void displayInOrder() const
    {
        displayInOrder(root);
    }

    void displayPreOrder() const
    {
        displayPreOrder(root);
    }

    void displayPostOrder() const
    {
        displayPreOrder(root);
    }

};

template <class T>
void BinaryTree<T>::insert(TreeNode *&root, TreeNode *&newNode)
{
    if (root == nullptr)
        root = newNode;
    else if (newNode->value < root->value)
        insert(root->left, newNode);
    else
        insert(root->right, newNode);
}

template <class T>
void BinaryTree<T>::insertNode(T item)
{
    TreeNode *newNode = nullptr;

    newNode = new TreeNode;
    newNode->value = item;
    newNode->left = newNode->right = nullptr;

    insert(root, newNode);
}

template <class T>
void BinaryTree<T>::destroySubTree(TreeNode *nodePtr)
{
    if (nodePtr)
    {
        if (nodePtr->left)
            destroySubTree(nodePtr->left);
        if (nodePtr->right)
            destroySubTree(nodePtr->right);
        delete nodePtr;
    }
}

template <class T>
bool BinaryTree<T>::searchNode(T item)
{
    TreeNode *nodePtr = root;

    while (nodePtr)
    {
        if (nodePtr->value == item)
            return true;
        else if (item < nodePtr->value)
            nodePtr = nodePtr->left;
        else
            nodePtr = nodePtr->right;
    }
    return false;
}

template <class T>
void BinaryTree<T>::remove(T item)
{
    deleteNode(item, root);
}

template <class T>
void BinaryTree<T>::deleteNode(T item, TreeNode *&nodePtr)
{
    if (item < nodePtr->value)
        deleteNode(item, nodePtr->left);
    else if (item > nodePtr->value)
        deleteNode(item, nodePtr->right);
    else
        makeDeleteion(nodePtr);
}

template <class T>
void BinaryTree<T>::makeDeletion(TreeNode *&nodePtr)
{
    TreeNode *tempNodePtr = nullptr;

    if (nodePtr == nullptr)
        cout << "Cannot delete empty node." << endl;
    else if (nodePtr->right == nullptr)
    {
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->left;
        delete tempNodePtr;
    }
    else if (nodePtr->left == nullptr)
    {
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->right;
        delete tempNodePtr;
    }
    else
    {
        tempNodePtr = nodePtr->right;
        while (tempNodePtr->left)
            tempNodePtr = tempNodePtr->left;
        tempNodePtr->left = nodePtr->left;
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->right;
        delete tempNodePtr;
    }
}

template <class T>
void BinaryTree<T>::displayInOrder(TreeNode *nodePtr) const
{
    if (nodePtr)
    {
        displayInOrder(nodePtr->left);
        cout << nodePtr->value << endl;
        displayInOrder(nodePtr->right);
    }
}

template <class T>
void BinaryTree<T>::displayPreOrder(TreeNode *nodePtr) const
{
    if (nodePtr)
    {
        cout << nodePtr->value << endl;
        displayPreOrder(nodePtr->left);
        displayPreOrder(nodePtr->right);
    }
}

template <class T>
void BinaryTree<T>::displayPostOrder(TreeNode *nodePtr) const
{
    if (nodePtr)
    {
        displayPostOrder(nodePtr->left);
        displayPostOrder(nodePtr->right);
        cout << nodePtr->value << endl;
    }
}

template <class T>
int BinaryTree<T>::count1(TreeNode *root)
{
    int count = 1;
    if (root->left != nullptr)
    {
        count += count1(root->left);
    }
    if (root->right != nullptr)
    {
        count += count1(root->right);
    }
    return count;
}

template <class T>
int BinaryTree<T>::countLeft(TreeNode *root)
{
    int count = 1;
    if (root->left != nullptr)
        count += countLeft(root->left);
    return count;
}

template <class T>
int BinaryTree<T>::findHeight(TreeNode *nodePtr)
{
    if (nodePtr == NULL)
    {
        return 0;
    }

    int left = findHeight(nodePtr->left);
    int right = findHeight(nodePtr->right);

    if (left > right)
        return 1 + left;
    else
        return 1 + right;

}

#endif

Here is my EmployeeInfo class header and cpp:

/* Specification file for the EmployeeInfo class which will hold two private data members, one which is an integer called empID and another which will
be a string called empName.*/
#include "BinaryTree.h"
#include <iostream>
#include <string>
#ifndef EMPLOYEEINFO_H
#define EMPLOYEEINFO_H

class EmployeeInfo
{
private:
    int empID;
    string empName;
public:
    // Default Constructor
    EmployeeInfo();

    // Constructor
    EmployeeInfo(int, string);

    // Mutator functions
    void setEmpID(int);
    void setEmpName(string);

    // Accessor functions
    int getEmpID() const;
    string getEmpName() const;

    // Overloaded operators
    bool operator < (const EmployeeInfo &right);
    bool operator > (const EmployeeInfo &right);
    bool operator == (const EmployeeInfo &right);
};
#endif

// Declaration file for the EmployeeInfo class
#include "BinaryTree.h"
#include "EmployeeInfo.h"
#include <iostream>
#include <string>

// Default Constructor
EmployeeInfo::EmployeeInfo()
{
    empID = 0;
    empName = "";
}

// Constructor
EmployeeInfo::EmployeeInfo(int i, string n)
{
    empID = i;
    empName = n;
}

// Mutators
void EmployeeInfo::setEmpID(int i)
{
    empID = i;
}

void EmployeeInfo::setEmpName(string n)
{
    empName = n;
}

// Accessors
int EmployeeInfo::getEmpID() const
{
    return empID;
}

string EmployeeInfo::getEmpName() const
{
    return empName;
}

// Overloaded operators
bool EmployeeInfo::operator > (const EmployeeInfo &right)
{
    bool status;

    if (empID > right.empID)
        status = true;
    else
        status = false;

    return status;
}

bool EmployeeInfo::operator < (const EmployeeInfo &right)
{
    bool status;

    if (empID < right.empID)
        status = true;
    else
        status = false;

    return status;
}

bool EmployeeInfo::operator == (const EmployeeInfo &right)
{
    bool status;

    if (empID == right.empID)
        status = true;
    else
        status = false;

    return status;
}

And here is the main program:

#include "BinaryTree.h"
#include "EmployeeInfo.h"
#include <iostream>
#include <string>
using namespace std;

const int NUM_EMPS = 5;

int main()
{
    BinaryTree<EmployeeInfo> staff;
    int ID;
    string name;

    // Fill up the tree
    for (int count = 0; count < NUM_EMPS; count++)
    {
        cout << "Enter the ID number for Employee " << count + 1 << ": ";
        cin >> ID;
        cout << "Name: ";
        cin >> name;
        EmployeeInfo newEmp(ID, name);
        staff.insertNode(newEmp);
    }

    // NEED HELP WITH THIS PART!!!
    do
    {
        int search;
        cout << "Enter the ID number you'd like to search for: ";
        cin >> search;


    system("pause");
    return 0;
}

I'm able to fill up the tree fine with the objects, but when it comes to searching the tree I'm lost! Any help will be appreciated.

Upvotes: 2

Views: 738

Answers (1)

amallard
amallard

Reputation: 1229

Display the info using the binary tree class.

Edit your searchNode function in the Binary Tree class

template <class T>
bool BinaryTree<T>::searchNode(T item) {
    TreeNode *nodePtr = root;

    while (nodePtr) {
        if (nodePtr->value == item) {
            cout << nodePtr->value << endl;
            return true;
        }
        else if (item < nodePtr->value)
            nodePtr = nodePtr->left;
        else
            nodePtr = nodePtr->right;
        }
    return false;
}

Then create an EmployeeInfo object, assign it the ID to search for, and search your tree:

int search;
cout << "Enter the ID number you'd like to search for: ";
cin >> search;

EmployeeInfo tempEmp;
tempEmp.setEmpID(search);

if (!staff.searchNode(tempEmp))
        cout << "Employee ID not found.\n";

// else if staff.searchNode(tempEmp) == true, employee info will 
// be displayed from Binary Tree searchNode method

Upvotes: 1

Related Questions