Changing a tree into a list question

[transgalactic]

i got a BST tree
each node builded like this:

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 can't use malloc
and i can't 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

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 don't 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 can't go back to the root
and i can't cut this "founded node" from that tree without changing the structure of a tree

??

 

[transgalactic]

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 :

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 don't know how to combine then in the recurstion
??

 

[Coin]

So first off, this:

node *tree2list(node *root)
{

tree2list(root->left);

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)

 

[transgalactic]

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.

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 don't know how to define the recursive call
for the previous node in the list because it can be:

 return tree2list(root->left)->next=*root;

or

return tree2list(root->right)->next=*root;

??

 

[Coin]

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.

 

[transgalactic]

i tried to write a new function:
i got to the first stage of the base case.
when i put it into my tree

http://img204.imageshack.us/my.php?image=19509120rh8.gif

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 don't know how to continue
because
i kept only one variable (the last node)
i don't 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 don't know how to do this simple thing
and i can't think further regarding how it will act on the global scale
??

how to develop it further
??