|
|
 | | From: | Richard Harter | | Subject: | Re: convert a list to tree | | Date: | Thu, 20 Jan 2005 15:48:18 GMT |
|
|
 | On 18 Jan 2005 07:18:40 -0800, prabhat143@gmail.com wrote:
>Hi,
>
>Given a singly linked, null terminated list, how can it be converted to
>tree? Each node in the list has three attributes: it's ID, it's parent
>ID and of course, the next node it's pointing to. The parent id of root
>of the tree is 0. The length of list is not known. What will be the
>optimal solution?
>
>Node* convertToTree(Node* listHead);
>
>My solution had a lot of scanning and rescanning of list.
>regards,
>prabhat
For some reason everyone seems to misread this request. Each node
contains its own ID (so we can know which node is which) and ITS
PARENT ID, i.e., an identifier of the node's parent in the tree. The
structure of the tree is already specified in the list; the object is
to construct the predefined tree.
The fundamental problem I have with this formulation is that the type
of node required for the tree is different from the type of node in
the linked list. Tree nodes provide links to an indefinitely large
number of children; the described list nodes do not.
I have added comp.programming to the newsgroups.
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.
|
|
| | From: | moi | | Subject: | Re: convert a list to tree | | Date: | Thu, 20 Jan 2005 19:55:32 +0100 |
|
|
| Richard Harter wrote:
> On 18 Jan 2005 07:18:40 -0800, prabhat143@gmail.com wrote:
>
>
>>Hi,
>>
>>Given a singly linked, null terminated list, how can it be converted to
>>tree? Each node in the list has three attributes: it's ID, it's parent
>>ID and of course, the next node it's pointing to. The parent id of root
>>of the tree is 0. The length of list is not known. What will be the
>>optimal solution?
>>
>>Node* convertToTree(Node* listHead);
>>
>>My solution had a lot of scanning and rescanning of list.
>>regards,
>>prabhat
>
>
>
> For some reason everyone seems to misread this request. Each node
> contains its own ID (so we can know which node is which) and ITS
> PARENT ID, i.e., an identifier of the node's parent in the tree. The
> structure of the tree is already specified in the list; the object is
> to construct the predefined tree.
>
> The fundamental problem I have with this formulation is that the type
> of node required for the tree is different from the type of node in
> the linked list. Tree nodes provide links to an indefinitely large
> number of children; the described list nodes do not.
>
> I have added comp.programming to the newsgroups.
Smells like homework. silly typedef's ...
If sizeof pointer <= sizeof ID, this could be done. (XOR trick ?)
Why would anyone ever store the *parent* ID in a linked list node?
HTH,
AvK
|
|
| | From: | Till Crueger | | Subject: | Re: convert a list to tree | | Date: | Sat, 22 Jan 2005 11:36:56 +0100 |
|
|
| On Thu, 20 Jan 2005 19:55:32 +0100, moi wrote:
> Richard Harter wrote:
>> On 18 Jan 2005 07:18:40 -0800, prabhat143@gmail.com wrote:
>>>Given a singly linked, null terminated list, how can it be converted to
>>>tree? Each node in the list has three attributes: it's ID, it's parent
>>>ID and of course, the next node it's pointing to. The parent id of root
>>>of the tree is 0. The length of list is not known. What will be the
>>>optimal solution?
>>>
>>>Node* convertToTree(Node* listHead);
>> For some reason everyone seems to misread this request. Each node
>> contains its own ID (so we can know which node is which) and ITS
>> PARENT ID, i.e., an identifier of the node's parent in the tree. The
>> structure of the tree is already specified in the list; the object is
>> to construct the predefined tree.
>>
>> The fundamental problem I have with this formulation is that the type
>> of node required for the tree is different from the type of node in
>> the linked list. Tree nodes provide links to an indefinitely large
>> number of children; the described list nodes do not.
>>
>> I have added comp.programming to the newsgroups.
>
> Smells like homework. silly typedef's ...
> If sizeof pointer <= sizeof ID, this could be done. (XOR trick ?)
> Why would anyone ever store the *parent* ID in a linked list node?
As far as I understood it the Parent ID is not the ID of the Parent in
the list, but the ID of the Parent in the Tree. So it makes sense actually
to store it. Here is an Example of how it might look:
------- ------- ------- -------
|ID =1| |Id =0| |ID =3| |ID=2 |
|Data | ->|Data | ->|Data | ->|Data |
|PID=0| |PID=0| |PID=0| |PID=1|
------- ------- ------- -------
The tree constructed from this would look like this (Only IDs)
0
/ \
1 3
/
2
There Never was a word about anything being sorted in this case, Nor did
the OP ever talk about an Binary-Search tree. My guess is that the list is
some weird serialisation of the Tree.
To find an O(n^2) Solution to this problem is quiet trivial. I am not sure
if there actually is a better solution. I certainly can't think of one. My
best guess would be to begin with a forest instead of a tree, i.E.
something like this:
While (Nodes in List) DO
Pop a node from the list
Create a new Tree in the Forest from node
Combine trees
OD
The only Problem I have left is the Combine Trees step, which might get
pretty lengthy. I guess each tree has to keep a List of its Parent, and
you`d have to Use some kind of UNION-FIND structure for the updates.
HTH,
Till
--
Please add "Salt and Peper" to the subject line to bypass my spam filter
|
|
| | From: | Richard Harter | | Subject: | Re: convert a list to tree | | Date: | Sat, 22 Jan 2005 18:15:43 GMT |
|
|
| On Sat, 22 Jan 2005 11:36:56 +0100, Till Crueger
wrote:
Till Crueger seems to be the only person who read the request and
understood it. It's sort of depressing, really.
>On Thu, 20 Jan 2005 19:55:32 +0100, moi wrote:
>
>> Richard Harter wrote:
>>> On 18 Jan 2005 07:18:40 -0800, prabhat143@gmail.com wrote:
>
>>>>Given a singly linked, null terminated list, how can it be converted to
>>>>tree? Each node in the list has three attributes: it's ID, it's parent
>>>>ID and of course, the next node it's pointing to. The parent id of root
>>>>of the tree is 0. The length of list is not known. What will be the
>>>>optimal solution?
>>>>
>>>>Node* convertToTree(Node* listHead);
This can't be right; the input is a list node and the output is a tree
node. A proper description might be:
TreeNode * convertToTree(ListNode * ListHead);
There are various structures that one could use for a tree node; a
reasonable (minimal) choice is:
struct TreeNode {
ID id;
TreeNode *children;
};
The natural way to do this task is O(n^2). The key difficulty is
associating an id with an address, i.e., a list node specifies a
parent's id whereas what one needs is the address of the parent's node
in the tree.
Realizing that, the obvious thing to do is to use a hash table that
contains the tree node addresses. Initially each tree node contains
an id and an empty children list. We then scan the list; for each
list node we look up the tree nodes for the item id and the parent id.
We then add the item tree node to the parent tree node's children
list. This is a O(n) solution. There are many others, both O(n) and
O(n*log(n)).
[snip complaint by RH]
>> Smells like homework. silly typedef's ...
>> If sizeof pointer <= sizeof ID, this could be done. (XOR trick ?)
>> Why would anyone ever store the *parent* ID in a linked list node?
Apparently "moi" accidently attached comments to the wrong post.
>
>As far as I understood it the Parent ID is not the ID of the Parent in
>the list, but the ID of the Parent in the Tree. So it makes sense actually
>to store it. Here is an Example of how it might look:
>
>------- ------- ------- -------
>|ID =1| |Id =0| |ID =3| |ID=2 |
>|Data | ->|Data | ->|Data | ->|Data |
>|PID=0| |PID=0| |PID=0| |PID=1|
>------- ------- ------- -------
>
>The tree constructed from this would look like this (Only IDs)
>
> 0
> / \
> 1 3
> /
> 2
>
>There Never was a word about anything being sorted in this case, Nor did
>the OP ever talk about an Binary-Search tree. My guess is that the list is
>some weird serialisation of the Tree.
I can think of contexts where it would be a natural data
representation. For example, given a company you might a have a list
of employees (specified by ID) and, for each employee, the ID of their
boss. What you want is the command structure of the company. You
might have a list of components and subsystems. For each element you
have know the subsystem it belongs to; recover the the system
structure.
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.
|
|
| | From: | Ben Pfaff | | Subject: | Re: convert a list to tree | | Date: | Sat, 22 Jan 2005 10:26:32 -0800 |
|
|
| cri@tiac.net (Richard Harter) writes:
>>>>>Node* convertToTree(Node* listHead);
>
> This can't be right; the input is a list node and the output is a tree
> node.
If the node has appropriate fields for representing both lists
and trees, then it could be correct. For example, you could
represent a list with `prev' and `next' pointers, then later
treat these as `left' and `right' pointers in a binary tree
representation of a tree.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
|
|
| | From: | Richard Harter | | Subject: | Re: convert a list to tree | | Date: | Sat, 22 Jan 2005 20:57:50 GMT |
|
|
| On Sat, 22 Jan 2005 10:26:32 -0800, Ben Pfaff
wrote:
>cri@tiac.net (Richard Harter) writes:
>
>>>>>>Node* convertToTree(Node* listHead);
>>
>> This can't be right; the input is a list node and the output is a tree
>> node.
>
>If the node has appropriate fields for representing both lists
>and trees, then it could be correct. For example, you could
>represent a list with `prev' and `next' pointers, then later
>treat these as `left' and `right' pointers in a binary tree
>representation of a tree.
True enough. However the OP explicitly said that (a) the nodes
contained two IDs and one pointer, and (b) the tree isn't necessarily
a binary tree, so one couldn't reuse the nodes the way you suggest.
On the other hand my remark about a tree node needing one pointer is
also wrong; you need a children link and a sibling link. If we add
another link field then your suggestion goes through.
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
All my life I wanted to be someone;
I guess I should have been more specific.
|
|
|
