troubleshooting Question

Binary Search Tree Implementation

Avatar of Paul_ATL
Paul_ATL asked on
ProgrammingC++Algorithms
3 Comments3 Solutions1311 ViewsLast Modified:
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;
}

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.
ASKER CERTIFIED SOLUTION
William Sherif

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Join our community to see this answer!
Unlock 3 Answers and 3 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 3 Answers and 3 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros