Thread: BST inser method seems to be crashing my prog

  1. #1
    Registered User
    Join Date
    Jul 2004
    Posts
    8

    Question BST insert 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
    Last edited by ray_broome; 04-21-2005 at 10:20 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > bsTree->insertNode
    Where do you think bsTree is pointing?

    Do you have a constructor for your class, and do you do
    bsTree = new bsTree;
    ?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jul 2004
    Posts
    8
    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) {}
    Last edited by ray_broome; 04-21-2005 at 11:33 AM.

  4. #4
    Registered User
    Join Date
    Apr 2005
    Posts
    22
    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...

  5. #5
    Registered User
    Join Date
    Jul 2004
    Posts
    8
    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.

  6. #6
    Registered User
    Join Date
    Apr 2005
    Posts
    22
    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.

  7. #7
    carry on JaWiB's Avatar
    Join Date
    Feb 2003
    Location
    Seattle, WA
    Posts
    1,972
    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);
    "Think not but that I know these things; or think
    I know them not: not therefore am I short
    Of knowing what I ought."
    -John Milton, Paradise Regained (1671)

    "Work hard and it might happen."
    -XSquared

  8. #8
    Registered User
    Join Date
    Jul 2004
    Posts
    8
    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.

  9. #9
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    > 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?
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  10. #10
    Registered User
    Join Date
    Jul 2004
    Posts
    8
    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.
    Last edited by ray_broome; 04-22-2005 at 08:31 AM.

  11. #11
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    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.

    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    "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
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #13
    Registered User
    Join Date
    Jul 2004
    Posts
    8
    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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. need help program crashing
    By tunerfreak in forum C++ Programming
    Replies: 14
    Last Post: 05-22-2006, 11:29 AM
  2. How do I stop cin from crashing my prog
    By Panopticon in forum C++ Programming
    Replies: 10
    Last Post: 12-13-2004, 03:41 PM
  3. why is this prog crashing on delete?
    By Waldo2k2 in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 11:17 PM
  4. Crashing on prog quit
    By Hunter2 in forum Game Programming
    Replies: 11
    Last Post: 09-07-2002, 12:13 PM
  5. sprintf crashing my prog?
    By Eber Kain in forum C++ Programming
    Replies: 11
    Last Post: 11-21-2001, 04:25 AM