I'm having a problem inserting data into my binary search tree, it will insert some of it but not all.
this is the header file for my BST class:
#ifndef BST_H
#define BST_H
//-----------------------------------------------------------------------------------------
#include <string>
#include "LinkedList.h"
//-----------------------------------------------------------------------------------------
using namespace std;
//-----------------------------------------------------------------------------------------
class BST
{
public:
//Default constructor, sets the address of root to NULL
BST ();
//Deconstructor
~BST () {};
//Insert new data into binary search tree
bool Insert (string &word, int docID);
//Find the word passed in as a parameter and copy document list
bool Find (string &word, LinkedList &list);
//friend ostream &operator << (ostream &ostr, BST &BSTree);
private:
struct BSTNode {
string Word; //contains a single word
LinkedList DocList; //a linked list of document IDs
BSTNode *left; //points to the left child
BSTNode *right; //points to the right child
};
BSTNode * root;
//Insert into subtree
bool InsertIntoSubTree(BSTNode &parent, BSTNode &newNode);
};
#endifHere is the .cpp implementation:
#include "BST.h"
BST::BST()
{
root = NULL;
}
//-----------------------------------------------------------------------------------------
// Insert new data into binary search tree
//-----------------------------------------------------------------------------------------
bool BST::Insert(string &word, int docID)
{
BSTNode *newNode = new BSTNode;
bool success = false;
newNode->Word = word;
newNode->DocList.Insert(docID);
newNode->left = NULL;
newNode->right = NULL;
if (root == NULL)
{
root = newNode;
success = true;
cout << "root: " << root->Word << endl;
}
else if (root->Word == word)
{
return false;
}
else
{
success = InsertIntoSubTree(*root, *newNode);
}
return success;
}
//-----------------------------------------------------------------------------------------
// Insert into the BST sub branch
//-----------------------------------------------------------------------------------------
bool BST::InsertIntoSubTree(BSTNode &parent, BSTNode &newNode)
{
bool success = false;
if (newNode.Word < parent.Word)
{
if (parent.left == NULL)
{
parent.left = &newNode;
success = true;
cout << "left: " << parent.Word << endl;
}
else
{
success = InsertIntoSubTree(*parent.left, newNode);
}
}
else
{
if (parent.right == NULL)
{
parent.right = &newNode;
success = true;
cout << "right: " << parent.Word << endl;
}
else
{
success = InsertIntoSubTree(*parent.right, newNode);
}
}
return success;
}
//-----------------------------------------------------------------------------------------
/*ostream &operator << (ostream &ostr, BST &BSTree)
{
//ostr << "The document numbers contained in the list:";
for (BSTNode *ptr = &BSTree.root; ptr-> != NULL; ptr = ptr->left)
{
ostr << ptr.Word;
}
return ostr;
}*/And finally this is what I am trying to do:
// BSTTest.cpp
//--------------------------------------------------------------------
#include "WordStream.h"
#include "BST.h"
//--------------------------------------------------------------------
using namespace std;
//--------------------------------------------------------------------
int main()
{
BST * newBST = new BST;
string filename = "test.txt";
WordStream file(filename);
string word;
while (file.Next(word)) //continuially reads a word from a file until end of file is reached
{
cout << "Input word: " << word << endl; //display what is being inputed
newBST->Insert(word,1);
}
system("pause");
return 0;
}