Solved

Binary Search Tree Implementation

Posted on 2014-11-11
4
432 Views
Last Modified: 2015-02-20
Hello Experts,

I am currently learning how to implement a binary search tree using templates. As part of the learning experience, I am learning to write a program in C++ that will do the following:

1) Read in from a text file
2) Sort the words from the text file into nodes
3) Display the BST once the program finishes sorting through the text file

Below is the code I have written so far.

#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>

template <class T>
class BST
	{
		// Internal Node Structure Class
		struct BSTNode
		{
			T data;
			BSTNode* left;		// Store address of left child node
			BSTNode* right;		// Store address of right child node

			// New Nodes
			// Node will have val assigned to data and empty child nodes
			BSTNode(T val):data(val),left(NULL),right(NULL)
				{

				}	// End Node Constructor
		};	// End Node Structure

		BSTNode* rootPtr;					// Root Node Pointer

		void display(BSTNode*);			// Declare a display method for an individual Node
		void freeMem(BSTNode*);			// Declare a method to be used in the destructor
	
	public:
		BST();							// Constructor
		~BST();							// Destructor
		void insert();					// Insert Method
		void display();					// Display Method
	};	// End BST Class Template

// BST Constructor with the root pointer set to NULL
template <class T>
BST<T>::BST():rootPtr(NULL)
	{

	}	// End BST Method Template

// BST Destructor that will free up memory and remove nodes
template <class T>
BST<T>::~BST()
	{
		freeMem(rootPtr);
	}	// End ~BST Method Template

// FreeMem Method used in the destructor
template <class T>
BST<T>::freeMem(BST::BSTNode *node)
	{
		// Do nothing if the node has nothing
		if(node == NULL)
			{
				return;
			}	// End If Statement

		// Remove the left child node
		if(node->left)
				freeMem(node->left);
		// Remove the right child node
		if(root->right)
				freeMem(node->right);
		delete node;
	}	// End FreeMem Method Template

// Insert Method
template <class T>
void BST<T>::insert()
	{
		Node* node = NULL;

		try
			{
				node = new Node(val);
			}	// End Try Block

		catch(std::bad_alloc &exception)
			{
				std::calloc << "Caught bad_alloc: " << exception.what() << std::endl;				// Display the error message
				EXIT_FAILURE;																		// Terminate the program
			}	// End Catch Block

		Node *temp = NULL;
		Node *prev = NULL;

		temp = rootPtr;		// Assign the rootPtr to temp for insertion algorithm

		// Runs while temp is not NULL
		while(temp)
			{
				prev = temp;																			// Assign temp value to prev

				// Push temp data to the right node
				if(temp->data < node->data)
					{
						temp = temp->right
					}	// End If Statement

				// Push temp data to the left node
				else
					{
						temp = temp->left;
					}	// End Else Statement
			}	// End While Loop

		// Assign the address of a node to rootPtr if there is no previous address stored
		if(prev == NULL)
			{
				rootPtr = node;
			}	// End If Statement

		else
			{
				// Push prev right child node as node value
				if(prev->data < node->data)
					{
						prev->right = node;
					}	// End If Statement

				// Push prev left child node as node value
				else
					{
						prev->left = node;
					}	// End Else Statement
			}	// End Else Statement
	}	// End Insert Method Template

// Display method for an individual node
template <class T>
void BST<T>::display(BSTNode *rootPtr)
	{
		// Display nothing if the rootPtr points to nothing
		if(rootPtr == NULL)
			{
				return;
			}	// End If Statement

		// Print out the node and its child nodes
		print(rootPtr->left);
		std::cout << rootPtr->data << std::endl;
		print(rootPtr->right);

	}	// End Node Display Method Template

// Display method for the entire BST
template <class T>
void BST<T>::display()
	{
		print(rootPtr);
	}	// End Display Method Template


int main(int argc, char argv[])
{
	std::string word;
	std::string line;
	std::ifstream declaration;
	BST <std::string> tree;

	// Read in the text file
	declaration.open("Independence.txt");

	if(declaration.is_open())
		{
			while(declaration >> word)
				{
					tree.insert();
				}	// End While Loop
		}	// End If Statement

	tree.display();

	return 0;
}

Open in new window


For the most part, I think I have a basic understanding as to how the tree will work, but I am having some problems with the coding and do not see where the problem lies. The compiler points me towards an error with an identifier in my freeMem() method. Though I have not been able to run the code for debugging until this issue is resolved, I am also having trouble figuring out if the call to insert in the main function is correct and would like some feedback. Thank you for any help you can provide.
0
Comment
Question by:Paul_ATL
4 Comments
 
LVL 12

Assisted Solution

by:trinitrotoluene
trinitrotoluene earned 167 total points
ID: 40436362
There are several errors in your code least of all the error in freeMem(). That should go away with a proper declaration.
void BST<T>::freeMem(BSTNode *node)

Open in new window



Overall this looks more like a copy paste attempt and I doubt you will be able to compile successfully leave alone debug unless you fix all the other errors in your code.


Here are a few observations

Where is print() defined? Without a definition how can you call the method?
print(rootPtr);

Open in new window


what is Node? I don't see a declaration.
Node* node = NULL;

Open in new window


why are you using calloc to display output?? calloc has a very different use if used the way its intended to be used
std::calloc << "Caught bad_alloc: " << exception.what() << std::endl;				// Display the error message

Open in new window


From a design perspective you should be using a class to encapsulate all info about the tree. I don't see a need to use a separate struct within the class.
0
 
LVL 32

Assisted Solution

by:sarabande
sarabande earned 166 total points
ID: 40439695
I built the code and could resolve all errors (which mostly were already pointed out by trinitrotoluene)

line 52: missing 'void' return type in declaration of function freeMem
 ==> add 'void'
line 52: using incomplete type 'BST::BSTNode' in declaration of function freeMem
 ==> use either 'BST<T>::BSTNode' or only 'BSTNode'
line 64: invalid pointer variable 'root' used
 ==> replace 'root' by 'node'
line 71: missing argument 'T val' for insert function
 ==> add 'T val' as argument (also in declaration line 32)
line 73 - 87: using unknown type Node
 ==> replace Node by BSTNode for all occurrences
line 82: invalid 'std::calloc' used.
 ==> replace by 'std::cout'
line 99:  missing semicolon ; at end of statement.
 ==> add ;
line 142 + line 144 + line 152: unknown function print used.
 == replace print by display

if you do the changes the code builds and works as expected. if you run the program from visual studio ide you should set a breakpoint to return statement of main function to see the output.
 
Sara
0
 

Accepted Solution

by:
William Sherif earned 167 total points
ID: 40510214
You had a couple of errors in your code that caused the compiler to choke. I just reformatted it so it compiles.


#include <iostream>
#include <string>
#include <fstream>
using namespace std;
template <class T>
class BST
{
	// Internal Node Structure Class
	struct BSTNode
	{
		T data;
		BSTNode* left;		// Store address of left child node
		BSTNode* right;		// Store address of right child node

		// New Nodes
		// Node will have val assigned to data and empty child nodes
		BSTNode( T val ) :data( val ), left( NULL ), right( NULL )
		{

		}	// End Node Constructor
	};	// End Node Structure

	BSTNode* rootPtr;					// Root Node Pointer

	void freeMem( BSTNode*node )
	{
		// Do nothing if the node has nothing
		if( node == NULL )
		{
			return;
		}	// End If Statement

		// Remove the left child node
		if( node->left )
			freeMem( node->left );
		// Remove the right child node
		if( rootPtr->right )
			freeMem( node->right );
		delete node;
	}

public:
	BST():rootPtr( NULL )
	{
	}
	~BST()
	{
		freeMem( rootPtr );
	}
	void insert( T val )
	{
		BSTNode* node = NULL;

		try
		{
			node = new BSTNode( val );
		}	// End Try Block

		catch( std::bad_alloc &exception )
		{
			std::cout << "Caught bad_alloc: " << exception.what() << std::endl;				// Display the error message
			EXIT_FAILURE;																		// Terminate the program
		}	// End Catch Block

		BSTNode *temp = NULL;
		BSTNode *prev = NULL;

		temp = rootPtr;		// Assign the rootPtr to temp for insertion algorithm

		// Runs while temp is not NULL
		while( temp )
		{
			prev = temp;																			// Assign temp value to prev

			// Push temp data to the right node
			if( temp->data < node->data )
			{
				temp = temp->right;
			}	// End If Statement

			// Push temp data to the left node
			else
			{
				temp = temp->left;
			}	// End Else Statement
		}	// End While Loop

		// Assign the address of a node to rootPtr if there is no previous address stored
		if( prev == NULL )
		{
			rootPtr = node;
		}	// End If Statement

		else
		{
			// Push prev right child node as node value
			if( prev->data < node->data )
			{
				prev->right = node;
			}	// End If Statement

			// Push prev left child node as node value
			else
			{
				prev->left = node;
			}	// End Else Statement
		}	// End Else Statement
	}

	void print( BSTNode * node )
	{
		cout << node->data << endl;
	}
	
	void display()
	{
		// Display nothing if the rootPtr points to nothing
		if( rootPtr == NULL )
		{
			return;
		}	// End If Statement

		// Print out the node and its child nodes
		print( rootPtr->left );
		std::cout << rootPtr->data << std::endl;
		print( rootPtr->right );
	}
};

int main( int argc, char argv[] )
{
	std::string word;
	std::string line;
	std::ifstream declaration;
	BST <std::string> tree;

	// Read in the text file
	declaration.open( "Independence.txt" );

	if( declaration.is_open() )
	{
		while( declaration >> word )
		{
			tree.insert( word );
		}	// End While Loop
	}	// End If Statement

	tree.display();

	return 0;
}

Open in new window

0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Suggested Solutions

This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
This article will show, step by step, how to integrate R code into a R Sweave document
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

20 Experts available now in Live!

Get 1:1 Help Now