-
Binary Tree Search
Howdy,
I was reading Preludes Binary Tree Search article, and figured I'd give it a go myself.
Heres what I managed to get, but it doesn't seem to be working :S
Code:
#include <iostream>
#include <windows.h>
#include <string>
using std::string;
using std::cout;
using std::cin;
using std::endl;
//=============================================
// Tree Branch
//=============================================
class TreeBranch
{
public:
int Data;
TreeBranch * Branches[2];
TreeBranch()
{
Data = 0;
Branches[0] = NULL;
Branches[1] = NULL;
}
};
class TreeTop
{
public:
TreeTop()
{
Size = 0;
Header = NULL;
}
int Size;
TreeBranch * Header;
bool Find(int SearchKey);
bool Insert(TreeBranch * NewValue, int New);
};
//=============================================
// TreeTop::Find()
//=============================================
bool TreeTop::Find(int SearchKey)
{
TreeBranch * Walk;
int Direction;
Walk = Header;
for (;;)
{
if (Walk == NULL)
{
// Reached the end :(
return false;
}
if (Walk->Data == SearchKey)
{
// Found what we were looking for!
return true;
}
Direction = Walk->Data < SearchKey;
Walk = Walk->Branches[Direction];
}
}
//=============================================
// TreeTop::Insert()
//=============================================
bool TreeTop::Insert(TreeBranch * NewValue, int New)
{
// Search for a dead link
TreeBranch * Walk;
TreeBranch ** Save;
int Direction;
Save = &this->Header;
Walk = Header;
for (;;)
{
if (Walk == NULL)
{
// Reached a dead link
break;
}
else if (Walk->Data == NewValue->Data)
{
// The value already exists!
cout << "New value of " <<
NewValue->Data << " already exists!" << endl;
return false;
}
// Ok, we didn't find it, but we do have branches left...
Direction = Walk->Data < NewValue->Data;
Save = &Walk->Branches[Direction];
Walk = Walk->Branches[Direction];
}
*Save = NewValue;
this->Size++;
cout << endl << "New value (" << NewValue->Data
<< ") inserted at: " << &Save << endl;
return true;
}
//=============================================
// Main()
//=============================================
int main()
{
cout << "Creating new tree... ";
TreeTop Tree;
Tree.Size = 0;
Tree.Header = NULL;
cout << "OK" << endl;
cout << "Populating Tree... ";
TreeBranch * NewValue = new TreeBranch;
NewValue->Data = 9;
Tree.Insert(NewValue, 9);
NewValue->Data = 8;
Tree.Insert(NewValue, 8);
NewValue->Data = 5;
Tree.Insert(NewValue, 5);
NewValue->Data = 2;
Tree.Insert(NewValue, 2);
NewValue->Data = 8;
Tree.Insert(NewValue, 8);
NewValue->Data = 7;
Tree.Insert(NewValue, 7);
delete NewValue;
cout << "OK" << endl;
cout << "Searching the tree for '2'... ";
if (Tree.Find(2) == true)
{
cout << "Found!" << endl;
}
else cout << "Not Found!" << endl;
return 0;
}
When I run it, I get:
Code:
Creating new tree... OK
Populating Tree...
New value (9) inserted at: 0012FEF0
New value of 8 already exists!
New value of 5 already exists!
New value of 2 already exists!
New value of 8 already exists!
New value of 7 already exists!
OK
Searching the tree for '2'...
And it freezes when it tries to find the new values... whats going on?:S I think I've done something wrong with the pointers somewhere, gosh I hate them!
-
As you've created this in main():
TreeBranch * NewValue = new TreeBranch;
then passed it to the insert function, the tree holds the same address as main()'s pointer, meaning the tree and NewValue are pointing to the same thing. Changing the value of the data in main() affects the data pointed to by the tree, which is why the tree thinks most of the data already exists.
You should be creating leaves in the tree class, not in main, and copying the data to them.
Also, these shouldn't be in main():
Tree.Size = 0;
Tree.Header = NULL;
They should be private members of the class, so that no-one can screw up the tree except the class itself ;)
-
Hammer beat me to it (I'm slowing down in my old age :p), but here is the (ugly as sin) code for one of my test drivers for the basic functions from that article. It may help you...somehow:
Code:
#ifdef TEST_DRIVER
#include <stdio.h>
#include <stdlib.h>
void print_node ( int value, int level )
{
int i;
for ( i = 0; i < level; i++ )
printf ( "\t" );
printf ( "%d\n", value );
}
void print_tree_structure ( struct pretree_node *node, int level )
{
if ( node == NULL )
print_node ( -1, level );
else {
print_tree_structure ( node->link[1], level + 1 );
print_node ( node->data, level );
print_tree_structure ( node->link[0], level + 1 );
}
}
int main ( void )
{
struct pretree tree = {0};
struct pretree_node *node;
int i;
for ( i = 0; i < 20; i++ ) {
node = malloc ( sizeof *node );
if ( node == NULL )
break;
node->data = rand() % 10;
node->link[0] = node->link[1] = NULL;
pretree_insert ( &tree, node, node->data );
}
print_tree_structure ( tree.header, 0 );
while ( tree.header != NULL ) {
printf ( "\n-----------------------------------\n" );
printf ( "Item to remove: " );
fflush ( stdout );
pretree_remove ( &tree, &node, getchar() - '0' );
getchar();
print_tree_structure ( tree.header, 0 );
}
return 0;
}
#endif
-
Ahhhh ok, I understand, thanks guys :) Since I was changing the same place in memory that was being used by the tree, the data in the tree was also changed (since really its the same data...) gotcha :D
This is what main() looks like:
Code:
int main()
{
cout << "Creating new tree... ";
TreeTop Tree;
cout << "OK" << endl;
cout << "Populating Tree... ";
TreeBranch * NewValue = new TreeBranch;
NewValue->Data = 9;
Tree.Insert(NewValue, 9);
TreeBranch * NewValue2 = new TreeBranch;
NewValue2->Data = 7;
Tree.Insert(NewValue2, 7);
TreeBranch * NewValue3 = new TreeBranch;
NewValue3->Data = 2;
Tree.Insert(NewValue3, 2);
TreeBranch * NewValue4 = new TreeBranch;
NewValue4->Data = 6;
Tree.Insert(NewValue4, 6);
delete NewValue;
delete NewValue2;
delete NewValue3;
delete NewValue4;
cout << "OK" << endl;
cout << "Searching the tree for '2'... ";
if (Tree.Find(2) == true)
{
cout << "Found!" << endl;
}
else cout << "Not Found!" << endl;
return 0;
}
I also had to be careful not to delete a NewValue variable before they were created.
Now however its still pausing when searching for the number 2, even though it has been put in. The Find() function hasn't changed since I first posted... what could be causing this problem?
-
Hm interesting,
I did a little looking and found the loop in Find() only ever runs once right to the end of the loop. Then it seems to go to start again, but nothing happens, then I get an application error.
VC++ says its an Unhandled exception, access invalid (I think), on this line:
if (Walk->Data == SearchKey)
Hm... could it be because ones an int, and the other is an int but one that is in a part of memory that belongs to another part of the application? Although that shouldn't matter should it...
This is the output I managed to get before it crashed:
Code:
Creating new tree... OK
Populating Tree...
New value (9) inserted at: 0012FEB4
New value (7) inserted at: 0012FEB4
New value (2) inserted at: 0012FEB4
New value (6) inserted at: 0012FEB4
OK
Searching the tree for '2'...
-
Omg I'm so naughty, I deleted the memory that it was stored in, so therefore I didn't own that memory, which explains the access violation. Its all fixed now, I wont use new and delete I'll just make them as regular variables hehe... thanks for all the help guys :)
And thanks for the great tutorial Prelude! I haven't finished reading it all but I plan to.
-
>I wont use new and delete I'll just make them as regular variables hehe...
You'll have more luck with new and delete, but new creates a node that is placed in the tree. The memory should only be released when the node is removed from the tree, which is usually only two cases:
1) A single node is removed from the tree by a call to a remove routine. This is the hardest as you have to unlink the node, fix the structure of the tree, then release the memory, resulting in a stable tree.
2) All nodes in the tree are removed, usually with a postorder recursive traversal. This is easier as you only have to worry about releasing the nodes in the correct order so that you can reach all of them. The structure of the tree after this operation is irrelevant.
-
This is what my code is currently, not a problem as far as I can tell:
Code:
#include <iostream>
#include <windows.h>
#include <string>
using std::string;
using std::cout;
using std::cin;
using std::endl;
//=============================================
// Tree Branch
//=============================================
class TreeBranch
{
public:
int Data;
TreeBranch * Branches[2];
TreeBranch()
{
Data = 0;
Branches[0] = NULL;
Branches[1] = NULL;
}
};
class TreeTop
{
public:
TreeTop()
{
Size = 0;
Header = NULL;
}
int Size;
TreeBranch * Header;
bool Find(int SearchKey);
bool Insert(TreeBranch * NewValue, int New);
bool NewInsert(int New);
};
//=============================================
// TreeTop::Find()
//=============================================
bool TreeTop::Find(int SearchKey)
{
TreeBranch * Walk;
int Direction;
Walk = Header;
for (;;)
{
if (Walk == NULL)
{
// Reached the end :(
return false;
}
if (Walk->Data == SearchKey)
{
// Found what we were looking for!
return true;
}
// Ok, we didn't find it, but we do have
// branches left...
Direction = Walk->Data < SearchKey;
Walk = Walk->Branches[Direction];
cout << ".";
}
}
//=============================================
// TreeTop::Insert()
//=============================================
bool TreeTop::Insert(TreeBranch * NewValue, int New)
{
// Search for a dead link
TreeBranch * Walk;
TreeBranch ** Save;
int Direction;
Save = &this->Header;
Walk = Header;
for (;;)
{
if (Walk == NULL)
{
// Reached a dead link
break;
}
else if (Walk->Data == NewValue->Data)
{
// The value already exists!
cout << "New value of " <<
NewValue->Data << "
already exists!" << endl;
return false;
}
// Ok, we didn't find it, but we do have
// branches left...
Direction = Walk->Data < NewValue->Data;
Save = &Walk->Branches[Direction];
Walk = Walk->Branches[Direction];
}
*Save = NewValue;
this->Size++;
cout << endl << "New value (" << NewValue->Data
<< ") inserted at: " << &Save << endl;
return true;
}
bool TreeTop::NewInsert(int New)
{
// Search for a dead link
TreeBranch * Walk;
TreeBranch ** Save;
int Direction;
TreeBranch * NewValue = new TreeBranch;
if (NewValue == NULL)
{
return false;
}
NewValue->Data = New;
Save = &this->Header;
Walk = Header;
for (;;)
{
if (Walk == NULL)
{
// Reached a dead link
break;
}
else if (Walk->Data == NewValue->Data)
{
// The value already exists!
cout << "New value of " <<
NewValue->Data << " already
exists!" << endl;
return false;
}
// Ok, we didn't find it, but we do have
// branches left...
Direction = Walk->Data < NewValue->Data;
Save = &Walk->Branches[Direction];
Walk = Walk->Branches[Direction];
}
*Save = NewValue;
this->Size++;
cout << endl << "New value (" << NewValue->Data
<< ") inserted at: " << &Save << endl;
return true;
}
//=============================================
// Main()
//=============================================
int main()
{
cout << "Creating new tree... ";
TreeTop Tree;
cout << "OK" << endl;
cout << "Populating Tree... ";
Tree.NewInsert(6);
Tree.NewInsert(7);
Tree.NewInsert(3);
Tree.NewInsert(32);
Tree.NewInsert(45);
Tree.NewInsert(67);
Tree.NewInsert(1);
Tree.NewInsert(12);
Tree.NewInsert(8);
Tree.NewInsert(2);
Tree.NewInsert(9);
cout << "OK" << endl;
cout << "Searching the tree for '2'... ";
if (Tree.Find(2) == true)
{
cout << "Found!" << endl;
}
else cout << "Not Found!" << endl;
return 0;
}