Binary Tree

This is a discussion on Binary Tree within the C Programming forums, part of the General Programming Boards category; I coded a binary tree with basic functions: insert, display, search and clear. The clear() function isn't working properly. I ...

  1. #1
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312

    Binary Tree

    I coded a binary tree with basic functions: insert, display, search and clear. The clear() function isn't working properly. I want to delete all the nodes. So I modified the display function:

    Code:
    // header files
    
    struct tree
    {
    	int dat;
    	struct tree *left, *right;
    } *root, *temp;
    
    void display(struct tree *n)
    {
    	if(n->left) display(n->left);
    	printf("%d\n", n->dat);
    	if(n->right) display(n->right);
    }
    
    // Other functions
    
    void clear(struct tree *n)
    {
    	if(n->left) clear(n->left);
    	free(n);
    	if(n->right) clear(n->right);
    	n->left = NULL;
    	n->right = NULL;
    }
    I remove the nodes in sort order (small -> big numbers). After I cleared the tree, I display() the tree again. It prints 1 rubbish number. Though the n->right and n->left should be NULL. I know the clear() function is wrong, but I don't know how to clear the tree properly.
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    That's because your "top" (root) node is not set to NULL - so when you traverse the tree, it finds one node.

    Code:
    void clear(struct tree *n)
    {
    	if(n->left) clear(n->left);
    	free(n);
    	if(n->right) clear(n->right);
    	n->left = NULL;
    	n->right = NULL;
    }
    Also, the code is "broken" in the fact that you use the data pointed to by n after it's been freed - which is bad, since there is absolutely no guarantee that it's going to contain valid data. Try using a macro like this:
    Code:
    #define free(x) do { memset(x, 0xD4, sizeof(*x)); free(x); } while(0)
    EDIT: Corrected te order of memset arguments.

    and it will crash when you do the above. If your code was multithreaded, there's no guarantee that another thread will not "grab" the memory you just freed and use it for other purposes, before you have deleted the rest of the tree - particularly if the tree as thousands of entries.

    You need to free it LAST, after you have traversed the nodes below this point.

    You probably want to pass in a pointer to pointer to tree, so that you can update the actual pointer to NULL - and then you don't have to set the left/right pointers to NULL separately, which makes the code a bit simpler.

    --
    Mats
    Last edited by matsp; 10-25-2007 at 08:56 AM. Reason: Fix incorrect order of arguments.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    Is this solution good too?

    Code:
    void delNodes(struct tree *n)
    {
    	if(n->left) delNodes(n->left);
    	n->left = NULL;
    	n->right = NULL;
    	free(n);
    	if(n->right) delNodes(n->right);
    	
    }
    
    void clear(struct tree *n)
    {
    	delNodes(n);
    	temp->left = temp->right = NULL;
    	free(temp);
    	root->left = root->right = NULL;
    	free(root);
    	root = temp = NULL;
    }
    You probably want to pass in a pointer to pointer to tree, so that you can update the actual pointer to NULL - and then you don't have to set the left/right pointers to NULL separately, which makes the code a bit simpler.
    I don't know what you mean with this? Pointer to a pointer, so

    Code:
    struct tree **tempPtr = &n;
    But how do I set the right and left pointers to NULL with **tempPtr?
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    void delNodes(struct tree *n)
    {
    	if(n->left) delNodes(n->left);
    	n->left = NULL;
    	n->right = NULL;
    	free(n);
    	if(n->right) delNodes(n->right);
    	
    }
    Still uses n->something after free and n->right is now NULL when you go to delete it - so it will not delete it.

    I don't think you need to split the function [although it's a viable solution], but rather just pass in struct tree **n and do "*n = NULL" just after free(*n); Before you do any of that, of course, delete (recursively) your left and right tree nodes.

    Add the macro I posted in the previous post, and you will definitely see if you use after free.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    Using the macro I see the error now, but when I use your solution (instead of splitting the task into two functions) I get a segfault. I don't get this segfault when I split the task into two functions.

    Code:
    void delNodes(struct tree **n)
    {
    	if((*n)->left) delNodes((*n)->left);
    	
    	if((*n)->right) delNodes((*n)->right);
    	
    	(*n)->left = NULL;
    	(*n)->right = NULL;
    	free(*n);
    	*n = NULL;
    	printf("free\n");
    }
    And I don't understand why I can't just use struct tree *n instead of struct tree **n in this function?
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,659
    > delNodes((*n)->left);
    Do you get any warnings?

    It would seem to me to be
    delNodes( &((*n)->left) );
    given the new prototype of the function.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
    	if((*n)->left) delNodes(&(*n)->left);
    	
    	if((*n)->right) delNodes(&(*n)->right);
    I don't think you are compiling your code with Warnings enabled in the compiler. That would spot the above problem.

    If you want to simplify your code, you couold use something like this:
    Code:
    void delNodes(struct tree **pn)
    {
       struct tree *n = *pn;
    
       if (n->right) delNodes(&n->right);
       ...  // More code goes here. 
       free(n);
       *pn = NULL;
    }
    You only need the double pointer to be able to set the "incoming" pointer to NULL.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    Oh I see now . One last question about this: Why does the following 'delNodes' function segfault? Is it because you make *n NULL and use it afterwards (instead of making *n NULL and using **n)?

    Code:
    void delNodes(struct tree *n)
    {
    	if(n->left) delNodes(n->left);
    	
    	if(n->right) delNodes(n->right);
    	
    	n->left = NULL;
    	n->right = NULL;
    	free(n);
    	n = NULL;
    	printf("free\n");
    }
    EDIT: oh, you were faster, (I was thinking and trying very long). Thanks for the help!
    Last edited by Ideswa; 10-25-2007 at 10:17 AM. Reason: Correct superfluous post
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    No, it is because you are passing in the wrong address &(*n)->right is not the same value as (*n)->right, so you are trying to look at "->right" on something that isn't a pointer to pointer to a tree - which will be the wrong memory location and thus seg-fault.

    Use -Wall on the compiler, and it will tell you when you pass the wrong type of pointer - C as a language is quite flexible with what pointers mean and point to, but enabling warnings will give you a warning when the compiler thinks "this doesn't look quite like I expected". [99% of the time, the compiler is right, and in the case where it isn't, you probably should use a cast - but it's more likely that you made a mistake].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    I already use -Wall. When I use

    Code:
    void delNodes(struct tree *n)
    {
    	if(n->left) delNodes(n->left);
    	
    	if(n->right) delNodes(n->right);
    	
    	n->left = NULL;
    	n->right = NULL;
    	free(n);
    	n = NULL;
    	printf("free\n");
    }
    it doesn't give any warnings... though it segfaults...
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  11. #11
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    delNodes segfaults, or the display code segfaults?

    I don't see anything that would make it segfault, but root will still point to something bad when delNodes is finished - whcih is why you need to pass a pointer to pointer.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #12
    C / C++
    Join Date
    Jan 2006
    Location
    The Netherlands
    Posts
    312
    display() segfaults. When I set root = NULL after delNodes() it doesn't segfault anymore. So the pointer to pointer solution is more efficient. Thanks again .

    But when delNodes() returns a struct tree * and it always returns NULL, and when I return NULL to the root pointer in the main function, the problem is solved.
    Last edited by Ideswa; 10-25-2007 at 10:38 AM. Reason: addition
    Operating Systems:
    - Ubuntu 9.04
    - XP

    Compiler: gcc

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Here's what's wrong with it:
    There should only be one if-statement, and it should only be checking n.
    setting n->left or n->right to NULL is a waste of time.
    It should be taking a pointer-pointer, or returning a pointer.
    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: 0
    Last Post: 11-04-2006, 10:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21