BinaryTree search function

[Lilspree]

I need my if(tree.searchNode(info) located in main to return the corresponding employee name. The user is supposed to enter the ID number of the employee he or she wants to search for. If the ID number exist it displays the employee name. I'm having trouble with that. Any suggestions?

  #ifndef EMPLOYEEINFO_H
#define EMPLOYEEINFO_H
#include <string>
#include <iostream>
using namespace std;

// This class has two data members to hold the employee ID
// and the name of the employee.

class EmployeeInfo
{
private:
    int empID;      // To hold employee ID number
    string empName; // To hold employee name

public:
    // Default Constructor
    EmployeeInfo();

    // Constructor
    EmployeeInfo(int, string);

    // Mutators
    void setEmpID(int);
    void setEmpName(string);

    // Accessors
    int getEmpID();
    string getEmpName();

	// Overloaded operator. This works directly with
	// the insert function of BinaryTree.h more specifically
	// line 71. *For my knowledge*
	bool operator < (const EmployeeInfo &e)
	{
		if (empID < e.empID)
			return true;
		return false;
	}
	// 124
	bool operator == (const EmployeeInfo &e)
	{
		if (empID == e.empID)
			return true;
		return false;
	}

};
#endif
#include "EmployeeInfo.h"

//*********************************************************
// Default constructor intializes the data members        *
//*********************************************************
EmployeeInfo::EmployeeInfo()
{
	empName = "";
    empID = 0;  
}

//*********************************************************
// Constructor sets the data members                      *
//*********************************************************
EmployeeInfo::EmployeeInfo(int ID, string name)
{
	empName = name;
    empID = ID; 
}

//*********************************************************
// setEmpID stores the employee ID number                 *
//*********************************************************
void EmployeeInfo::setEmpID(int ID)
{
    empID = ID;
}

//*********************************************************
// setEmpName stores the full name of the employee        *
//*********************************************************
void EmployeeInfo::setEmpName(string name)
{
    empName = name;
}

//*********************************************************
// getEmpID returns the employee ID number                *
//*********************************************************
int EmployeeInfo::getEmpID()
{
    return empID;
}

//*********************************************************
// getEmpName returns the full name of the employee       *
//*********************************************************
string EmployeeInfo::getEmpName()
{
    return empName;
}

#ifndef BINARYTREE_H
#define BINARYTREE_H
#include <iostream>
using namespace std;

// This class is a template class that creates a binary
// tree that can hold values of any data type. It has 
// functions to insert a node, delete a node, display the
// tree In Order, Pre Order and Post Order, search for a 
// value, count the number of total nodes, left nodes, 
// and a function to determine the height of the tree.

template <class T>
class BinaryTree
{
private:
    struct TreeNode
    {
        T value;            // The value in the node
        TreeNode *left;     // Pointer to left child node
        TreeNode *right;    // Pointer to right child node
    };

    TreeNode *root;         // Pointer to the root node

    // Private member 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;
 
public:
    // Constructor
    BinaryTree()
    { root = NULL; }

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

    // Binary tree operations
    void insertNode(T);
    bool searchNode(T);
    void remove(T);

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

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

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

};

//*********************************************************
// insert function accepts a TreeNode pointer and a       *
// pointer to a node. The function inserts the node into  *
// the tree pointer to by the TreeNode pointer. This      *
// function is call recursively.                          *
//*********************************************************
template <class T>
void BinaryTree<T>::insert(TreeNode *&nodePtr, TreeNode *&newNode)
{
    if (nodePtr == NULL)
        nodePtr = newNode;              // Insert the node
    else if (newNode->value < nodePtr->value)
        insert(nodePtr->left, newNode); // Search the left branch
    else
        insert(nodePtr->right, newNode);// Search the right branch
}

//*********************************************************
// insertNode creates a new node to hold item as its value*
// and passes it to the insert function.                  *
//*********************************************************
template <class T>
 void BinaryTree<T>::insertNode(T item)
 {
     TreeNode *newNode;     // Pointer to a new node

     // Create anew node and store num in it
     newNode = new TreeNode;
     newNode->value = item;
     newNode->left = newNode->right = NULL;

     // Insert the node
     insert(root, newNode);
 }

//**********************************************************
// destroySubTree is called by the destructor. It deletes  *
// all nodes in the tree.                                  *
//**********************************************************
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;
     }
}

//**********************************************************
// searchNode determines if a value is present in the tree.*
// If so, the function returns true. Otherwise it returns  *
// false.
//**********************************************************
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;
}


#endif

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

int main()
{

    // Create an instance of BinaryTree
    BinaryTree<EmployeeInfo> tree;

    // Create an EmployeeInfo object
    EmployeeInfo emp1(1021, "John Williams");
    EmployeeInfo emp2(1057, "Bill Witherspoon");
	EmployeeInfo emp3(2487, "Jennifer Twain");
	EmployeeInfo emp4(3769, "Sophia Lancaster");
	EmployeeInfo emp5(1017, "Debbie Reece");
	EmployeeInfo emp6(1275, "George McMullen");
	EmployeeInfo emp7(1899, "Ashley Smith");
	EmployeeInfo emp8(4218, "Josh Plemmons");    

    tree.insertNode(emp1);
    tree.insertNode(emp2);
	tree.insertNode(emp3);
	tree.insertNode(emp4);
    tree.insertNode(emp5);
	tree.insertNode(emp6);
	tree.insertNode(emp7);
    tree.insertNode(emp8);

	// Search for an employee
	char again = 'y';		// To hold yes
	int id;					// To hold ID number from user

	cout << "Would you like to search for an employee?\n";
	cout << "Enter Y for yes or N for No: ";
	cin >> again;
	if (again)
	{
		do
		{
			cout << "Enter the ID number of the employee: ";
			cin >> id;
			// Create an EmployeeInfo object to store the user's 
			// search parameters
			EmployeeInfo info;
			info.setEmpID(id);

			// If search finds what the user entered display the 
			// corresponding employee
			if (tree.searchNode(info))
			{
				
				cout << info.getEmpName() << endl;
			}
			else
				cout << "ID not found!" << endl;

			cout << "Would you like to search for an employee?\n";
			cout << "Enter Y for yes or N for No: ";
			cin >> again;
		}while (again == tolower('Y'));
	}


    // Display in order
    tree.displayInOrder();
	cout << endl;
	tree.displayPreOrder();
	cout << endl;
	tree.displayPostOrder();
}

[TheIdeasMan]

Hi Lilspree,

The user is supposed to enter the ID number of the employee he or she wants to search for. If the ID number exist it displays the employee name. I'm having trouble with that. Any suggestions?

Some really lazy (on my part), but very very useful advice: Learn to use a debugger - it will literally save you days of wondering what is wrong with the code. Step through the code 1 line at a time and keep an eye the values of your variables. Programs like valgrind can help too.

Also, what does the program do exactly (what is the output) - it might give a clue as to where to look.

Edit: removed wrong advice

Some other stuff that is good practice, and probably nothing to do with your problem:

Don't have using namespace std; - it brings in the entire std namespace which can cause naming conflicts, which is what namespaces were designed to avoid! put std:: before each std thing - as in std::cout for example. Really you should put your own stuff in it's own namespace.

Trivial accessor functions can be inlined - for example:

inline int getEmpID() { return empID;}

inline is just advice to the compiler: it will decide whether it will actually inline the function. Anything that is too long, recursive, contains loops or anything thing else it thinks will impact adversely won't be inlined.

Use initialiser lists in constructors:

EmployeeInfo::EmployeeInfo(int ID, string name) : // colon introduces init list
     empID(ID),
     empName(name);
{}

This is because variable are automatically initialised before any code in the constructor is executed, so doing this saves re-initialising them by assignment. One can initialise base classes from here too, if required.

Rather than using new & delete, try using smart pointers instead. The main problem with delete is early termination by exception or other means, so the destructor is never called.


Hope that helps