changing a tree into a list question..

This is a discussion on changing a tree into a list question.. within the C Programming forums, part of the General Programming Boards category; i got a BST tree each node builded like this: Code: typedef struct node node; struct node { int value; ...

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    changing a tree into a list question..

    i got a BST tree
    each node builded like this:
    Code:
    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:
    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

    ??
    Last edited by transgalactic2; 10-30-2008 at 09:01 AM.

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Is using calloc() an option?

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i think calloc is forbidden too

    its an "in order" traversal
    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:
    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
    ??
    Last edited by transgalactic2; 11-01-2008 at 12:33 PM.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Do you ever read the code you write? Or the code you post? Surely you would need to check that root exists before you use it, and doing the left side of the tree twice surely isn't going to help.

    So look at what you want to happen -- you need to do the left side, with the least element getting a link from, well, nowhere and the greatest element linking to the root; and you need to do the left side, with the least element getting a link from the root and the greatest element linking to, well, nowhere. You could maybe make the same routine handle this, but it might be nicer to write two slightly different routines; the one on the left would return the greatest element, so it can be linked to root; the one on the right would return the smallest element, so the root can link to it. And if you're going to do the recursion, you should at some point at least try to handle the base case, which in this case is when there is no subtree.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Alright, so I've worked it out on paper. I used a helper function to do the recursion so's I could use some auxiliary variables (namely -- if this element is minimum, what needs to link to here; if this element is maximum, where does this element link to). Again, you're going to know whether you are maximum or minimum based on the absence of children, so those are your base cases, so to speak. If you sit down with a piece of paper and a tree drawn on it, you'll see how what to do in each case, I think.

    You'll also need to work out how to return a pointer to the least element in the whole tree (which will become the head of the linked list) (not hard).

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    If you get stuck, have a hunt here: http://thedailywtf.com
    Make sure you have a good go at it first though. I think you're doing well enough that you might be able to get a good solution on your own if you stick at it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    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:
    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);
    }
    Last edited by transgalactic2; 11-04-2008 at 03:23 AM.

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    the problem is i dont know how to define the recursive call
    for the previous node in the list because it can be:
    Code:
    return tree2list(root->left)->next=*root;
    or
    Code:
    return tree2list(root->right)->next=*root;
    Last edited by transgalactic2; 11-04-2008 at 03:27 AM.

  9. #9
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    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:
    http://img204.imageshack.us/my.php?image=19509120rh8.gif
    Code:
    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
    ??

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Consider: It's a binary tree. As in all recursive algorithms with a binary tree, you must have two recursive calls in the function (one down the left side, one down the right side). Ask yourself: If this node doesn't have a left child, what does that mean in terms of links? It allows you to set a link (from somewhere to the current node) -- so you'll have to pass in some information to set that link. If this node doesn't have a right child, what does that mean in terms of links? It allows you to set a link (from the current node to somewhere) -- so you'll have to pass in some information to set that link. Every time you make a recursive call you'll change that information for the next level.

    You're right that it needs to be in-order based (since you want the links to happen in-order) -- but instead of printing, you need to set a link when the children are NULL. Draw a tree with say ten nodes and look at the pattern. When a node doesn't have a left child, where does the link come from? When a node doesn't have a right child, where does the link go?

  11. #11
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i found another solution but i cant understand the purpose of this line

    Code:
    node* tree2list(node *root) {
      node *head,*temp
    if (!root) return null;
    if(root->left) head=tree2list(root->left);
    else head=root;
    temp=head;
    while(temp->next) temp=temp->next;
    if (head!=root) temp->next=root;               //what is the purpose of this line
    root->next=tree2list(root->right);
    
    return head;

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    What part of "if head is not the same as root, put root on to temp->right" do you struggle to understand?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    why does they put this line?

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by transgalactic2 View Post
    why does they put this line?
    It sets the link from the largest element on the left to the root element. That's what next is supposed to hold, the link to the next element.

  15. #15
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    but why to check if head!=root

    it should be only temp->next=root;

    in order to attach the end of the left sublist point to the root of the tree.

    why we need the head!=root
    checking?

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 12:21 PM
  2. Resource manager tree
    By VirtualAce in forum Game Programming
    Replies: 23
    Last Post: 09-07-2007, 10:27 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. question about linklist
    By fj8283888 in forum C Programming
    Replies: 1
    Last Post: 04-14-2004, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21