Thread: Binary tree

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    101
    Rep Power
    0

    Binary tree


    Code:
    #include<stdio.h>
    
    typedef struct nums {
    	short value;
    	struct nums *left;
    	struct nums *right;
    } nums;
    
    int main()
    {
    	nums *l;
    	nums *r;
    	nums Ten = {10,NULL,NULL};
    	nums Nine = {9,NULL,NULL},eight = {8,NULL,NULL};
    	nums seven = {7,NULL,NULL},six = {6,NULL,NULL}, five = {5,NULL,NULL},four = {4,NULL,NULL};
    	Ten.left = &Nine;
    	Ten.right = &eight;
    	Nine.left = &seven;
    	Nine.right = &six;
    	eight.left = &five;
    	eight.right = &four;
    	seven.left = &six;
    	seven.right = &five;
    	six.left = &five;
    	six.right = &four;
    	six.left = &four;
    	l = &Nine;
    	r = &eight;
    	do 
    	{
    		printf("%d\n%d\n",l->value,r->value);
    		l = l->left;
    		r = r->right;
    	} while(l->value > 4 || r->value > 4);
    	puts("Countdown success!");
    	getchar();
    	return 0;
    }
    This is how you do a binary tree, correct? Well, if so, is there any easier way to get the pointer values? I was debugging this for so long and I still couldn't be able to achieve my goal of counting down numbers 10 - 4. My best attempt was when it was counting down, but the numbers were counting down together. So it was like 10,10,9,9,8,8,7,7 etc.. this was my final attempt. That's when I couldn't find the bug and became desperate for help. Tell me, where's my problem, how am I able to fix it and is there an easier way to shorten this out? Keep in mind, I want do this with A BINARY TREE
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,891
    Rep Power
    481
    You made this tree, I think:
    Code:
                      10              
              9                8      
           7     6          5     4   
         6   5  4 4                   
        4 4
    With NULL at the unshown leaves.

    It's [edit*]not (see
    dwise1_aol below)[/edit] a binary tree.

    That's not how I make binary trees, nor how I follow them.

    The web site at this eternallyconfuzzled link explains various data structures quite well.


    *I had looked only for loops or cross-links. Not okay to reuse nodes where they only appear as terminals!
    Last edited by b49P23TIvg; March 31st, 2013 at 12:44 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    101
    Rep Power
    0
    Then how do you follow them? I was asking is there a better way to do this because this confuses my head when I try to debug it. I want to see other advantages on how to use Binary trees.
  6. #4
  7. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,172
    Rep Power
    2222
    That is not a binary tree. It starts out as one, but then the third row down goes awry with nodes 7 and 6 pointing over to nodes 6, 5, and 4. Each node is supposed to only have one parent, but 6 has two (9 and 7), 5 has two (8 and 7 -- it was at first 3 parents since six.left was at first set to 5 but then reassigned to point to 4), and 4 has three (8, 6, and 7).

    Also, I cannot see how 10 could ever possibly be visited. Your transiting pointers, l and r, never once point to node 10, but rather to its children, 9 and 8. Here is what I see as the output (by hand):
    9
    8
    7
    4
    6
    <garbage>
    That garbage output will also undoubtedly cause the program to crash, because you trying to dereference a pointer value of NULL, which is what 4's right pointer is set to.

    Here is what I got when I tried to run it:
    C:\otros\dcw>a
    9
    8
    7
    4

    C:\otros\dcw>
    And it crashed as predicted.

    I have no idea how you could have possibly gotten the output that you report, nor can I understand what you're trying to do.

    When I learned Pascal in school (1980), the chapter on pointers or the section on recursion gave an example of using a binary tree as a sort tree and a recursive procedure to traverse through the tree printing everything out in order. For the next two years in school, I used sort trees extensively.

    Here is a quick attempt at a recursive function to traverse a binary tree using your node structure. It goes leftwards as far as possible (ie, until it hits NULL), then tries to go rightwards as far as possible, then returns to its parent. Each node first tries to go to its left child, then prints out its own value, then tries to go to its right child, then returns to its parent. We start with a pointer to the top node. I'm writing this almost completely from memory and have not tested it in any way, but hopefully it will make some sense.

    Code:
    void traverse(nums *p)
    {
        // I think this is mainly useful only to guard against 
        //     the first pointer being NULL
        if (p == NULL)
            return;
    
        // p is valid, so traverse
        traverse(p->left);
        printf("%d\n",p->value);
        traverse(p->right);
    }
  8. #5
  9. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,172
    Rep Power
    2222
    Originally Posted by miz6565
    Then how do you follow them? I was asking is there a better way to do this because this confuses my head when I try to debug it. I want to see other advantages on how to use Binary trees.
    In the example of a sort tree, you want to add or otherwise process an item for the tree, so you traverse the tree looking for where that item would go. If it already exists, you do whatever processing (eg, increment a count, add a line number of where this symbol exists in the code being parsed), but if it does not already exist, then you add it to the tree. Normally in C, you will malloc each node as you add it, but pre-creating a pool of nodes that you can draw from dynamically would also work -- I would recommend creating an array of empty nodes and a counter to index the next node that's free to be added to the tree.

    True, you can put one together by hand has you have attempted to do, but you must be very careful and pay great attention to detail. My suggestion would be to use pencil and paper to graph out the binary tree that you want to create and then use that to write the code to create it.

    But to answer your fundamental question: no, you would not create a useful tree in the manner that you have attempted.
    Last edited by dwise1_aol; March 30th, 2013 at 04:40 PM.

IMN logo majestic logo threadwatch logo seochat tools logo