tree problem

[Mike]

Why does this code insert a node into a binary search tree correctly? If I
only inserting going by first digit it works properly but when I try
inserting going by the whole ip and the port number the inserts are totally
out of order.

where
IPAddress is four ints
Node is an IPAddress, portNumber, left pointer and right pointer
Nodeptr is a pointer to a Node

Nodeptr add(Nodeptr tree, IPAddress ip, int portNumber)
{
if(tree==NULL)
{
if((tree = malloc(sizeof(Node)))==NULL )
{
printf("No memory Left\n");
}
else
{
tree->address.digit1 = ip.digit1;
tree->address.digit2 = ip.digit2;
tree->address.digit3 = ip.digit3;
tree->address.digit4 = ip.digit4;
tree->portNo=portNumber;
tree->left = tree->right = NULL;
}
}

else if(ip.digit1 < tree->address.digit1)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit1 >= tree->address.digit1)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit2 < tree->address.digit2)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit2 >= tree->address.digit2)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit3 < tree->address.digit3)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit3 >= tree->address.digit3)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit4 < tree->address.digit4)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit4 >= tree->address.digit4)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(portNumber < tree->portNo)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(portNumber >= tree->portNo)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
return tree;
}

[Flash Gordon]

On Mon, 11 Oct 2004 20:39:52 +1000
"Mike" <mi****@iprimus.com.au> wrote:

Why does this code insert a node into a binary search tree correctly?
If I only inserting going by first digit it works properly but when I
try inserting going by the whole ip and the port number the inserts
are totally out of order.

where
IPAddress is four ints
Node is an IPAddress, portNumber, left pointer and right pointer
Nodeptr is a pointer to a Node
You should have included everything to make this a compilable example
rather than just describing things. Sometimes the error is in the
implementation of the bits described and sometimes we need to compile
and test, so leaving out this information reduces the help people can
provide.
Nodeptr add(Nodeptr tree, IPAddress ip, int portNumber)
I don't like using typedefs for pointers.
{
if(tree==NULL)
{
if((tree = malloc(sizeof(Node)))==NULL )
if((tree = malloc(sizeof *tree))==NULL )
There is less chance of error. Also, it no longer matters if you change
the type of tree.

{
printf("No memory Left\n");
}
else
{
tree->address.digit1 = ip.digit1;
tree->address.digit2 = ip.digit2;
tree->address.digit3 = ip.digit3;
tree->address.digit4 = ip.digit4;
tree->portNo=portNumber;
tree->left = tree->right = NULL;
}
}

else if(ip.digit1 < tree->address.digit1)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
If ip.digit1 is not less than tree->address.digit1 it MUST logically be
greater than or equal to it. So the if below will always test true if it
is reached.
else if(ip.digit1 >= tree->address.digit1)
else if(ip.digit1 > tree->address.digit1)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
So with my change above, it will actually execute the else clause here
when ip.digit1 == tree->address.digit1
else if(ip.digit2 < tree->address.digit2)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
Here we have the same error.
else if(ip.digit2 >= tree->address.digit2)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit3 < tree->address.digit3)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
and again
else if(ip.digit3 >= tree->address.digit3)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit4 < tree->address.digit4)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
and again
else if(ip.digit4 >= tree->address.digit4)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(portNumber < tree->portNo)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
and again
else if(portNumber >= tree->portNo)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
return tree;
}

So this time you were lucky and the error was obvious in the snippet you
provided without compilation.
--
Flash Gordon
Sometimes I think shooting would be far too good for some people.
Although my email address says spam, it is real and I read it.

[Richard Bos]

"Mike" <mi****@iprimus.com.au> wrote:

Why does this code insert a node into a binary search tree correctly? Nodeptr add(Nodeptr tree, IPAddress ip, int portNumber)
{ else if(ip.digit1 < tree->address.digit1)
{
tree->left = add(tree->left, ip,portNumber);
return tree;
}
else if(ip.digit1 >= tree->address.digit1)
{
tree->right = add(tree->right,ip,portNumber);
return tree;
}
else if(ip.digit2 < tree->address.digit2)

You know, this problem sounded strangely familiar. And true enough,
after rummaging through my outbox for a while, I found this:
<http://www.google.com/groups?threadm=414eb9a3_1%40news.iprimus.com.au>

Before looking for answers for homework problems, a little trip to
Google is often enough to prevent being found out.

Richard

[Method Man]

[snip]

I don't like using typedefs for pointers.

I can't stand when someone typedef's a pointer. I see it way too often in
people's code for my liking. It's as if the programmer is going out of
his/her way to make the code obsfucated by disguising the pointer. All just
to save typing a single '*' character.

[Christopher Benson-Manica]

Method Man <a@b.c> spoke thus:

I can't stand when someone typedef's a pointer. I see it way too often in
people's code for my liking. It's as if the programmer is going out of
his/her way to make the code obsfucated by disguising the pointer. All just
to save typing a single '*' character.

At our company, we have

typedef const char *CPCHAR;

Needless to say, I avoid using it like the plague. Unfortunately I'm
the only one who does so...

--
Christopher Benson-Manica | I *should* know what I'm talking about - if I
ataru(at)cyberspace.org | don't, I need to know. Flames welcome.

[CBFalconer]

Christopher Benson-Manica wrote:

Method Man <a@b.c> spoke thus:

I can't stand when someone typedef's a pointer. I see it way too
often in people's code for my liking. It's as if the programmer
is going out of his/her way to make the code obsfucated by
disguising the pointer. All just to save typing a single '*'

character.

At our company, we have

typedef const char *CPCHAR;

Needless to say, I avoid using it like the plague. Unfortunately
I'm the only one who does so...

You might point out it is both ugly and misnamed. It creates a
pointer to a constant char, not a constant pointer to a char.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!