Thread: Binary Search tree problem

  1. #1
    Registered User
    Join Date
    Jul 2005
    Posts
    3

    Binary Search tree problem

    Hi,

    Am attempting to get this little populate function to work. Currently it populates the first node on either side of the root, but beyond that it will crash.

    Code:
    // this is the struct
    
    struct nodeType
    {
    	int info;
    	nodeType *llink;
    	nodeType *rlink;
    }; 
    
    //this is the constructor for instantiating the tree
    
    cBinaryTree::cBinaryTree(void)
    {
    	root = new nodeType;
    	
    	root->info = 0;
    	root->llink = NULL;
    	root->rlink = NULL;
    }
    
    //this is the for loop in main that sends a random number and the
    //root to the populate() function. theTree is the instantiated class.
    
    for (int i = 0; i < 10; i++)
    	{
    	randomNumber = TOPRAND*rand()/(RAND_MAX + 1);
    	theTree->populate(randomNumber, theTree->root);
    	}
    
    //this is populate
    
    void cBinaryTree::populate(int num, nodeType *p)  //p is root
    {
    	
    	temp = p;                              
    	bool isPlaced = false;  //marker for placement
    
    	while (isPlaced != true)
    		{
    		if (num <= temp->info )
    		{ 
    			if (temp->llink == 0)
    				{
    			nodeType * newNode;
    			newNode = new nodeType;
    			temp->llink = newNode;
    			newNode->info = num;
    			cout<<temp->llink->info;
    			isPlaced = true;
    				}
    				
                                                   else temp = temp->llink;
                                   }
    
    		else
    		{
    			if (temp->rlink == 0)
    				{
    			nodeType * newNode;
    			newNode = new nodeType;
    			temp->rlink = newNode;
    			newNode->info = num;
    			cout<<temp->rlink->info;
    			isPlaced = true;
    				}
    				
                                                  else temp = temp->rlink;
    			}
    		}
    }

    As i mentioned, this code can populate the right and left links of the root - but beyond that I get a crash... I have tried various versions of the above code, but i *think* my issue has to do with the linking of the various nodes.

    Wow, that statement seems obvious, but... there you have it...

    Any and ALL help would be appreciated. I'm certain it's probably something stupid - but I am at a loss...

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    I suspect you will need to explicitly set the rlink and llink pointers to NULL (or 0) for each new nodeType entered into the tree. Without doing so, the addresses rlink and llink contain are random, and will most likely not equate to 0 (or NULL) when you go to evaluate them the next time around, even if they should be NULL by protocol yet (for example the first nodes to root). You do this for root in the constructor, you need to do it for every new node added to the tree.
    You're only born perfect.

  3. #3
    Registered User
    Join Date
    Nov 2002
    Posts
    126
    I could be wrong on this, but I think that because you've declared nodeType as a struct and given it no constructor, the new operator does not know to initialize the left and right pointers to NULL, meaning that you could be dereferencing wild pointers. Try adding a constructor to newNode:
    Code:
    struct nodeType
    {
    	int info;
    	nodeType *llink;
    	nodeType *rlink;
    	
    	//Add this
    	nodeType::nodeType() : left(NULL), right(NULL) {};
    };
    There may also be some other logical problems with the algorithm, I didn't read it over very carefully. Hope that helps.

    BTW: I think scientific studies have proven that Whitesmith indention style does in fact cause brain damage.

  4. #4
    Registered User
    Join Date
    Jul 2005
    Posts
    3
    Thanks folks - that seemed to have solved it to some degree - I certainly now have a populated tree...

    And the identation style was not intentional - i was just trying to make stuff clear and when I did the copy-paste things went insane...

    You guys are life-savers, thanks very, very much...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree - object instantiation problem
    By patricio2626 in forum C++ Programming
    Replies: 3
    Last Post: 11-14-2006, 02:11 AM
  2. binary tree token problem
    By OldSchool in forum C++ Programming
    Replies: 13
    Last Post: 05-28-2006, 10:42 PM
  3. Binary Search Tree
    By penance in forum C Programming
    Replies: 4
    Last Post: 08-05-2005, 05:35 PM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 03:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM