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
/ /\
b->2 a-> 2- 3
/
3 b->4
/ /
4 5
/ /
5 6
/ /
6 7
/ /
7 8
/ /
8 9
/
9
(1) (2)
1 1
/\ /\
2 3 2 3
/\ /\ /\ /\
a->4 -5- 6 -7 4 5 -6 -7
/\
b->8 8-9
/
9
(3) (4)
1
/\
2 3
/\ /\
4 5 6 7
/\
8 9
(5)
time cost: 2n, O(n)
space cost: 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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
