Thread: Please help with BST

I'm working on a BST for the first time and need some big time help. I've gotten some of the functionality written and was wanting to test it so I've got this simple code that Inserts a node into the tree and then reads it:

Code:

#include <string>

using namespace std;

void main()
{
	CharString name = "Tyson";
	CharString att1 = "Is a scud";
	CharString att2 = "Is Married";
	int attcnt = 2;
	TreePtr X = new Node;
	strcpy(X->Info.Name, name);
	X->Info.AttributeCount = attcnt;
	strcpy(X->Info.Attribute[0], att1); 
	strcpy(X->Info.Attribute[1], att2); 

	BST Original;

	Original.Insert (X);
	Original.TestPrint (X);

	cout << "Do you want to continue?"<<endl;
	int spare;
	cin >> spare;
	
}

When I debug its getting an error in the TestPrint function, which is here:

Code:

void BST::TestPrint (TreePtr P)
{
	if (P)
	{
		TestPrint (P->Left);
		cout << Root->Info.Name << endl;
		TestPrint (P->Right);
	}
}

It goes through the loop fine the first time but when it hits TestPrint (P->Left) the second time it dies. I get this message:

Unhandled exception at 0x00433f4c in Binary_Search_Tree.exe: 0xC0000005: Access violation reading location 0xcdcdcee9.

Can someone help find the problem. I would appreciate it.

0xcdcd it what MSVC puts in allocated memory when in debug mode. Are you initializing your Left/Right pointers to NULL when you create a new node? If you are, then you're doing something bad in code you didn't post.

Zip up all your code and post it - the problem could be anywhere.

gg

try this:

Code:

void BST::TestPrint (TreePtr *P)

Not sure if this solves the problem. But my guess would be the same as Salem´s. When you add a node are you "linking" the links(pointers) correctly???

Thanks for the replies, here's all the code.

Looks like I called this one , although it really could have been any number of things:

Code:

P->Left = NULL;
P->Left = NULL; //Poor Right, he's all left out (no pun intended)

You also have some memory leaks...

Code:

TreePtr P = new Node;
...
P = data; //nevermind mr. new, I think I'll use this instead

Haven't looked at the rest of your code, but your test program will run properly when you fix these problems.

gg

Thanks for the help, that fixed it. But I'm not sure what you mean here:

---------------------------------------------------------------------------------
You also have some memory leaks...

Code:

TreePtr P = new Node;
...
P = data; //nevermind mr. new, I think I'll use this instead

----------------------------------------------------------------------------------

What should I do instead?

In your design, you have to decide who is going to manage memory, the tree or the user. I'd let the tree do it.

When you say "P = data", you just overwrote the pointer that new returned to you - memory that will never be deleted, thus a memory leak. If you want to copy the node data then you can say "*P = *data".

Remember, every new should have a cooresponding delete - you're missing one in main().

gg

Should I also have done "*P->Left = NULL"? (notice the *)

No. "*" will dereference the Left pointer, which will give you type Node, not a pointer, so setting it to NULL doesn't make sense.

Don't confuse setting a pointer value and setting the value of what the pointer points to.

Code:

int *p = new int; //assign the pointer p a new value
*p = 5; //assign what p points to a new value

gg

I need some more help with this program,


from main...

Code:

BST Original;

Original.Insert (X);
Original.Insert (Y);
Original.InOrder (cout);

I think the insertion works alright but when I get to InOrder it fails. Here's the function...

Code:

void BST::InOrder (ostream &x)
{
	InOrderTraversal (Root, x);
}

void BST::InOrderTraversal (TreePtr root, ostream & file)
{
	
	if (root)
	{
		InOrderTraversal (root->Left, file); <----- here's the error 
		file << root->Info.Name << endl;
		InOrderTraversal (root->Right, file); 
		
	}
}

The error message I'm getting is:
Unhandled exception at 0x00432b00 in Binary_Search_Tree.exe: 0xC0000005: Access violation reading location 0xfeef000a.

Any idea what's wrong?

gonna have to post your code again...

gg

here ya go.

Don't "delete P" on Insert(), that's what DestroyTree() is for - to delete everything you new'd.

Code:

int *p = new int;
int *q = p;

delete p;  //the memory pointed to by both p and q is now invalid

Also, you need to heed your compiler's warnings:

BST.cpp(70) : warning C4390: ';' : empty controlled statement found; is this the intent?
BST.cpp(88) : warning C4700: local variable 'Parent' used without having been initialized

gg