Thread: 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 ), 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

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?

>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.