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.
While not strictly a C issue, as it's really an algorithm issue, here
is my solution.
You can do it in only two passes.
The first pass counts the number of nodes.
The second pass is recursive. Start with the number of the middle node,
recursively call the tree-build routine for the left node (which starts
at the middle node of the left branch), create the parent mode for this
piece of the tree, and recursively call it for the right node. (If you
are at a leaf node, then you obviously skip the left- and right-node
steps.)
While this sounds like you need to have random access to the list, it
turns out that all nodes will be found in sequential order. Remember,
until you need the node (ie: it's a leaf node, or it's the parent node
after parsing the left branch), all you need is the node number, not
the contents of the node.
ie:
4
/ \
/ \
/ \
2 6
/ \ / \
1 3 5 7
The MiddleNode is (BranchLowest+BranchHighest)/2. Each left-branch
goes from BranchLowest to MiddleNode-1, and each right-branch goes
from MiddleNode+1 to BranchHighest. If MiddleNode==BranchLowest,
there is no left branch. If MiddleNode==BranchHighest, there is no
right branch. You are at a leaf node when BranchLowest==BranchHighest.
Given 7 nodes, start at node (1+7)/2=4. The left branch for node 4
is at (1+(4-1))/2=2. The left node for 2 starts at (1+(2-1))/2=1.
Node 1 is a leaf node. You then process parent node 2. You then
go to the right-branch for 2, which is leaf-node 3. (The right
branch goes from 2+1 to 4-1, where 2 is your node, and 4 is your
parent's node.) You're now done with the left-node from 4, so you
now have parent node 4. Now you go through the right branch from 4.
You start at node 6, which takes the left branch to leaf-node 5,
parent node 6, right branch to leaf-node 7.
In other words, you have accessed the nodes' contents in order from 1,
2, 3, 4, 5, 6, and finally 7, which is just fine for a singly-linked
list.
--
+-------------------------+--------------------+-----------------------------+
| Kenneth J. Brody |
www.hvcomputer.com | |
| kenbrody/at\spamcop.net |
www.fptech.com | #include <std_disclaimer.h> |
+-------------------------+--------------------+-----------------------------+
Don't e-mail me at: <mailto:
[email protected]>