Destructor or Pointer Issue - Storing Binary Trees in a Vector

[nbstrong]

Hi, I am working on a personal project that requires storing binary trees in a vector. I can store them correctly and perform operations. The only issue is that my destructor is not working correctly. If I comment it out the code runs fine but if I do not and attempt to free up the memory it does not.

Exception thrown: read access violation.

node was 0xDDDDDDDD.

// Source.cpp
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>

#include "Environment.h"

int main(){
	const int targetfunction = 5;
	const int popsize = 3;
	const int maxgen = 3;
	const int maxtreedepth = 3;
	srand(time(0));

	// Create environment object
	Environment env(popsize, maxgen, maxtreedepth);

	env.evolve();

	return 0;
}

// Environment.cpp
#include "Environment.h"

#ifndef Environment_H
#define Environemnt_H

Environment::Environment() {
}

Environment::Environment(const int popsize, const int maxgen, const int maxdepth) {
	Popsize = popsize;
	Maxgen = maxgen;
	Maxdepth = maxdepth;
}

Environment::~Environment() {

}

void Environment::evolve() {
	std::vector<Tree> popvec;
	//std::vector<Node*> popptvec;

	for (int i = 0; i < Popsize; i++) {
		Tree membertree(Maxdepth);
		popvec.push_back(membertree);
		//popvec.emplace_back(Maxdepth);
	}

	displayVector(popvec);
	std::sort(popvec.begin(), popvec.end(), [](const Tree& obj1, const Tree& obj2) {return obj1.fitness > obj2.fitness; });
	displayVector(popvec);
	//std:random_shuffle(popvec.begin(), popvec.end());
	//displayVector(popvec);
}

void Environment::displayVector(std::vector<Tree>& popvec) {
	// Prints vector
	for (int i = 0; i < popvec.size(); i++) {
		std::cout << "Fitness[" << i << "]:" << popvec[i].fitness << std::endl;
		std::cout << "Tree:" << std::endl;
		popvec[i].displayNode(popvec[i].Root());
	} std::cout << std::endl; // keep this inline
}




#endif 

// Tree.cpp
#include "Tree.h"

#ifndef Tree_H
#define Tree_H

// Constructor
Tree::Tree() {
	root = NULL;
	fitness = rand() % 100;
}

// Overload constructor
Tree::Tree(int maxdepth) {
	root = NULL;
	fitness = rand() % 100;
	while (TreeDepth(root) < maxdepth) {
		addNode(root);
	}

}

// Copy constructor
Tree::Tree(const Tree& obj) {
	fitness = obj.fitness;
	if (obj.root == NULL) {
		root = NULL;
	}
	else {
		copyTree(this->root, obj.root);
	}
}

void Tree::copyTree(Node *& thisRoot, Node * sourceRoot) {
	if (sourceRoot == NULL)
	{
		thisRoot = NULL;
	}
	else
	{
		thisRoot = new Node;
		thisRoot->funct = sourceRoot->funct;
		thisRoot->left = sourceRoot->left;
		thisRoot->right = sourceRoot->right;
		thisRoot->up = sourceRoot->up;
		copyTree(thisRoot->left, sourceRoot->left);
		copyTree(thisRoot->right, sourceRoot->right);
	}
}

// Destructor
Tree::~Tree() {
	freeNode(root); // If I comment out this line the code runs without error
	root = NULL;
}

// Post traversal node deletion
void Tree::freeNode(Node* node) {
	if (node != NULL) {
		freeNode(node->left);
		freeNode(node->right);
		delete node;
	}
}

// Adds a node to the tree
void Tree::addNode(Node* node) {
	if (root == NULL) {
		Node* temp = new Node();
		root = temp;
	}
	else if (node->left == NULL) {
		Node* temp = new Node();
		node->left = temp;
	}
	else if (node->right == NULL) {
		Node* temp = new Node();
		node->right = temp;
	}
	else if (node->left != NULL) {
		addNode(node->left);
	}
	else if (node->right != NULL) {
		addNode(node->right);
	}
}

int Tree::TreeDepth(Node* node) {
	if (node == NULL) {
		return 0;
	}
	int nLeft = TreeDepth(node->left);
	int nRight = TreeDepth(node->right);
	return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}

void Tree::displayNode(Node* node) {
	if (node != NULL) {
		displayNode(node->left);
		std::cout << node->funct << std::endl;
		displayNode(node->right);
	}
}

// Crossover the tree
#endif 

// Node.cpp
#include "Node.h"

#ifndef Node_H
#define Node_H

Node::Node() {
	left = NULL;
	right = NULL;
	up = NULL;
	funct = rand() % 10; // 10 = range 0-9, 100 = range 0-99
}

Node::~Node() {
}

#endif 

Thank you for your help

[nbstrong]

I hope it is alright if I bump this as I am still looking for any assistance

[cire]

std::sort uses assignment (copy or move) to shuffle things about. You only have the defaulted operator which is not sufficient for the job, so you need to supply one that is sufficient.


Something like:

    Tree& operator=(Tree other) {
        if (root) freeNode(root);

        fitness = other.fitness;
        root = other.root;
        other.root = nullptr;

        return *this;
    }

Please read: http://en.cppreference.com/w/cpp/language/rule_of_three

[nbstrong]

Hi thank you for your help. That seems to be a copy constructor? Doesn't this fulfill that requirement?

// Copy constructor
Tree::Tree(const Tree& obj) {
	fitness = obj.fitness;
	if (obj.root == NULL) {
		root = NULL;
	}
	else {
		copyTree(this->root, obj.root);
	}
}

void Tree::copyTree(Node *& thisRoot, Node * sourceRoot) {
	if (sourceRoot == NULL)
	{
		thisRoot = NULL;
	}
	else
	{
		thisRoot = new Node;
		thisRoot->funct = sourceRoot->funct;
		thisRoot->left = sourceRoot->left;
		thisRoot->right = sourceRoot->right;
		thisRoot->up = sourceRoot->up;
		copyTree(thisRoot->left, sourceRoot->left);
		copyTree(thisRoot->right, sourceRoot->right);
	}
}

I have read that link but it is difficult to get through.

Edit: I am sorry I see that it is an assignment operator. I will keep reading.