Deconstructor issue on Binary Search Tree

[jcorney]

I am having a weird issue. I ran the following program without the function call prePostInOrder(); and put it back into main and it works just fine but the moment I put the function call into use the program crashes. I ran a debugger and found that there was an issue in my freeTree when this function call was made so I commented out the delete r in freeTree() function that is located in my BST.h and it worked. Anyone know why its crashing?

I am using Microsoft Visual Studio 10

Here is my .cpp file, below that are my two .h files. Any help is very Appreciated!

#include <iostream>
#include "BST.h"
#include "BSTNode.h"
using namespace std;

void prePostInOrder(BST<int> tree);



int main()
{

int treeArray2[7] = {1, 2, 3, 4, 5, 6, 7};

BST<int> tree2;

for(int i = 0; i < 7; i++)
{
tree2.insert(treeArray2[i]);
}


prePostInOrder(tree2);


return 0;
}


void prePostInOrder(BST<int> tree)
{
list<int> L1, L2, L3;

cout << endl << "Tree pre-order = ";
tree.preorder(L1);
for(list<int>::iterator it = L1.begin(); it != L1.end(); it++)
{
cout << *it << " ";
}

//In-order
cout << endl << endl<< "Tree in order = ";
tree.inorder(L2);
for(list<int>::iterator it = L2.begin(); it != L2.end(); it++)
{
cout << *it << " ";
}

//Post-order
cout << endl << endl << "Tree post order = ";
tree.postorder(L3);
for(list<int>::iterator it = L3.begin(); it != L3.end(); it++)
{
cout << *it << " ";
}


};


#ifndef BSTNODE_H_
#define BSTNODE_H_

#include <iostream>
using namespace std;

template <class T>
class BST;

template <class T>
class BSTNode {
friend class BST<T>;
private:
BSTNode() : left(NULL), right(NULL), parent(NULL) {};
BSTNode(T x) : data(x), left(NULL), right(NULL), parent(NULL) {};
virtual ~BSTNode() {};

T data;
BSTNode<T> *left;
BSTNode<T> *right;
BSTNode<T> *parent;
};




#endif /* BSTNODE_H_ */

Here is my BST.h file, The issue starts down at freeTree() at the bottom. If I comment out delete r in freeTree I do not have an issue? Does anyone know why?



#ifndef BST_H_
#define BST_H_

#include "BSTNode.h"
#include <list>
using namespace std;

template<class T>
class BST {
public:
BST() :
root(NULL), size(0) {
}
virtual ~BST();

bool isEmpty();

bool member(T x);

void insert(T x);

bool remove(T x);

int inorder(list<T>& result);

int preorder(list<T>& result

int postorder(list<T>& result);

double averageProbeCount();


private:
BSTNode<T> *root;
int size;

BSTNode<T> *findNewParent(T x, BSTNode<T> *r);
BSTNode<T> *search(T x, BSTNode<T> *r);
void remove(BSTNode<T> *r);
bool isLeaf(BSTNode<T> *r);
bool hasSingleChild(BSTNode<T> *r);
BSTNode<T> *findMax(BSTNode<T> *r);


void inorder(list<T>& result, BSTNode<T> *r);

void preorder(list<T>& result, BSTNode<T> *r);

void postorder(list<T>& result, BSTNode<T> *r);
void freeTree(BSTNode<T> *r);
void findAllDepth(list<T>& result, BSTNode<T> *r, int depth);

};
// end BST

// -----------------------------------
// code for the public methods
//------------------------------------
template<class T>
BST<T>::~BST()
{
freeTree(root); // free all the nodes in the tree
size = 0;
};

template<class T>
bool BST<T>::isEmpty()
{
return size == 0;
};

template<class T>
bool BST<T>::member(T x)
{
BSTNode<T> *p = search(x, root);
if (p == NULL)
return false;

else
return true;

};

template<class T>
void BST<T>::insert(T x)
{
BSTNode<T> *newNode = new BSTNode<T>(x);
BSTNode<T> *p = findNewParent(x, root);

if (p == NULL)
root = newNode; //new root
else if (x < p->data) {
p->left = newNode; //left child of parent
newNode->parent = p;
} else {
p->right = newNode; //right child of parent
newNode->parent = p;
}
size++;
}; //end insert

template<class T>
bool BST<T>::remove(T x)
{
BSTNode<T> *delNode = search(x, root);
if (delNode != NULL) {
remove(delNode);
size--;
return true;
} else {
return false;
}
};

template<class T>
int BST<T>::inorder(list<T>& result)
{
inorder(result, root);
return size;
};

template<class T>
int BST<T>::preorder(list<T>& result)
{
preorder(result, root);
return size;
};

template<class T>
int BST<T>::postorder(list<T>& result)
{
postorder(result, root);
return size;
};

template<class T>
int BST<T>::maxDepth()
{
list<int> L;
findAllDepth(L, root, 0);
int max = 0;
list<int>::iterator i;
for (i = L.begin(); i != L.end(); ++i) {
if (max < *i) {
max = *i;
}
}
return max;
};

template<class T>
double BST<T>::averageProbeCount()
{
if (root == NULL) {
return 0;
} else {
list<int> L;
findAllDepth(L, root, 0);
int sum = 0;
list<int>::iterator i;
for (i = L.begin(); i != L.end(); ++i) {
sum += (*i + 1); // Note: # of probes is always 1+depth
}

return (double) (sum) / size; // note that it is an integer division
}
};


template<class T>
BSTNode<T>* BST<T>::findNewParent(T x, BSTNode<T> *r)
{
if (r == NULL) // empty tree
return NULL;
else if (x < r->data) { // go down left subtree
if (r->left == NULL)
return r;
else
return findNewParent(x, r->left);
} else { // x >= r->data
if (r->right == NULL)
return r;
else
return findNewParent(x, r->right);
}
}; // findNewParent

template<class T>
BSTNode<T>* BST<T>::search(T x, BSTNode<T> *r)
{
if (r == NULL)
return NULL;
else if (r->data == x)
return r;
else if (x < r->data)
return search(x, r->left);
else
return search(x, r->right);
};

template<class T>
void BST<T>::remove(BSTNode<T> *delNode)
{
BSTNode<T> *p;

if (isLeaf(delNode)) { // case 1
if (delNode == root)
root = NULL;
else {
p = delNode->parent;
if (delNode == p->left)
p->left = NULL;
else
p->right = NULL;
}
delete delNode;
} else if (hasSingleChild(delNode)) { // case 2
BSTNode<T> *child =
(delNode->left == NULL) ? delNode->right : delNode->left;

if (delNode == root) {
root = child;
child->parent = NULL;
} else {
p = delNode->parent;
child->parent = p;
if (delNode == p->left)
p->left = child;
else
p->right = child;
}
delete delNode;
} else { // case 3
BSTNode<T> *pred = findMax(delNode->left);
if (pred == delNode->left) { // case 3b
delNode->data = pred->data;
delNode->left = pred->left;
if (delNode->left != NULL)
delNode->left->parent = delNode;
delete pred;
} else { // case 3a
delNode->data = pred->data;
remove(pred);
}
}
}; // end remove

// returns true if r is a leaf node
template<class T>
bool BST<T>::isLeaf(BSTNode<T> *r)
{
return r->left == NULL && r->right == NULL;
};

// returns true if r has only one child
template<class T>
bool BST<T>::hasSingleChild(BSTNode<T> *r)
{
return (r->left == NULL && r->right != NULL)
|| (r->left != NULL && r->right == NULL);
};

template<class T>
BSTNode<T>* BST<T>::findMax(BSTNode<T> *r)
{
if (r == NULL) // empty tree
return NULL;
else if (isLeaf(r)) // singleton tree
return r;
else if (r->right == NULL) // r is the largest node
return r;
else
// largest node is in r’s right subtree
return findMax(r->right);
};

template<class T>
void BST<T>::inorder(list<T>& result, BSTNode<T> *r)
{
if (r != NULL) {
inorder(result, r->left);
result.push_back(r->data);
inorder(result, r->right);
}
};

template<class T>
void BST<T>::preorder(list<T>& result, BSTNode<T> *r)
{
if (r != NULL) {
result.push_back(r->data);
preorder(result, r->left);
preorder(result, r->right);
}
};

template<class T>
void BST<T>::postorder(list<T>& result, BSTNode<T> *r)
{
if (r != NULL) {
postorder(result, r->left);
postorder(result, r->right);
result.push_back(r->data);
}
};

template<class T>
void BST<T>::freeTree(BSTNode<T> *r)
{
if(r != NULL)
{
freeTree(r->left);
freeTree(r->right);
delete r;
}

};

template<class T>
void BST<T>::findAllDepth(list<T>& result, BSTNode<T> *r, int depth)
{

if (r != NULL)
{
findAllDepth(result, r->left, depth + 1);
findAllDepth(result, r->right, depth + 1);
result.push_back(depth);
}
};

#endif /* BST_H_ */

[yulingo]

The declaration of your function is like this:
void prePostInOrder(BST<int> tree)

Notice that you're passing your tree object by value, so the compiler is going to call a copy constructor to create a copy of the tree object. Since you did not define a copy constructor/assignment operator for your tree object, the compiler will go ahead and define one for you. When the compiler defines a copy-constructor, it only performs a shallow copy of your object, meaning that it will copy all of your variables, but it will not create a copy of your dynamically allocated memory. Now you have a copy of your tree, but all the pointers are still referring to the originals.

The problem with that is once execution reaches the end of prePostInOrder, the compiler destroys the local copy of the tree object by calling the destructor... which happily destroys the allocated memory of your original tree object. Therefore, when you finish your main and try to clean up your original tree, you end up trying to free already deallocated memory.

You probably want to pass the tree to prePostInOrder by reference, like:
void prePostInOrder(BST<int> &tree).