Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Changing a tree into a list question

  1. Oct 30, 2008 #1
    i got a BST tree
    each node builded like this:
    Code (Text):


    typedef struct node node;
    struct node {
      int value;
       node *left,* right,*next;
    };
     
    i need to change it into a sorted linked list from the smallest to the biggest.
    i cant use malloc
    and i cant change the anything in this tree

    i need to write a function called

    node *tree2list(node *root) that gets a root of the tree and returns the head of a list


    first i can find the smallest member in this tree
    Code (Text):

    while (tree->left){
    tree=tree->left;
    }
     
    the problem comes when i need to find the second smallest
    and put it to the "next" of the smallest member of all the tree

    its a recursion


    but i dont know how to make a pointer for a tree which will lack that "first found " node

    because our pointer after that loop is at the bottom of a tree
    i cant go back to the root
    and i cant cut this "founded node" from that tree without changing the structure of a tree

    ??
     
  2. jcsd
  3. Nov 1, 2008 #2
    by "in order" traversal method
    it goes from the smallest to the biggest
    first it goes to the most left (the smallest) then it goes to the middle one
    then to the biggest
    so my solution is :

    Code (Text):

    typedef struct node node;
    struct node {
      int value;
       node *left,* right,*next;
    };

    node *tree2list(node *root)
        {

     tree2list(root->left);
        if (root){
           return root;
                    }
     tree2list(root->left);

    }
     
     
    by this traversal i go from the smallest to the biggest
    BUT I DONT KNOW HOW TO DO THE LINKING PART

    ??

    it should be some thing like

    tree2list(root->left)->next=tree2list(root);
    tree2list(root)->next=tree2list(root)->right;

    but i dont know how to combine then in the recurstion
    ??
     
  4. Nov 1, 2008 #3
    So first off, this:

    Is *really bad*, it will cause an immediate infinite loop. There needs to be some kind of "termination condition" that will cause tree2list to NOT be called when you reach the leftmost place.

    As for "how to combine them in the recursion", I am not altogether certain I understand what you are trying to do, but what I would recommend is that you add a second argument to tree2list pointing to the list you are trying to add to, and then you simply add nodes to the list pointed to as you go. (If that makes sense.)

    Another option is to write some kind of separate "concatenate linked lists" function. If you have the ability to add one linked list to another, then your tree2list function becomes very simple, something like :

    list l = tree2list(root->left)
    list r = tree2list(root->right)
    return list_concatenate(l, r)
     
  5. Nov 4, 2008 #4
    this is an "in order " code
    but i need that instead of printing the "value" of the node
    it will link it to the "next" of the previous smaller node.


    Code (Text):

    typedef struct node node;
    struct node {
      int value;
       node *left,* right,*next;
    };

    node *tree2list(node *root)
        {
    if (!root){
      return null;
               }
    tree2list(root->left);
        if (root){
           printf("%d",root->value);  //i need to change this line
                    }
     tree2list(root->right);
    }
     
    the problem is i dont know how to define the recursive call
    for the previous node in the list because it can be:
    Code (Text):

     return tree2list(root->left)->next=*root;
     
    or
    Code (Text):

    return tree2list(root->right)->next=*root;  
     
    ??
     
  6. Nov 5, 2008 #5
    I'm sorry, I just don't understand what it is you're trying to do here. I guess I can make two general comments about your particular code snippets here:

    - You say "if (!root) return null;", then a few lines later you say "if (root) { do something }". The second if (root) is redundant because if root is null, then you have already returned from the function. Remember, if you "return" at any point during a function then the remainder of the function is not executed.

    - If you say something->next=*root; this will not compile. "->next" and "root" are pointers to nodes, "*root" will be just a node. The types do not match.

    - If you remove the asterisk and say " return tree2list(root->left)->next=root; " this will compile but I do not think it will do what you want. This will:
    - Query tree2list to obtain a pointer to [some node]
    - Assign the 'next' field of [some node] to root
    - Throw the pointer to [some node] away and return root
    Sometimes it is a good idea to try to only do one thing per line, so that you do not create confusions like this.
     
  7. Nov 8, 2008 #6
    i tried to write a new function:
    i got to the first stage of the base case.
    when i put it into my tree
    Code (Text):

    http://img204.imageshack.us/my.php?image=19509120rh8.gif
     
    Code (Text):

    node tree2list(node *root,node *first,node *last)
    {

    if (!root->left) {
                      first=root;
                      first->next=last;
                      return last;
    return last=tree2list(root->left,first,root);
                           
     
    in the end when i get to the call where
    tree2list(node *root,node *first,node *last) root=node5 first=null last=node10
    in this call
    first=node5
    first->next= node10
    and it returns node10

    i dont know how to continue
    because
    i kept only one variable (the last node)
    i dont know how to keep the head of the list

    and now i got only two nodes connected
    i need to connect the last one (which is the local "father") to its right node

    i dont know how to do this simple thing
    and i cant think further regarding how it will act on the global scale
    ??

    how to develop it further
    ??
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Changing a tree into a list question
Loading...