algorithm - 创建对具有无限子层次结构的页面进行排序的算法时的建议

Question

在解决排序算法时，我需要一些建议。这个特定的算法将有一个包含 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;
}

Answer 1

您通常会使用某种字典数据结构来执行此操作。基本上，你有这样的结构:

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