将列表转换为树 [英] convert a list to tree
问题描述
给定一个单链接的空终止列表，如何将它转换为
树？列表中的每个节点都有三个属性：它的ID，它的父级
ID，当然还有它所指向的下一个节点。树的根
的父ID是0.列表的长度未知。什么是
最佳解决方案？
节点* convertToTree（节点* listHead）;
我的解决方案有很多扫描和重新扫描列表。
问候，
prabhat
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
推荐答案
pr********@gmail.com 写道：
给定一个单链接，空终止列表，如何将其转换为
树？列表中的每个节点都有三个属性：它的ID，它的父ID
ID，当然还有它所指向的下一个节点。树的根
的父ID是0.列表的长度是未知的。什么是最佳解决方案？
节点* convertToTree（节点* listHead）;
我的解决方案有很多扫描和重新扫描列表。
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.
虽然不是严格意义上的C问题，因为它确实是算法问题，这里
是我的解决方案。
你可以只用两遍。
第一遍计算节点数。
第二遍是递归的。从中间节点的编号开始，
递归调用左节点的树构建例程（在左侧分支的中间节点处启动
），创建这个
片段的父模式，并递归调用它为正确的节点。 （如果你是
在叶子节点，那么你显然会跳过左右节点
步骤。）
虽然这听起来像你需要随机访问列表，但事实证明，所有节点都将按顺序找到。记住，
直到你需要节点（即：它是一个叶子节点，或者解析左分支后它是父节点
），所有你需要的是节点号，而不是节点的内容。
ie：
4
/ \
/ \
/ \
2 6
/ \ / \\ \\ b
1 3 5 7
MiddleNode是（BranchLowest + BranchHighest）/ 2。每个左分支
从BranchLowest到MiddleNode-1，每个右分支从MiddleNode + 1到BranchHighest从
开始。如果MiddleNode == BranchLowest，
则没有左分支。如果MiddleNode == BranchHighest，则没有
右分支。当BranchLowest == BranchHighest时，您处于叶节点。
给定7个节点，从节点（1 + 7）/ 2 = 4开始。节点4的左分支
为（1 +（4-1））/ 2 = 2。 2的左节点从（1+（2-1））/ 2 = 1开始。
节点1是叶节点。然后你处理父节点2.你然后
转到右分支2，这是叶节点3.（右边
分支从2 + 1开始到4-1，其中2是你的节点，4是你的'b $ b'父节点。）你现在已经完成了4的左节点，所以你
现在有父节点4.现在你从4开始通过正确的分支。
你从节点6开始，它将左分支带到叶节点5，
父节点6，右分支到叶节点7.
换句话说，您已经按顺序从1开始访问节点的内容，
2,3,4,5,6，最后7，这对于单独链接的
列表来说很好。
-
+ ------------------------- + ---------------- ---- + ----------------------------- +
| Kenneth J. Brody | www.hvcomputer.com | |
| kenbrody / at\spamcop.net | www.fptech.com | #include< std_disclaimer.h> |
+ ------------------------- + -------------- ------ + ----------------------------- +
不要给我发邮件：< mailto：Th ************* @ gmail.com>
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:Th*************@gmail.com>
pr ******** @ gmail.com 写道：
pr********@gmail.com writes:
给定一个单独链接的空终止列表，如何将其转换为树？列表中的每个节点都有三个属性：它的ID，它的父ID
ID，当然还有它所指向的下一个节点。树的根
的父ID是0.列表的长度是未知的。什么是最佳解决方案？
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?
您希望如何安排树？你想要树还是
二叉树？另外，我认为这会更好。
comp.programming。
-
我不是要说服白痴不要傻。
无论如何他们都不会听。
- 丹恩柯比特
How do you want the tree arranged? Do you want a tree or a
binary tree? Also, I think this would be better off in
comp.programming.
--
"I''m not here to convince idiots not to be stupid.
They won''t listen anyway."
--Dann Corbit
pr********@gmail.com 写道：
pr********@gmail.com wrote:
给定一个单独链接的空终止列表，如何将其转换为
树？
从列表中弹出一个元素，将其推入树中。重复直到
列表为空。之后保留列表留作
的练习...
什么是最佳解决方案？
Given a singly linked, null terminated list, how can it be converted to
tree?
Pop an element off the list, push it into the tree. Repeat until the
list is empty. Preserving the list afterwards is left as an exercise for
the...
What will be the optimal solution?
....家庭作业骗子。
Richard
....homework cheater.
Richard
这篇关于将列表转换为树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
