Thread: changing a tree into a list question..

Is using calloc() an option?

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.

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

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

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?

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;

why does they put this line?

Originally Posted by transgalactic2

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.

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?