在解决排序算法时,我需要一些建议。这个特定的算法将有一个包含 n 个项目的列表的输入。每个项目都有一个 ID 和一个父 ID。像这样:
[
{id : 1, parent_id : 0},
{id : 2, parent_id : 1},
{id : 3, parent_id : 1},
{id : 4, parent_id : 2},
{id : 5, parent_id : 4},
{id : 6, parent_id : 0}
]
这是预期的结果:
[
{id : 1, parent_id : 0, children:
[
{id : 2, parent_id : 1, children:
[
{id : 4, parent_id : 2, children:
[
{id : 5, parent_id : 4}
]}
]
},
{id : 3, parent_id : 1}
]},
{id : 6, parent_id : 0}
]
我最初的想法是将算法拆分为层次结构级别,递归地解析每个级别。所以它在理论上看起来像这样:
- 将未排序列表中的每个项目与所有项目进行比较,看是否有任何匹配项,将每个匹配项放入每个父项的子节点中,将每个父项放入排序列表变量中。
- 将子节点中的每个项与未排序列表中的所有项进行比较,看是否匹配,将每个子节点中的匹配放入自己的子节点中。
- 继续最后一步,直到每个级别都没有匹配项。
我刚刚开始研究一些函数式编程范例,并开始阅读更多有关算法和分析的内容,只是因为我不熟悉递归思考。
所以我的问题是:
- 在处理某种逻辑时,您有什么建议?
- 我如何学会以正确的方式思考?
- 通过查看我当前的算法,我觉得我已经掌握了这个概念,只是我真的不知道如何使第二次检查作为递归解决方案工作。我离正确的方向还远吗?
到目前为止,我已经创建了一个算法,该算法将具有 2 级层次结构。它看起来像这样(目前用 php 编写,只是概念代码的证明):
function sortParentsChildren($unsortedList, $parentIDKey = "parent_id", $childNameKey = "children"){
$sortedList = array();
foreach($unsortedList as $key => $value){
$children = array();
//See if there are any children for this item
foreach($unsortedList as $skey => $svalue){
if($value["id"] == $svalue[$parentIDKey]){
$children[] = $svalue;
}
}
//Add all items with parent id = 0 to the root
if($value["parent_id"] == 0){
$sortedList[$key] = $value;
}
//Check if there were any children
if(sizeof($children) > 0){
//Search each children and see if they have any matches
foreach($children as $ckey => $cvalue){
foreach($unsortedList as $s2key => $s2value){
if($cvalue["id"] == $s2value[$parentIDKey]){
$children[$ckey][$childNameKey][] = $s2value;
}
}
}
$sortedList[$key] = $value;
$sortedList[$key][$childNameKey] = $children;
}
}
return $sortedList;
}
最佳答案
您通常会使用某种字典数据结构来执行此操作。基本上,你有这样的结构:
Node
{
int id;
int parent;
Node[] children;
}
您将其保存在字典或以 id 为键的关联数组中。创建一个id值为0,parent id为-1的节点。
按父 ID 对输入数组进行排序,然后遍历列表。对于每个项目,将其添加到字典中。同时查找它的父节点(它已经在字典中,因为输入列表已按父 id 排序),并将新节点添加到父节点的子列表中。
完成后,node[0] 包含构造的层次结构。
我不是 PHP 程序员,所以您必须使用伪代码:
Nodes = new associative array
Nodes[0] = new Node(0, -1)
sortedInput = sort input by parent id
foreach item in sortedInput
Nodes[item.id] = new Node(item.id, item.parent);
//Nodes[item.parent].Children.Add(Node);
// Above line commented and replaced with this.
Nodes[item.parent].Children.Add(Nodes[item.id]);
end
// Nodes[0] contains the hierarchy
OutputNode(Nodes[0], "")
输出层级的函数是递归的:
OutputNode(Node, indent)
print indent, Node.id, Node.parent
foreach (child in Node.children)
OutputNode(child, indent+" ");
end
end
关于algorithm - 创建对具有无限子层次结构的页面进行排序的算法时的建议,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5886142/