• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 271
  • Last Modified:

Binary tree, trouble with a simple if statement

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
Your help is appreciated.
0
sdholden28
Asked:
sdholden28
  • 13
  • 9
1 Solution
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi sdholden28,

Just a simple:

   if (node == NULL)

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



Good Luck!
Kent
0
 
sdholden28Author Commented:
I am passing TREE_T **node.
0
 
sdholden28Author Commented:
I also tried your solution anyway, Kdo, no luck
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
sdholden28Author Commented:
I guess what im looking for is what assignment will make

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

a true statement.
0
 
Kent OlsenData Warehouse Architect / DBACommented:
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
 
sdholden28Author Commented:
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
 
Kent OlsenData Warehouse Architect / DBACommented:
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
 
sdholden28Author Commented:
Visual Studio 2005
0
 
sdholden28Author Commented:
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
 
sdholden28Author Commented:
im baffled.
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi sdholden28,

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



Kent
0
 
sdholden28Author Commented:
yes, after
     free(node);
I have
     node = NULL;
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi sdholden28,

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



Kent
0
 
sdholden28Author Commented:
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
 
Kent OlsenData Warehouse Architect / DBACommented:
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
 
sdholden28Author Commented:
that's what i though, but that fails to explain why the NULL test doesn't work.
Would you like entire code?
0
 
Kent OlsenData Warehouse Architect / DBACommented:
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
 
sdholden28Author Commented:
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
 
sdholden28Author Commented:
could you offer some insight as to why this solution worked Kdo?
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Hi sdholden28,

Which solution?

Kent
0
 
sdholden28Author Commented:
the one i posted,

starting with

FOUND IT!!!
0
 
Kent OlsenData Warehouse Architect / DBACommented:
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

Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

  • 13
  • 9
Tackle projects and never again get stuck behind a technical roadblock.
Join Now