Re: convert a list to tree
From: Richard Harter (cri_at_tiac.net)
Date: 01/22/05
- Next message: Ben Pfaff: "Re: convert a list to tree"
- Previous message: Chris Torek: "Re: To find the size of array using its pointer"
- In reply to: Till Crueger: "Re: convert a list to tree"
- Next in thread: Ben Pfaff: "Re: convert a list to tree"
- Reply: Ben Pfaff: "Re: convert a list to tree"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sat, 22 Jan 2005 18:15:43 GMT
On Sat, 22 Jan 2005 11:36:56 +0100, Till Crueger <TillFC@gmx.net>
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.
- Next message: Ben Pfaff: "Re: convert a list to tree"
- Previous message: Chris Torek: "Re: To find the size of array using its pointer"
- In reply to: Till Crueger: "Re: convert a list to tree"
- Next in thread: Ben Pfaff: "Re: convert a list to tree"
- Reply: Ben Pfaff: "Re: convert a list to tree"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
