DaniWeb Forum Index > Software Development > C++

C++ RSS

Binary Search Tree

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Feb 2005

Posts: 46

Reputation: blackdove is an unknown quantity at this point

Solved Threads: 0

blackdove

Offline

Light Poster

Binary Search Tree

Mar 28th, 2006

I've been working on a binary search tree and I've written out most of what I think the code should look like but I can't test it because of an error I'm getting. I have no idea if what I have is even correct. My professor gave us the class, the structure, and the Main to use. My problem is in the getRoot(void) function. When I try compiling my code, it tells me that ptr is undeclared. I can't figure out what to change. I would appreciate it if someone could help me.

Here's my code:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
using namespace std;
 
///////////////////////////////////////////////
// tnode structure
typedef struct tnode
{
	int data;
	struct tnode *leftChild;
	struct tnode *rightChild;
}TNODE;
 
///////////////////////////////////////////////
//Binary search tree class
 
class BSTree
{
public:
	BSTree(void);
 
	void addNode(int data);
	void findNode(TNODE *ptr, int data);
	void printTree(TNODE *ptr, int level);
	TNODE *getRoot(void);
private:
	TNODE* ptr;	
};
 
///////////////////////////////////////////////
//main
 
int main()
{
	BSTree mytree;
	int level = 1;
 
	TNODE* tree;
	int i, numbers[] = {9, 7, 15, 5, 8, 14, 20, 4};
 
	for(i = 0; i < 8; i++)
		mytree.addNode(numbers[i]);
	mytree.printTree(mytree.getRoot(), level);
	return 0;
}
 
////////////////////////////////////////////////
//methods
 
BSTree::BSTree() 
{//constructor
	 ptr = NULL; // indicates an empty list
} 
 
void BSTree::addNode(int data)
{//adds root to the tree. 
	if(ptr == NULL)
	{
		ptr->data = data;
		ptr->leftChild = NULL;
		ptr->rightChild = NULL;
	}
	else
		findNode(ptr, data);
}
 
void BSTree::findNode(TNODE *ptr, int data)
{//finds where to add the node. Traverse through tree then add the node.
	if ( data < ptr->data )
	{
		findNode(ptr->leftChild, data);
	}
	else if (data > ptr->data)
	{
		findNode(ptr->rightChild, data);
	}
	else if(ptr->data == NULL)
	{
		ptr->data = data;
		ptr->leftChild = NULL;
		ptr->rightChild = NULL;
	}
}
 
void BSTree::printTree(TNODE *ptr, int level)
{//prints out the tree on its side
	if(ptr != NULL)
	{
		printTree(ptr->rightChild, level + 1);
		for(int i = 0; i < 3 * level; i++)
			cout << " ";
		cout << ptr -> data << endl;
		printTree(ptr->leftChild, level + 1);
	}
}
 
TNODE *getRoot(void)
{//returns the root pointer
	return ptr;
}
#include <iostream>
using namespace std;

///////////////////////////////////////////////
// tnode structure
typedef struct tnode
{
	int data;
	struct tnode *leftChild;
	struct tnode *rightChild;
}TNODE;

///////////////////////////////////////////////
//Binary search tree class

class BSTree
{
public:
	BSTree(void);

	void addNode(int data);
	void findNode(TNODE *ptr, int data);
	void printTree(TNODE *ptr, int level);
	TNODE *getRoot(void);
private:
	TNODE* ptr;	
};

///////////////////////////////////////////////
//main

int main()
{
	BSTree mytree;
	int level = 1;

	TNODE* tree;
	int i, numbers[] = {9, 7, 15, 5, 8, 14, 20, 4};

	for(i = 0; i < 8; i++)
		mytree.addNode(numbers[i]);
	mytree.printTree(mytree.getRoot(), level);
	return 0;
}

////////////////////////////////////////////////
//methods

BSTree::BSTree() 
{//constructor
	 ptr = NULL; // indicates an empty list
} 

void BSTree::addNode(int data)
{//adds root to the tree. 
	if(ptr == NULL)
	{
		ptr->data = data;
		ptr->leftChild = NULL;
		ptr->rightChild = NULL;
	}
	else
		findNode(ptr, data);
}

void BSTree::findNode(TNODE *ptr, int data)
{//finds where to add the node. Traverse through tree then add the node.
	if ( data < ptr->data )
	{
		findNode(ptr->leftChild, data);
	}
	else if (data > ptr->data)
	{
		findNode(ptr->rightChild, data);
	}
	else if(ptr->data == NULL)
	{
		ptr->data = data;
		ptr->leftChild = NULL;
		ptr->rightChild = NULL;
	}
}

void BSTree::printTree(TNODE *ptr, int level)
{//prints out the tree on its side
	if(ptr != NULL)
	{
		printTree(ptr->rightChild, level + 1);
		for(int i = 0; i < 3 * level; i++)
			cout << " ";
		cout << ptr -> data << endl;
		printTree(ptr->leftChild, level + 1);
	}
}

TNODE *getRoot(void)
{//returns the root pointer
	return ptr;
}

•

Join Date: Jun 2005

Posts: 2,039

Reputation: Rashakil Fol is just really nice

Solved Threads: 139

Rashakil Fol Rashakil Fol is offline

Offline

Super Senior Demiposter

Re: Binary Search Tree

Mar 28th, 2006

You meant BSTree::getRoot.

All my posts may be redistributed under the GNU Free Documentation License.

•

Join Date: Feb 2005

Posts: 46

Reputation: blackdove is an unknown quantity at this point

Solved Threads: 0

blackdove

Offline

Light Poster

Re: Binary Search Tree

Mar 28th, 2006

Thanks for the help. Atleast it will compile. Now I just need to try and figure out how to get this thing running correctly.

•

Join Date: Dec 2005

Posts: 43

Reputation: Nedals is an unknown quantity at this point

Solved Threads: 0

Nedals

Offline

Light Poster

Re: Binary Search Tree

Mar 29th, 2006

I don't know exactly what your professor gave you, but the code you have is probably not
going to get you where you want to go. You don't really need the 'findNode' or 'getRoot'
functions (methods).

Here's some commented code that should get you started on the right track.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
BSTree::BSTree() 
{
  ptr = NULL; // indicates an empty list
}
BSTree::~BSTree()
{
  // Add a destructor to delete the list on exit
  // otherwise you will end up with a memory leak
}
void BSTree::addNode(int data)
{
  // create a new record (struct)
  // use a *curr for traversing
  if(curr == NULL)
  {
    // List is empty so add the first record (struct). 
  }
  else
  {
    // There are records in list, so traverse according to rules until curr=NULL
    // and insert new record. - exit the loop using a break. 
    while (curr != NULL)
    {
    }
  }
}
BSTree::BSTree() 
{
  ptr = NULL; // indicates an empty list
}
BSTree::~BSTree()
{
  // Add a destructor to delete the list on exit
  // otherwise you will end up with a memory leak
}
void BSTree::addNode(int data)
{
  // create a new record (struct)
  // use a *curr for traversing
  if(curr == NULL)
  {
    // List is empty so add the first record (struct). 
  }
  else
  {
    // There are records in list, so traverse according to rules until curr=NULL
    // and insert new record. - exit the loop using a break. 
    while (curr != NULL)
    {
    }
  }
}

•

Join Date: Sep 2004

Posts: 7,625

Reputation: Narue has a reputation beyond repute

Solved Threads: 716

Narue

Offline

Code Goddess

Re: Binary Search Tree

Mar 29th, 2006

>I don't know exactly what your professor gave you
Probably something akin to bad Java via C++. Professors have a tendency to do that. :rolleyes:

I'm here to prove you wrong.

•

Join Date: Feb 2005

Posts: 46

Reputation: blackdove is an unknown quantity at this point

Solved Threads: 0

blackdove

Offline

Light Poster

Re: Binary Search Tree

Mar 30th, 2006

I finally got it to build a tree using what he gave us. I did, however, end up changing one of his method declarations a bit. This project was just to build the tree. The next one we have to do actually adds on to what we had to do here; adding a destructor, deletion, and traversals. Well this is what I ended up with:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
using namespace std;
 
///////////////////////////////////////////////
// tnode structure
typedef struct tnode
{
	int data;
	struct tnode *leftChild;
	struct tnode *rightChild;
}TNODE;
 
///////////////////////////////////////////////
//Binary search tree class
 
class BSTree
{
public:
	BSTree(void);
 
	void addNode(int data);
	TNODE *findNode(TNODE *ptr, int data);
	void printTree(TNODE *ptr, int level);
	TNODE *getRoot(void);
private:
	TNODE* ptr;	
};
 
///////////////////////////////////////////////
//main
 
int main()
{
	BSTree mytree;
	int level = 1;
 
	TNODE* tree;
	int i, numbers[] = {9, 7, 15, 5, 8, 14, 20, 4};
 
	for(i = 0; i < 8; i++)
		mytree.addNode(numbers[i]);
	mytree.printTree(mytree.getRoot(), level);
	return 0;
}
 
////////////////////////////////////////////////
//methods
 
BSTree::BSTree() 
{//constructor
	ptr = NULL; // indicates an empty list
} 
 
void BSTree::addNode(int data)
{//adds root to the tree. 
	if(ptr == NULL)
	{ 
		TNODE* newnode1 = new TNODE;
		newnode1->data = data;
		newnode1->leftChild = NULL;
		newnode1->rightChild = NULL;
		ptr = newnode1;
	}
	else
		findNode(ptr, data);
}
 
TNODE *BSTree::findNode(TNODE *ptr, int data)
{//finds where to add the node. Traverse through tree then add the node.
 	if(ptr == NULL)
	{ 
		TNODE* newnode1 = new TNODE;
		newnode1->data = data;
		newnode1->leftChild = NULL;
		newnode1->rightChild = NULL;
		ptr = newnode1;
		return ptr;
	}
	else if(data < ptr->data)
	{
		ptr->leftChild = findNode(ptr->leftChild, data);
	}
	else
		ptr->rightChild = findNode(ptr->rightChild, data);
	return ptr;
}
 
void BSTree::printTree(TNODE *ptr, int level)
{//prints out the tree on its side
	if(ptr != NULL)
	{
		printTree(ptr->rightChild, level + 1);
		for(int i = 0; i < 3 * level; i++)
			cout << " ";
		cout << ptr -> data << endl;
		printTree(ptr->leftChild, level + 1);
	}
}
 
TNODE *BSTree::getRoot(void)
{//returns the root pointer
	return (ptr);
}
#include <iostream>
using namespace std;

///////////////////////////////////////////////
// tnode structure
typedef struct tnode
{
	int data;
	struct tnode *leftChild;
	struct tnode *rightChild;
}TNODE;

///////////////////////////////////////////////
//Binary search tree class

class BSTree
{
public:
	BSTree(void);

	void addNode(int data);
	TNODE *findNode(TNODE *ptr, int data);
	void printTree(TNODE *ptr, int level);
	TNODE *getRoot(void);
private:
	TNODE* ptr;	
};

///////////////////////////////////////////////
//main

int main()
{
	BSTree mytree;
	int level = 1;

	TNODE* tree;
	int i, numbers[] = {9, 7, 15, 5, 8, 14, 20, 4};

	for(i = 0; i < 8; i++)
		mytree.addNode(numbers[i]);
	mytree.printTree(mytree.getRoot(), level);
	return 0;
}

////////////////////////////////////////////////
//methods

BSTree::BSTree() 
{//constructor
	ptr = NULL; // indicates an empty list
} 

void BSTree::addNode(int data)
{//adds root to the tree. 
	if(ptr == NULL)
	{ 
		TNODE* newnode1 = new TNODE;
		newnode1->data = data;
		newnode1->leftChild = NULL;
		newnode1->rightChild = NULL;
		ptr = newnode1;
	}
	else
		findNode(ptr, data);
}

TNODE *BSTree::findNode(TNODE *ptr, int data)
{//finds where to add the node. Traverse through tree then add the node.
 	if(ptr == NULL)
	{ 
		TNODE* newnode1 = new TNODE;
		newnode1->data = data;
		newnode1->leftChild = NULL;
		newnode1->rightChild = NULL;
		ptr = newnode1;
		return ptr;
	}
	else if(data < ptr->data)
	{
		ptr->leftChild = findNode(ptr->leftChild, data);
	}
	else
		ptr->rightChild = findNode(ptr->rightChild, data);
	return ptr;
}

void BSTree::printTree(TNODE *ptr, int level)
{//prints out the tree on its side
	if(ptr != NULL)
	{
		printTree(ptr->rightChild, level + 1);
		for(int i = 0; i < 3 * level; i++)
			cout << " ";
		cout << ptr -> data << endl;
		printTree(ptr->leftChild, level + 1);
	}
}

TNODE *BSTree::getRoot(void)
{//returns the root pointer
	return (ptr);
}

•

Join Date: Dec 2005

Posts: 43

Reputation: Nedals is an unknown quantity at this point

Solved Threads: 0

Nedals

Offline

Light Poster

Re: Binary Search Tree

Mar 31st, 2006

Just for my own education in C/C++.

In the above thread, the OP has used recursion to insert an item in the list. (I assume that his 'professor' gave the OP this structure).

Is this an approved method? I generally use a while loop for that type of insertion. It seems to me that the recursion method would be incredibably resource intensive.

Your comments, please.

•

Join Date: Sep 2004

Posts: 7,625

Reputation: Narue has a reputation beyond repute

Solved Threads: 716

Narue

Offline

Code Goddess

Re: Binary Search Tree

Mar 31st, 2006

>Is this an approved method?
It depends on the programmer and the application.

>It seems to me that the recursion method would be incredibably resource intensive.
For a basic binary search tree, it can easily be. If the tree is suitably random then it should be appropriately balanced and recursion won't cause too much trouble. If the tree gets near any of the degenerate cases then the recursion could get too deep for the system to handle, and the application will break.

>Just for my own education in C/C++.
http://www.eternallyconfuzzled.com/tuts/bst1.html

I'm here to prove you wrong.