rainix wrote:
> let level_head_node(i) is the first node of the level i of the
> perfectly balanced BST
>
> ......
> node node_a = level_head_node(i); // get the first node
> of the levle i
> node node_b = level_head_node(i+1); // get the first node of
> the level i+1
> node tail = cursor_a->left; // travel
> the leve i only one step
> unsigned short no_child = 0; // these nodes
> of the level i have their children which belong to the level i+1
>
> // travel all nodes of level i
> // and get their children from level i+1
> // untill no more nodes in the level i+1
> for (i=0; i<2^i; i++)
> {
> node_a->left = node_b;
> node_b = node_b->left;
> if (node_b == NULL)
> {
> no_child = 1;
> break;
> }
> node_a->right = node_b;
> node_b = node_b->left;
> if (node_b == NULL)
> {
> no_child = 1;
> break;
> }
>
> node_a = tail;
> tail = tail->left;
> }
>
> // if ture
> // the remained nodes from the node referred by variable <tail>
> have not any child
> // just break them
> if (no_child == 1)
> {
> while (tail != NULL)
> {
> tail = tail->left;
> node_a->left = NULL;
> }
>
> return 0;
> }
>
> // get the first node of the level i+2
> level_head_node(i+2) = node_b;
>
> .......
a---->1 1 1
1 1
/ /\ /\
/\ /\
b---->2 a----> 2- 3 2 3
2 3 2 3
/ /\ /\
/\ /\ /\ /\
3 b---->4 a---->4 -5 - 6-7
4 5 -6-7 4 5 6 7
/ /
/\ /\
4 5 b---->8
8 -9 8 9
/ / /
5 6 9
/ /
6 7
/ /
7 8
/ /
8 9
/
9
time: 2n, O(n)
space: 3, O(1)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
