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!