Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 691
  • Last Modified:

Binary Search Tree Implementation

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
Paul_ATL
Asked:
Paul_ATL
3 Solutions
 
trinitrotolueneDirector - Software EngineeringCommented:
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
 
sarabandeCommented:
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
 
William SherifCommented:
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

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now