### Thread: swapping nodes in Binary Trees - in C

Page 1 of 2 12 Last
1. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
11

#### 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```
Last edited by gtpc; May 17th, 2004 at 09:59 AM.
2. 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
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2003
Location
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.
4. 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?
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2003
Location
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 ?
6. 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.
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
11
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.
8. 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,
9. 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.
10. 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

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

93
/    \
/        \
/            \
/                \
/                    \
/                        \
/                            \
75                              97
/    \                          /    \
/        \                      /        \
/            \                  /            \
47              82
/  \            /  \            /  \            /  \
/      \        /      \        /      \        /      \
24      58
/  \    /  \    /  \    /  \    /  \    /  \    /  \    /  \
09  37

Press any key to continue . . .```
11. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
11
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.
12. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
11
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 02:27 PM.
13. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Sep 2003
Location
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.
14. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2003
Location
Posts
228
Rep Power
11
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 04:09 PM.
15. 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
Page 1 of 2 12 Last