BST inser method seems to be crashing my prog

Hi, i am pretty damned sure i wrote the code for this insert method correctly (maybe not 100%) , but the program crashes when the first word is inserted into the Tree.

insert method being called...

Code:

---

while( inputFile >> word )
{                               
        word += " "; // append space to each word before displaying

        // next character is newline?
        if( inputFile.peek() == '\n' || inputFile.peek() == '\r' )
                word += "\r\n"; // append a 'windows' newline

        textDataDisplay->AppendText( word.c_str() );
                                       
        // remove punctuation from each word
        removePunctFrom( word );
                                       
        bsTree->insertNode( word.c_str() );// insert word into BST
}

---

insert code...

Code:

---

void insertNode( String* data )
{               
        Node* currentNode = EMPTY_NODE; // stores current node
               
        if( treeRoot->isEmpty() ) // is tree empty?
                treeRoot = new Node( data ); // add data as root
        else // tree is not empty
        {
                // see if a node with this data already exists
                currentNode = findNode( data, false );

              // test for duplicate data in tree
                if( currentNode->isEmpty() )
                {
                        currentNode = treeRoot;

                        // traverse tree until we reach an empty node
                        while( !currentNode->isEmpty() )
                        {
                        // data to insert is < data of currentNode
                        if( data->CompareTo( currentNode->data() ) < 0 )
                        {
                                currentNode = currentNode->leftChild();
                        }
                        else // data to insert is > data of currentNode
                        {
                                currentNode = currentNode->rightChild();
                        }
                }
                // store the data in the empty node
                currentNode = new Node( data );
        }
        else // a matching node was found
        {
                errorState = BAD_STATE; // set the state to bad
                return; // return from this function
        }
    }
    errorState = GOOD_STATE; // operation was successful
}// insertNode

---

Any help is GREATLY appreciated, my head is literally hurting me trying to figure out the problem

> bsTree->insertNode
Where do you think bsTree is pointing?

Do you have a constructor for your class, and do you do
bsTree = new bsTree;
?

declaration...

Code:

---

private: BinSearchTree* bsTree;

---

initialization...

Code:

---

public:
Form1(void)
{
        bsTree = new BinSearchTree();
        InitializeComponent();
}

---

BinSearchTree ctors...

Code:

---

BinSearchTree(): treeRoot(EMPTY_NODE), errorState(GOOD_STATE) {}

---

Code:

---

BinSearchTree( Node* root ): treeRoot(root), errorState(GOOD_STATE) {}

---

I might be stating the obvious but if you say the program crashes after you try to insert the first node into the BST, at this point the tree must be empty. So the problem must be in this code:

Code:

---

Node* currentNode = EMPTY_NODE; // stores current node
               
        if( treeRoot->isEmpty() ) // is tree empty?
                treeRoot = new Node( data ); // add data as root

---

How did you define EMPTY_NODE? Or maybe the problem is with the constructor for the Node class...

i #define EMPTY_NODE 0

ctors for Node class...

Code:

---

public:
        Node(): _leftChild(EMPTY_NODE), _rightChild(EMPTY_NODE), _nodeData(String::Empty) {}

---

and

Code:

---

public:
        Node( String* data ):
                _nodeData(data),
                _leftChild(EMPTY_NODE),
                _rightChild(EMPTY_NODE)
        {
        }

---

Could it be becuz i pass word.c_str() to insertNode which receives a System::String* ? I dismissed this becuz char* are assignable to System::Strings.

It could be because of that, yes, since insertNode asks for a String* and you give it a char*. However, I haven't really worked with System::String before so I can't really say.
Also, this line of code looks a bit suspicious to me:

Code:

---

Node* currentNode = EMPTY_NODE; // stores current node

---

You create a Node* and then assign to it an integer value (since you defined EMPTY_NODE as 0). Maybe you could use NULL instead?
The rest of your code looks alright to me. Hope this helps.

Code:

---

if( treeRoot->isEmpty() ) // is tree empty?
                treeRoot = new Node( data ); // add data as root

---

I don't think you can access treeRoot's member functions if you haven't even called new on it yet. Try:

Code:

---

if(!treeRoot)
  treeRoot = new Node( data);

---

oddly enough the !treeRoot doesnt work and i was sure it should have :(.

This is part of an assignment i have to hand in today so i probly won't get it working in time, but thanks for all the help.

> if( treeRoot->isEmpty() ) // is tree empty?
This will indeed crash if the tree is empty.

What do you mean, (!treeRoot) doesn't work? Doesn't it compile? Does it fail at runtime?

okay, !treeRoot did work (my bad). I thought it wasnt but after stepping thru the program with the debugger i realized there was a bit more to it. The way i was inserting the new node was incorrect. I recoded it as:

Code:

---

public:
void insertNode( String* data )
{               
        Node* currentNode; // stores current node we're at
       
        if( !treeRoot )// is tree empty?
                treeRoot = new Node( data ); // simply add the data as the root
        else // tree is not empty
        {
                currentNode = findNode( data, false ); // see if a node with this data already exists

                if( !currentNode )// node with matching data was not found (i.e. no duplicates)
                {
                        Node* parentNode = treeRoot; // start with the parent of the new node at the root

                        if( currentNode != treeRoot ) // current node is not the root?
                                parentNode = findNode( data, true ); // finds the parent of the new node we wish to insert
                               
                        if( data->CompareTo(parentNode->data()) < 0 ) // data to insert < parent's data?
                                parentNode->setLeftChild( new Node( data ) ); // attach node to parent's left subchild
                        else
                                if( data->CompareTo(parentNode->data()) > 0 ) // data to insert > parent's data?
                                        parentNode->setRightChild( new Node( data ) ); // attach node to parent's right subchild
                }
                else // a matching node was found (duplicate data)
                {
                          errorState = BAD_STATE; // set the state to bad
                        return; // return from this function
                }
        }
        errorState = GOOD_STATE; // operation was successful
       
}// insertNode

---

it no longer crashes (YAY!). Thanks so much for the help, i hope others can learn from this and see how it is very easy to miss certain things, especially when working with pointers.

Quote:

---

Originally Posted by CornedBee

> if( treeRoot->isEmpty() ) // is tree empty?
This will indeed crash if the tree is empty.

---

"Thou shalt not follow the NULL pointer, for chaos and madness await thee at its end." -- Henry Spencer.

:D :p

"Undefined behaviour means that anything at all can happen. As far as the specification is concerned, it might even make demons come out of your nose."
-- c.l.c, paraphrased

Quote:

---

Originally Posted by CornedBee

"Undefined behaviour means that anything at all can happen. As far as the specification is concerned, it might even make demons come out of your nose."
-- c.l.c, paraphrased

---

O_O ooookay...