-
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);
}
}
}
}
-
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
-
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.
-
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?
-
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;
}
-
>>BTW, what flags can i use to turn up the heat on the compiler?
gcc -Wall -W
ssharish
-
Quote:
Originally Posted by
qubit67
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.