tree to single linked list conversion

Hi Everyone,

I was working to convert a binary search tree into a singly linked

list, so that i get a sorted singly linked list too, and this is the

logic...

root = single_r(root,NULL); // Caller invokes in this manner...

static node* gresult; // Global pointer used to hold

the new root.

struct node * single_r(struct node* root, struct node* parent)

{

static int flag = 0;

if(root == NULL)

return root;

if(root->lptr != NULL)

{

root = clockwise_rotation(root,parent);

}

else

{

if(flag == 0)

{

gresult = root;

flag = 1;

}

parent = root;

root = root->rptr;

}

single_r(root,parent);

return gresult;

}

struct node * clockwise_rotation(struct node * root,struct node *

parent)

{

struct node * temp_root;

if(root == NULL)

return NULL;

if(root->lptr == NULL)

return root;

temp_root = root->lptr;

root->lptr = temp_root->rptr;

temp_root->rptr = root;

if(parent != NULL)

{

parent->rptr = temp_root;

}

return temp_root;

}

I keep on rotating the left child of the current node and make it as

a new root node. I keep repeating this until there isn't any left

childs. Now i repeat this for the right child and so on...

But the problem is that i have to return the new root node to the

caller and currently i'm using a static flag to serve this purpose.

But i want to avoid this as this doesn't fit well in multi-threaded

applications. Is there any way to solve without using static variables

and global variables and without iterations?

Thanks in advance ! ! !

Re: tree to single linked list conversion

Rahul <sam_cit@yahoo.co.in> writes:[color=blue]

>Hi Everyone,

>

> I was working to convert a binary search tree into a singly linked

>list, so that i get a sorted singly linked list too, and this is the

>logic...[/color]

[color=blue]

>Thanks in advance ! ! ![/color]

Do a google search on recursion. Look for algorithms for pre-order,

in-order and post-order tree walkers.

scott

Re: tree to single linked list conversion

On May 2, 10:48 pm, sc...@slp53.sl.home (Scott Lurndal) wrote:[color=blue]

> Rahul <sam_...@yahoo.co.in> writes:[color=green]

> >Hi Everyone,[/color]

>[color=green]

> > I was working to convert a binary search tree into a singly linked

> >list, so that i get a sorted singly linked list too, and this is the

> >logic...

> >Thanks in advance ! ! ![/color]

>

> Do a google search on recursion. Look for algorithms for pre-order,

> in-order and post-order tree walkers.

>

> scott[/color]

I knew that an inorder traversal of binary search tree would give me

the sorted list... but i can't change the links in them...

I wanted to have an in-place sorted list given a binary search tree...

Re: tree to single linked list conversion

Rahul wrote:[color=blue]

> Hi Everyone,

>

> I was working to convert a binary search tree into a singly linked

> list, so that i get a sorted singly linked list too, and this is the

> logic...

>

> root = single_r(root,NULL); // Caller invokes in this manner...

> static node* gresult; // Global pointer used to hold

> the new root.[/color]

[color=blue]

> I keep on rotating the left child of the current node and make it as

> a new root node. I keep repeating this until there isn't any left

> childs. Now i repeat this for the right child and so on...

>

> But the problem is that i have to return the new root node to the

> caller and currently i'm using a static flag to serve this purpose.

> But i want to avoid this as this doesn't fit well in multi-threaded

> applications. Is there any way to solve without using static variables

> and global variables and without iterations?[/color]

In general, you can always solve problems of this form in a mechanical

manner by making a temporary variable (usually a lexically-scoped local

variable) and then passing a pointer to that local variable into the

recursive function. Then you've replaced the global with a local.

For example, consider this node counting function that uses a global

variable:

int count; /* global */

void count_nodes(node* root) {

if (root == NULL) { return; }

count++;

count_nodes(root->left);

count_nodes(root->right);

}

void caller() {

count = 0;

count_nodes(sometree);

printf("there were %d nodes\n", count);

}

You can replace the above code with this:

void count_nodes_inner(node* root, int* count_ptr) {

if (root == NULL) { return; }

(*count_ptr)++;

count_nodes_inner(root->left, count_ptr);

count_nodes_inner(root->right, count_ptr);

}

int count_nodes_outer(node* root) {

int count = 0;

count_nodes_inner(root, & count);

}

void caller() {

printf("there were %d nodes\n", count_nodes_outer(sometree));

}

Often there is a better solution, but in the rare case that there isn't,

something like the above can always be used to eliminate the global

variable.

By the way, one object-oriented approach to solving this problem is to

create a class called something like TreeToListConversion. Then have a

method to do the conversion. The temporary state necessary during the

conversion can be stored in the fields of the object. It would be a

fairly short-lived object, but often that's OK.

- Logan