Binary Search Tree

[blackdove]

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:

#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;
}

[Rashakil Fol]

You meant BSTree::getRoot.

[blackdove]

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

[Nedals]

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.

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)
    {
    }
  }
}

[Narue]

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

[blackdove]

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:

#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);
}

[Nedals]

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.

[Narue]

>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

[Nedals]

Thanks for the link. Bookmarked :)