Debug assertion failed: _BLOCK_TYPE_IS_VALID(phead->nBlockUse)

[BananaCode]

Hey,

So I'm trying my hands with pointers by doing a binary search tree, however I've hit an other roadblock again. Here's the code:

class node
{
	public:
	node* left;
	node* right;
	node* root_;
	int value;

	node(int num, node* root)
	{
		value = num;
		left = right = NULL;
		root_ = root;
	}

	~node()
	{
		delete left;
		delete right;
		delete root_;
	}

	node* find(int num, node& root)
	{
		node* FoundNode;
		if(root.value < num)
		{
			if (root.right == NULL)
			{
				FoundNode = &root;
			}
			else
			{
				FoundNode = find(num, *root.right);
			}
		}
		if (root.value > num)
		{
			if (root.left == NULL)
			{
				FoundNode = &root;
			}
			else
			{
				FoundNode = find(num, *root.left);
			}
		}
		else
		{
			FoundNode = &root;
		}

		return FoundNode;
	} 
	//returns pointer to element if found or pointer to last element searched.

	void insert(int num, node& root)
	{
		node* position = find(num, root);
		node pos = *position;
		if (pos.value < num)
		{
			node temp(num, position);
			pos.right = &temp;
		}
		else if (pos.value > num)
		{
			node temp(num, position);
			pos.left = &temp;
		}
	}
	//inserts element in correct position if not found.
void traverse(node root)
	{
		if (root.left != NULL)
			traverse (*root.left);
		if (root.right != NULL)
			traverse (*root.right);
		cout << root.value;
	}
}

int main()
{
	node root (10, NULL);
	root.insert(9, root);
	root.traverse(root);
	system("sleep");
	return 0;
}

I'm completely new to pointers. I've searched the net a little and found out that it has to do with wrongly allocated memory of some sort. While trying to debug this thing, I noticed it crashes as soon as the function "insert" finishes. What am I doing wrong?

[Moschops]

In your destructor, you're trying to delete something you shouldn't be trying to delete. Replace your destructor with this and see if you can work it out :)

cout << left << " " << right << " " << root << endl;
cout << "Now delete left" << endl;
delete left;
cout << "Now delete right" << endl;
delete right;
cout << "Now delete root_" << endl;
		delete root_;

[Peter87]

There are many problems with this code.

You are not using any of the member variables of the object that the function is called on which is a bit weird. You should not have to pass in the root node as argument to the functions. The node itself is the root of the sub tree.

When you create a node like you do on line 60, 63 and 68 the node will stop to exist when it goes out of scope. If you want to create a node object that stays alive after the current scope has ended you can use new. node temp(num, position); becomes node* temp = new node(num, position);
You have to keep at least one pointer to the object otherwise you will not be able to reach it later.

On line 37 you should have else if.

[BananaCode]

Well I removed the delete root_; command, and it seems to run without errors. But, why is it calling the destructor so many times? I don't understand. I thought it only calls the destructor when something isn't "reachable" anymore.

In addition, my insert method isn't working. I'm passing the values by reference, but it doesn't seem to change the "root" object in the main feature. Why is that?

[BananaCode]

Peter, you mean like this?

void insert(int num)
	{
		node* position = find(num, *this);
		node pos = *position;
		if (pos.value < num)
		{
			pos.right = new node(num, position);
		}
		else if (pos.value > num)
		{
			pos.left = new node(num, position);
		}
	}
	//inserts element in correct position if not found. 

It still seems to delete the element.

[Peter87]

pos will be deleted at the end of the insert function. If I understand it correctly you want to modify the node object pointed to by position. In that case just use position->right and position->left and remove pos from your code.

[BananaCode]

Oh thank you so much. It works now! I'll ask more questions here if I experience any road blocks.

Regards

[BananaCode]

Everythings working now, and I've written my first datastructure, the binary tree, with basic functions like insert, remove, post-order traverse and height calculation. Thanks again for all the help I got.