Help with binary search tree insertion

[noxee]

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);
};
#endif

Here 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;
}

[iamthwee]

What's wordstream.h linkedlist.h?

Please label which one is which for clarity

[~s.o.s~]

What's wordstream.h linkedlist.h?

Please label which one is which for clarity

I think he hasn't posted those files.

[noxee]

What's wordstream.h linkedlist.h?

Please label which one is which for clarity

I haven't included them in the post, they aren't really relevant to the problem. All WordStream.h does is read in a word from a specified file source and it works fine, I've all ready tested it. LinkedList.h just generates and linked list from a given integer, again this works fine and doesn't really have and relevance to the insertion problem

[noxee]

Disregard all the above.... it was working fine i was just outputting the wrong thing when i was testing...:confused: