Thread: what am I doing wrong?

  1. #1
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85

    what am I doing wrong?

    I am coding a range function for a BST, can some one help me with what I'm doing wrong here?
    Code:
    typedef int data_t;
    typedef struct bnode bstree_t;
    
    struct bnode 
    {
    	data_t data;
    	bstree_t *left; 
    	bstree_t *right;	
    };
    /*aux functions*/
    int cmp (data_t x, data_t y)
    {
    	if (x < y)
    		return-1;
    	else if (x > y)
    		return 1;
    	else
    		return 0;
    }
    
    int within_range (data_t value, data_t low, data_t hi)
    {
    	if (((cmp (value, low)) >= 0) && ((cmp (value, hi)) <= 0))
    		return 1;
    	else
    		return 0;
    }
    /*range function*/
    int in_range (bstree_t *tree, data_t low, data_t hi) 
    {	
    	if (tree == NULL)
    	{
    		return 0;
    	}
    	else
    	{
    		if (within_range (tree->data, low, hi))
    		{
    			int counter = 1;
    			counter += in_range (tree->left, low, hi); 
    			counter += in_range (tree->right, low, hi);
    			return counter;
    		}
    		else 
    		{
    			if (cmp (tree->data,  low) > 0)
    			{
    				in_range (tree->left, low, hi);
    			}
    			else if (cmp (tree->data, hi) < 0)
    			{
    				in_range (tree->right, low, hi);		
    			}
    		}
    	}
    }

  2. #2
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    What do u mean by range, what excatly are u trying to do. I suspect there should be something wrong here

    Code:
    int counter = 1;
    counter += in_range (tree->left, low, hi);
    counter += in_range (tree->right, low, hi);
    return counter;
    ssharish

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    ssharish2005 he has a binary tree full of numbers and wants to count how many of those numbers are in a certain range.

    Although he hasn't stated what is wrong, I can see a definite problem in that some of the results of the recursive calls to in_range are simply being thrown away instead of being returned.

    Turn the compiler's warning level up and pay attention to the warnings. There are some ways of reaching the end of the function without returning a value. The compiler should tell you this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    thats right iMalc, I want to count the nodes from the low value to the hi value in the tree, and the error is:
    Code:
    Enter int values into a BST: 
    0 1 2 3 4 5 6 7 8 9 
    for what range would you like me to count the nodes?: 2 5
    the number of nodes are: 1232307264 for the tree
    0 1 2 3 4 5 6 7 8 9
    sorry about not posting before.

    I'm not sure where to initialize the variable counter, and then where to return it.

    BTW, what flags can i use to turn up the heat on the compiler?
    Last edited by qubit67; 11-19-2007 at 12:39 AM.

  5. #5
    Temporal Apparition qubit67's Avatar
    Join Date
    Jan 2007
    Posts
    85
    and solution:
    Code:
    int within_range (data_t value, data_t low, data_t hi)
    {
    	if (((cmp (value, low)) >= 0) && ((cmp (value, hi)) <= 0))
    		return 1;
    	else
    		return 0;
    }
    
    int in_range (bstree_t *tree, data_t low, data_t hi) 
    {	
    	int count = 0;
    	if (tree == NULL)
    	{
    		return count;
    	}
    	else
    	{
    		if (within_range (tree->data, low, hi))		
    		{		
    		    count = in_range (tree->left, low, hi) + 1
    		    	 + in_range (tree->right, low ,hi);
    		}
    		else 
    		{
    			if (cmp (tree->data, hi) > 0)
    			{
    				return in_range (tree->left, low, hi);
    			}
    			else if (cmp (tree->data, low) < 0)
    			{
    				return in_range (tree->right, low, hi);		
    			}
    		}	
    	}
    	return count;
    }

  6. #6
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    >>BTW, what flags can i use to turn up the heat on the compiler?
    gcc -Wall -W

    ssharish

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by qubit67 View Post
    Code:
    Enter int values into a BST: 
    0 1 2 3 4 5 6 7 8 9
    If you enter the values like that then your tree is probably going to degenerate to a linked-list. Note, I'm assuming it is a plain ordered tree and not a self-balancing tree.
    For a better test, you should try entering the numbers in this order:
    5 2 7 0 3 8 1 4 6 9
    Then test for numbers between various different ranges.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 07-15-2004, 03:30 PM
  2. Debugging-Looking in the wrong places
    By JaWiB in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 11-03-2003, 10:50 PM
  3. Confused: What is wrong with void??
    By Machewy in forum C++ Programming
    Replies: 19
    Last Post: 04-15-2003, 12:40 PM
  4. God
    By datainjector in forum A Brief History of Cprogramming.com
    Replies: 746
    Last Post: 12-22-2002, 12:01 PM
  5. Whats wrong?
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 07-14-2002, 01:04 PM