添加树视图分支的最有效算法
我必须构建将分支（节点）添加到树视图中。我正在努力确定最低 O(n) 技术是什么。
我的数据如下所示：
Id ParentId Value
0 null Bob
1 0 Amy
2 1 Susan
3 1 Matt
4 2 Keith
5 4 Craig
6 4 Derrick
所以树看起来像：
我能想出的只是一个 n^2 算法对于每个条目，它会扫描所有其他条目以查看它们是否属于子节点。 我还在添加条目时从数组中删除要扫描的条目。所以如果记忆有效的话（可能不会），它比 n^2 略小。
还有更好的技术吗？
I have to build add the branches (nodes) to a tree view. I'm struggling to determine what the lowest O(n) technique is.
My data presents as follows:
Id ParentId Value
0 null Bob
1 0 Amy
2 1 Susan
3 1 Matt
4 2 Keith
5 4 Craig
6 4 Derrick
So the tree would look like:
All I can come up with is an n^2 algorithm which for every entry scans every other entry to see if they belong as a sub node.
I also am removing entries from the array to scan as they are being added. So it's a little less than n^2 if memory serves (probably not).
Are there any better techniques?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
假设您的语言具有某种列表/向量/可调整大小的数组类型，这非常简单。
为每个 ID 创建一个空列表。迭代每一行，如果 ParentId 不为 null，则将该 Id 添加到 ParentId 的列表中。
现在，您可以在 O(n) 时间内获得每个条目的子项。
Assuming your language has some sort of list/vector/resizable array type, this is pretty easy.
Make an empty list for each ID. Iterate over each row, and if ParentId is not null, add the Id to the ParentId's list.
You now have the children for each entry in O(n) time.