Avatar of Paul_ATL
Paul_ATL
 asked on

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.
C++AlgorithmsProgramming

Avatar of undefined
Last Comment
William Sherif

8/22/2022 - Mon
SOLUTION
trinitrotoluene

Log in or sign up to see answer
Become an EE member today7-DAY FREE TRIAL
Members can start a 7-Day Free trial then enjoy unlimited access to the platform
Sign up - Free for 7 days
or
Learn why we charge membership fees
We get it - no one likes a content blocker. Take one extra minute and find out why we block content.
Not exactly the question you had in mind?
Sign up for an EE membership and get your own personalized solution. With an EE membership, you can ask unlimited troubleshooting, research, or opinion questions.
ask a question
SOLUTION
sarabande

Log in or sign up to see answer
Become an EE member today7-DAY FREE TRIAL
Members can start a 7-Day Free trial then enjoy unlimited access to the platform
Sign up - Free for 7 days
or
Learn why we charge membership fees
We get it - no one likes a content blocker. Take one extra minute and find out why we block content.
Not exactly the question you had in mind?
Sign up for an EE membership and get your own personalized solution. With an EE membership, you can ask unlimited troubleshooting, research, or opinion questions.
ask a question
ASKER CERTIFIED SOLUTION
Log in to continue reading
Log In
Sign up - Free for 7 days
Get an unlimited membership to EE for less than $4 a week.
Unlimited question asking, solutions, articles and more.
Experts Exchange is like having an extremely knowledgeable team sitting and waiting for your call. Couldn't do my job half as well as I do without it!
James Murphy