CODEWITHSUNDEEP
c++binary-search-tree
Stupore
Stupore

Reputation: 3

Binary Search Tree Template

I'm fairly new to c++ and I've recently received a project to create my own Binary Search Tree using a Template. The goal is for the Binary Tree to be able to take in any kind of data type. IntBinaryTree.h should be able to take in object of EmployeeInfo. I've gotten it to compile but I get an error message of glibc detected double free or corruption (fasttop) I'm not exactly sure what this means. Also I'm not sure if I've set the program up correctly. Also note, I'm testing functions 1 by 1 in main.cpp that's why there is only insert function being used.

Update I allocated memory for the insertNode function by TreeNode *newNode = new TreeNode, now I get error message of "in instantiation of void IntBinaryTree::insertNode(T) [with T = EmployeeInfo]: main.cpp:22:29 required from here "

#ifndef EMPLOYEEINFO_H
#define EMPLOYEEINFO_H

#include<iostream>
#include<string>
#include<cstdlib>

using namespace std;

class EmployeeInfo
{
public:
    EmployeeInfo(int, string);
    ~EmployeeInfo();
    //void print();
    int getEmployeeID();
    string getEmployeeName();
    void setEmployeeID(int);
    void setEmployeeName(string);
    bool operator ==(const EmployeeInfo &eO1) {return EmployeeID == eO1.EmployeeID;}
    bool operator >(const EmployeeInfo &eO1) {return EmployeeID > eO1.EmployeeID;}
    bool operator <(const EmployeeInfo &eO1) {return EmployeeID < eO1.EmployeeID;}

private:    
    int EmployeeID;
    string EmployeeName;
};

#endif


#include"EmployeeInfo.h"
#include<iostream>
#include<string>
#include<cstdlib>

using namespace std;

EmployeeInfo::EmployeeInfo(int empID, string name)
{
   EmployeeID = empID;
   EmployeeName = name;
}

EmployeeInfo::~EmployeeInfo()
{
}

int EmployeeInfo::getEmployeeID()
{
   return EmployeeID;
}

string EmployeeInfo::getEmployeeName()
{
   return EmployeeName;
}

void EmployeeInfo::setEmployeeID(int empID)
{
   EmployeeID = empID;
}

void EmployeeInfo::setEmployeeName(string name)
{
   EmployeeName = name;
}


#ifndef INTBINARYTREE_H
#define INTBINARYTREE_H

#include <iostream>
#include<string>
#include<cstdlib>
#include <iomanip>

using namespace std;

template<class T>
struct TreeNode
{
   T value;
   TreeNode<T> *left;
   TreeNode<T> *right;
};

template<class T>
class IntBinaryTree
{
   private:
      TreeNode<T>* root;
      void insert(TreeNode<T> *&, TreeNode<T> *&);
      void destroySubTree(TreeNode<T> *);
      void deleteNode(T, TreeNode<T> *&);
      void makeDeletion(TreeNode<T> *&);
      void displayInOrder(TreeNode<T> *) const;
      void displayPreOrder(TreeNode<T> *) const;
      void displayPostOrder(TreeNode<T> *) const;
   public:
      //Constructor
      IntBinaryTree();
     ~IntBinaryTree(){destroySubTree(root);}

      //Binary Tree Operations
      void insertNode(T);
      bool searchNode(T);
      void remove(T);

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

};

template<class T>
IntBinaryTree<T>::IntBinaryTree()
{
   root = NULL;
}

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

template<class T>
void IntBinaryTree<T>::insertNode(T val)
{
   TreeNode<T> *newNode;

   newNode->value = val;
   newNode->left = newNode->right = NULL;

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

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

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

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

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

   cout << "Binary Tree Destroyed\n";
}

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

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

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

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

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

   if (nodePtr == NULL)
       cout << "Cannot delete empty node\n";
   else if(nodePtr->right == NULL)
   {
       tempNodePtr = nodePtr;
       nodePtr = nodePtr->left;
       delete tempNodePtr;
   }
   else if(nodePtr->left == NULL)
   {
       tempNodePtr = nodePtr;
       nodePtr = nodePtr->right;
       delete tempNodePtr;
   }
   //If the node has two Children
   else
   {
       //Move one node to the right
       tempNodePtr = nodePtr->right;
       //Go to the end left node
       while(tempNodePtr->left)
          tempNodePtr = tempNodePtr->left;
       //Reattach the left subtree
       tempNodePtr->left = nodePtr->left;
       tempNodePtr = nodePtr;
       //Reattach the right subtree
       nodePtr = nodePtr->right;
       delete tempNodePtr;
   }
}

#endif



#include"EmployeeInfo.cpp"
#include"IntBinaryTree.h"
#include<iostream>
#include<string>
#include<cstdlib>

using namespace std;

int main()
{       
   IntBinaryTree<EmployeeInfo> mytree;

   EmployeeInfo employee1(1021, "John Williams");
   EmployeeInfo employee2(1057, "Bill Witherspoon");
   EmployeeInfo employee3(2487, "Jennifer Twain");
   EmployeeInfo employee4(3769, "Sophia Lancaster");
   EmployeeInfo employee5(1017, "Debbie Reece");
   EmployeeInfo employee6(1275, "George McMullen");
   EmployeeInfo employee7(1899, "Ashley Smith");
   EmployeeInfo employee8(4218, "Josh Plemmons");

   mytree.insertNode(employee1);
   mytree.insertNode(employee2);
   mytree.insertNode(employee3);
   mytree.insertNode(employee4);
   mytree.insertNode(employee5);
   mytree.insertNode(employee6);
   mytree.insertNode(employee7);
   mytree.insertNode(employee8);

   return 0;
}

Upvotes: 0

Views: 2258

Answers (1)

The Dark
The Dark

Reputation: 8514

In your insertNode method, you do not allocate any space for your node and you use an uninitialized pointer:

TreeNode<T> *newNode;

newNode->value = val;
newNode->left = newNode->right = NULL;

You need to allocate some memory for your node:

TreeNode<T> *newNode = new TreeNode<T>;

I highly recommend learning to use the debugger, so you can trace through your code line by line to see what it is doing. No one writes perfect code each time, and a debugger is the easiest way to see what is going wrong.

Edit: The above won't work as you don't have a default constructor for Employee, but you only have a default constructor for TreeNode. This means you can't create a TreeNode that contains an Employee.

The best way to fix this, is to add a constructor to TreeNode that takes a parameter that is a reference to a T object, so that it can initialize its own value object from that parameter.

Add this to your TreeNode class

TreeNode(T &val) : value(val), left(NULL), right(NULL) { }

This code copies the val parameter into value and initializes the left and right pointers.

Then change your insert code to.

TreeNode<T> *newNode = new TreeNode < T > (val) ;
//Insert the Node
insert(root, newNode);

Note that there is no need to set the left and right pointers, as the constructor now does that for you.

Upvotes: 0

Related Questions