Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12

    swapping nodes in Binary Trees - in C


    I am now trying to write a program that deletes the root node of a binary
    tree and replace the root node with the right-most leaf node. I tried this
    using inorder traversal, but couldn't get it. Then I thought, maybe I am
    supposed to create an array from the tree. Swap the data in the array, then
    recreate the new binary tree. Am I right? OR is there a way I should be able
    to swap the elements while in the tree?
    I attached the basic program for your use. The 'replace_root()' function
    is not at all done in it...

    example:
    Code:
    from... this:
              a
            /  \
          b     c
        /  \   /  
      d    e f    
    
    to.... this
              f
            /  \
          b     c
        /  \   
      d    e
    Attached Files
    Last edited by gtpc; May 17th, 2004 at 10:59 AM.
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2003
    Location
    Houston, TX
    Posts
    161
    Rep Power
    11
    If you no longer need node a at all and you just need node f in the a position, why can't you just copy the information from node f into the a position, or simpler yet, just copy the next* from a to f. Since it is the next* which really determine where in the list a node is.
    Are you looking for a way to do this one time or for a function that will swap any two nodes during runtime?
    -Tim
    Avalokiteshvara Bodhisattva, when practicing deeply the Prajna Paramita, perceives that all five skhandas in their own being are empty and is saved from all suffering.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2003
    Location
    Montreal, Canada
    Posts
    486
    Rep Power
    12
    I think your little graph is making sense

    don't know why you wnat to do this but it's making sense.

    cause the C will necessarly be at right of the f nodes cause it's bigger. The B is smaller than F so needs to be at left. the only problems I could see with this, are the nodes under, cause they could have been smaller than A and bigger than B but could they bigger than B and bigger than F, that mean they would need to be on the right ?

    i dunno.
  6. #4
  7. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    It doesn't make sense to me, Bob, because it blows the orderliness of the tree. You'd also have to find the leaf by looking a level ahead, because without reverse links, you have to adjust the right-most leaf's parent's pointers to make it a leaf. On the other hand, if the order is preserved, that's by definition a totally unbalanced tree, because the largest value is now the root. Is there a goal (or a future operation based on this) expressed in the problem?
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2003
    Location
    Montreal, Canada
    Posts
    486
    Rep Power
    12
    dawai : won't be unbalaced, cause it's not the biggest value that is set as the root, soo won't be like a list, but it will still look weird.

    You should try searching abour Red Binary trees or other type of trees. Some class have been made already where you could swap part of the tree to somewhere else, and it would balance the tree at the same time.
    Might consider checking that out.

    But can you tell us exactly what you are trying to do ?
  10. #6
  11. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    Watever, if you take the largest value in the tree and make it the root and keep the tree in order, the tree is unbalanced.

    Bob is studying 'C' (not C++) on his own and is working assignments as per their specifications. His freedom of choice is thereby somewhat limited.
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12
    I don't have any idea of an application beyond getting this question
    answered. The tree no longer has to have lesser and greater sides. This one
    is just a binary tree with random chars from my own array. The next
    question has a part 3 that will ask me to exchange the right-most leaf for
    the root. So I guess they want me to form the code at this point.
    I tried to write some find-replace code for it, but the inorder traversal put me
    back at the root for some reason, not at the last leaf node. I will try to put
    the function together as best I can and post it later. Thanks guys.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2004
    Posts
    23
    Rep Power
    0
    I'm assuming the node memory structure looks like this

    Code:
    Struct Node 
    {
         char Item;
         Node * Right, *Left;
    }
    if it does then first off find the leaf node. put the value in a temp variable and delete that node from the parent. place the temp variable into the root item. the root node has already been allocated no reason to delete it and adjust 3 pointers when you can delete the leaf and adjust only one pointer

    One way to check is to do a reverse preorder traversal, that is, you traverse right before you traverse left but at each node you check to make sure that the next node visited is NOT a leaf. if it is a leaf the first leaf you come to will be the right most leaf. access its Item and delete it there,
  16. #9
  17. Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Apr 2004
    Location
    Frostbite capital of the world
    Posts
    542
    Rep Power
    11
    If you are trying to switch the left most(smallest) item on the right side with the root, it shouldn't be too big of a problem.
    Just set f's children to be the same as a's children. Then set f's parent->left to null. Then delete the node at the root, (just the one not the children) and reset the pointer to the root to point at f.
  18. #10
  19. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    Bob, here's some output using my tree displayer. Note that if you merely replace the root with the rightmost (greatest) node, the tree, while it's still a binary tree, will be 'broken' as a binary SEARCH tree. The second output is of the same data inserted in descending order. The insertion procedure, which prevents the formation of a degenerate tree (linked list) has prevented a TOTAL imbalance, but I think it's safe to say it isn't a balanced tree.
    Code:
    Insertion order
    37     09     93     24     82     97     58     75     47
    Insertion
    37     09     93     24     75     97     58     82     47
    Traverse:
    09     24     37     47     58     75     82     93     97
    
    
    Breadth-first by level:
                                    37
                                  /    \
                                /        \
                              /            \
                            /                \
                          /                    \
                        /                        \
                      /                            \
                    09                              93
                  /    \                          /    \
                /        \                      /        \
              /            \                  /            \
                            24              75              97
           /  \            /  \            /  \            /  \
         /      \        /      \        /      \        /      \
                                        58      82
       /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \
                                      47
    
    Press any key to continue . . .
    
    Insertion order
    97     93     82     75     58     47     37     24     09
    Insertion
    93     75     97     47     82     24     58     09     37
    Traverse:
    09     24     37     47     58     75     82     93     97
    
    
    Breadth-first by level:
                                    93
                                  /    \
                                /        \
                              /            \
                            /                \
                          /                    \
                        /                        \
                      /                            \
                    75                              97
                  /    \                          /    \
                /        \                      /        \
              /            \                  /            \
            47              82
           /  \            /  \            /  \            /  \
         /      \        /      \        /      \        /      \
        24      58
       /  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \
      09  37
    
    Press any key to continue . . .
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12
    WHY is it 'broken'? perhaps I am missing an important point here. Help me
    out? But the way I am looking at this, remember that it is NOT part of the
    earlier question and is no longer an ordered binary tree, but is random AND
    we are inserting chars. Left is no longer 'lesser' is it? The right-most leaf is
    not greater is it?
    The part I was battling with was traversing through in order to find the last
    leaf node in order to use it and delete it. When I print 'inorder' it does print
    the last one fine, but when I try to use 'scanf' to copy the leaf to temp, it
    copies a '@', which I assume is one of several returns after the last leaf
    node, or an 'a', which is the root node.
    By the way, I like your tree displaying code.
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12
    Here is an attempt to do what I want. It works, but not exactly. It does
    swap the root node, but does not swap the right one, or something. IT
    starts by printing inorder traversal 'h d i b j e b a l b m c n g o' and after the
    swap it prints 'h d i b j e b b l b m c n g o'. The 'o' is still at the end and
    should be the new root!!!!!

    Code:
    /* Write a program that deletes the root node of a binary tree
       and replaces the root node with the right-most leaf node */
    
    #include <assert.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef  char  DATA;
    
    struct node {
       DATA		d;
       struct node	*left;
       struct node	*right;
    };
    
    typedef struct node NODE;
    typedef NODE	    *BTREE;
    
    void inorder(BTREE root);
    BTREE new_node();
    BTREE init_node(DATA d1, BTREE p1, BTREE p2);
    BTREE create_tree(DATA a[], int i, int size);
    int  count_nodes(BTREE root, int cnt);
    BTREE replace_root(BTREE parent, BTREE root);
    
    int main(void)
    {
       int i = 0;
       BTREE b_tree;
       char array_of_chars[] = {"abcdebghijblmno"};
    
       b_tree = (create_tree(array_of_chars, i, 15));
       printf("inorder traversal: ");
       inorder (b_tree);
          putchar('\n');
       printf("Number of nodes = %d\n", count_nodes(b_tree, 0));
       b_tree = replace_root(b_tree, b_tree);
       printf("After right-most leaf node replaces root...\n");
       printf("Inorder traversal: ");
       inorder (b_tree);
       putchar('\n');
       return 0;
    }
    
    /* replace root node with data of right-most leaf node */
    BTREE replace_root(BTREE parent, BTREE root)
    {
       char lastChar;
    
       if (parent != NULL)
       {
          replace_root(parent->right, root);
          if (parent->left != NULL)   /* in case there is a leaf node on left */
          {
             parent = parent->left;
          }
    	 root = init_node(parent->d, root->left, root->right);
       }
       return root;
    }
    
    /* inorder, preorder, and postorder binary tree traversal */
    void inorder(BTREE root)
    {
       if (root != NULL) {
          inorder(root->left);  /* recur left */
          printf("%c ", root->d);
          inorder(root->right); /* recur right */
       }
    }
    
    /* creating binary trees */
    BTREE new_node()
    {
       return (malloc(sizeof(NODE)));
    }
    
    BTREE init_node(DATA d1, BTREE p1, BTREE p2)
    {
       BTREE t;
       t = new_node();
       t->d = d1;
       t->left = p1;
       t->right = p2;
       return t;
    }
    
    /* create a binary tree from an array */
    BTREE create_tree(DATA a[], int i, int size)
    {
       if (i >= size)
          return NULL;
       else
          return (init_node(a[i],
                  create_tree(a, 2*i+1, size),
    	      create_tree(a, 2*i+2, size)));
    }
    
    int  count_nodes(BTREE root, int cnt)
    {
       if (root != NULL) {
          cnt = count_nodes(root->left, cnt);  /* recur left */
          cnt = count_nodes(root->right, ++cnt); /* recur right */
       }
       return cnt;
    }
    Last edited by gtpc; May 18th, 2004 at 03:27 PM.
  24. #13
  25. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2003
    Location
    Montreal, Canada
    Posts
    486
    Rep Power
    12
    Originally Posted by DaWei_M
    Watever, if you take the largest value in the tree and make it the root and keep the tree in order, the tree is unbalanced.
    true

    but if you check his exemple, he isn't taking the largest value cause C is larger than F.

    but the tree, will be weird and in MANY MANY case won't be balanced. It's pretty rare it will be balanced.

    sorry, i didn't know he was trying to learn by himself. But sometimes you learn by exemple from other :p ! soo that's why, red binary tree might help to see how they implemented it.
  26. #14
  27. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2003
    Location
    Canada
    Posts
    228
    Rep Power
    12
    HEY Watever! Don't apologize. I will take all the help I can get. DaWai has
    been a 'God-send' for me. Even when he or someone else gives me 'too
    much' help, or a chunk of the solution, I study it until I really understand. I
    have been on chapter 10 in my book for months, believe me, it is wearing.
    Last edited by gtpc; May 18th, 2004 at 05:09 PM.
  28. #15
  29. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3314
    I haven't looked at it yet, but I shall. Remember that when you find the rightmost (for 'greatest') node, you either have to deal with it immediately (relink it) or take its pointer all the way back out the 'unwind', preserving it throughout, and relinking it afterwards. To deal with it when you find it, you have to have the root available too, so it either has to be global or you have to carry it with you (passing it as an argument) during the locate process.

    A binary search tree is built so that you can enter at the root, make a comparison, and immediately reject half the tree as not containing your target value. With each comparison and branch in the appropriate direction, you reject half of the remaining part of the tree. If you look at your insertion procedure you will notice that it is a search for the value nearest to the one you want to insert. When you find it, you place the new value accordingly. If the tree is not in order, the search won't work. The in-order traversal and all other operations rely upon the original construction being intact. To find the largest value, for instance, you just take every right-hand branch until you run out of real estate. If someone unilaterally moves the largest value to the leftmost position, you won't find it. Consequently, I'm guessing that if you just hack and transplant some node, they're going to ask you to reconstitute the tree. It could very well be, however, that they are just teaching you to find a node and relink it. The fact that the tree is then worthless (as a search tree) is beside the point; you just trash it and move to the next assignment with the find (carrying or returning info)/prune/relink skill in hand.

    The tree display was a hassle, trying to calculate on the fly how I could maximize the use of available real estate without overlapping 'hives'. I finally said to heck with it, built a 2D character matrix, and just dump the results of the breadth-first traversal in fixed positions. Of course, I have to completely fill out the tree with dummy nodes after it's constructed in order to know what locations to skip to maintain alignment. I'll zip it up and attach it to the next post. It's limited to 5 levels because of screen width; anything over just prints below without formatting. It actually looks better on the screen than in the post, because the slashes are more in alignment. Font, I guess. It helps me to visualize what's going on when I try different insertions. I even thought about making a slow moving applet so I could watch it juggle things to avoid the degenerate tree form. But then I'm weird! Regards,

    David
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
    DaWei on Pointers Politically Incorrect.
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo