tree to single linked list conversion - Unix

This is a discussion on tree to single linked list conversion - Unix ; 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... ...

+ Reply to Thread
Results 1 to 4 of 4

Thread: tree to single linked list conversion

  1. 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 ! ! !

  2. Re: tree to single linked list conversion

    Rahul writes:
    >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...


    >Thanks in advance ! ! !


    Do a google search on recursion. Look for algorithms for pre-order,
    in-order and post-order tree walkers.

    scott

  3. Re: tree to single linked list conversion

    On May 2, 10:48 pm, sc...@slp53.sl.home (Scott Lurndal) wrote:
    > Rahul writes:
    > >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...
    > >Thanks in advance ! ! !

    >
    > Do a google search on recursion. Look for algorithms for pre-order,
    > in-order and post-order tree walkers.
    >
    > scott


    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...

  4. Re: tree to single linked list conversion

    Rahul wrote:
    > 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.



    > 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?


    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

+ Reply to Thread