Solved

Binary tree, trouble with a simple if statement

Posted on 2006-04-26
267 Views
I've set up a binary tree, reading to and from it, sorting etc. My problem is seemingly incredibly simple but I can't figure it out.
In my function tree_add_node i have the following if statement:

if (*node == (TREE_T *)NULL)

The statement allows the function to add a node at the head of the tree, or if theres already one there it proceeds to add either left or right.
First time through this if statement is handled accordingly.

I also have a clear function which resets the tree basically consisting of this:
free(node->left);
free(node->right);
free(node->word);
(I've also tried simply free(node) which should work, but doesn't)

The data from the nodes, words in this case is being cleared, evident in the output window.
However, when I attempt to add more nodes after clearing the first time tree_add_node skips over the
if (*node == (TREE_T *)NULL)
as if its not true. When this happens, no head node is created, and the subsequent attempt to add a node left or right results in an error.
I've also tried in my clear function *node = (TREE_T *)NULL) which i though would certainly work, but it does not fix the problem
0
Question by:sdholden28

LVL 45

Expert Comment

Hi sdholden28,

Just a simple:

if (node == NULL)

should suffice.  Unless you're dealing with TREE_T** structures.

Good Luck!
Kent
0

Author Comment

I am passing TREE_T **node.
0

Author Comment

I also tried your solution anyway, Kdo, no luck
0

Author Comment

I guess what im looking for is what assignment will make

if (*node == (TREE_T *)NULL)

a true statement.
0

LVL 45

Expert Comment

Hi sdholden28,

Most compilers let you test for NULL without recasting.  Either is correct, so just testing for NULL is often easier to read.

If you're passing TREE_T**node, there are a couple of thing to look out for.

1)  If the list is empty (no memory allocated for node), then you'll want to test for (node == NULL).
2)  If the list is non-empty, BUT has no nodes in it, then node will be non-NULL, but (*node == NULL) will be true.

Depending on your implementation, you may need to test for both.

Kent
0

Author Comment

first off, thanks for your help Kdo.

I understand exactly what you are saying, great insight.
However, when I attempt to add (*node == NULL) to my if statements, Im informed that
this is illegal for struct
0

LVL 45

Expert Comment

Hi sdholden28,

Oh, Ok.  :)  You may have to recast the pointer.  What compiler are you using?

Try this:

if ((TREE_T*)(*node) == NULL)

Kent
0

Author Comment

Visual Studio 2005
0

Author Comment

the compiler accepted the recast, but it did not fix the solution.
the if statement is evaluated to be true on first run through, i.e. before any data is entered into struct.
On second run, however, after free(node); has been executed, and all data has been cleared. The if statement evaluates to false.
0

Author Comment

im baffled.
0

LVL 45

Accepted Solution

Hi sdholden28,

After all of the data is cleared, do you reset node = NULL?

Kent
0

Author Comment

yes, after
free(node);
I have
node = NULL;
0

LVL 45

Expert Comment

Hi sdholden28,

Then the test for NULL should work.  How big is your code?

Kent
0

Author Comment

After my clear command, this is what is left in my structure.

-            node      0x00417178 _top      tree_struct * *
-                  0x00362650 {word=0x00362650 "Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾ " left=0xfeeefeee right=0xfeeefeee }      tree_struct *
+            word      0x00362650 "Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾Ã®Ã¾ "      char [16]
+            left      0xfeeefeee {word=0xfeeefeee <Bad Ptr> left=??? right=??? }      tree_struct *
+            right      0xfeeefeee {word=0xfeeefeee <Bad Ptr> left=??? right=??? }      tree_struct *

you'll notice that node->word is not equal to NULL, despite the free command and node = NULL.
I believe this is the problem. How do I get node->word equal to NULL?
0

LVL 45

Expert Comment

Hi sdholden28,

Your structure doesn't matter.  If you called free() to release the memory, then whatever is/was in the structure is considered void.  You don't have a real pointer to the structure anymore so the memory contents are meaningless.

Kent
0

Author Comment

that's what i though, but that fails to explain why the NULL test doesn't work.
Would you like entire code?
0

LVL 45

Expert Comment

Hi sdholden28,

Sure.  I'll look at the code.  But consider this:

TREE_T  *MyTree;

MyTree = (TREE_T *) malloc (sizeof (TREE_T));
MyTree->word = Something;
MyTree->left = (TREE_T *) malloc (sizeof (TREE_T));
MyTree->right = (TREE_T *) malloc (sizeof (TREE_T));

free (MyTree->left);
free (MyTree->right);
free (MyTree);
MyTree = NULL;

At this point we have no valid points into the tree.  Even if we saved the old pointer, the value is meaningless because any function that we call may get that same block of memory allocated at the next call to malloc().

Kent
0

Author Comment

FOUND IT!!!

In tree_add_node i was passing **node and using *node for the NULL test

In tree_clear I was passing *node and using free(node);
Passing **node to tree_clear and using free(**node) has solved the problem.

Thanks so much Kdo, your direction allowed me to find a solution. You will be awarded the points.
0

Author Comment

could you offer some insight as to why this solution worked Kdo?
0

LVL 45

Expert Comment

Hi sdholden28,

Which solution?

Kent
0

Author Comment

the one i posted,

starting with

FOUND IT!!!
0

LVL 45

Expert Comment

Hi sdholden28,

Ah.  Ok.

Some compilers treat pointers as pointers.  The levels of indirection (number of asterisks) are ignored so a **node is considered a valid parameter when a function expects *node.  Similarly *node is legal when ** node is expected.

The problem with that simplistic approach is that your function is usually written so that the function expects a pointer to an object or a pointer to a pointer to an object.  They are NOT interchangable.  To my way of thinking, it's a compiler bug.  But it may also be that one of the compiler switches enables/disables this kind of loose interpretation of pointers.

I can easily see a program where you pass a pointer and the first byte at the passed address identifies what was passed.  You'd then recast the passed address to a particular structure.  But I would expect that the parameter type would be void* in the function header, not a specific structure type.

Kent
0

Featured Post

Suggested Solutions

Workplace bullying has increased with the use of email and social media. Retain evidence of this with email archiving to protect your employees.
In our personal lives, we have well-designed consumer apps to delight us and make even the most complex transactions simple. Many enterprise applications, however, are a bit behind the times. For an enterprise app to be successful in today's tech woâ€¦
This video demonstrates basic masking and how to edit the mask to reveal the desired image.
This video will demonstrate how to find the puppet warp tool from the edit menu and where to put the points to edit.