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

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、父 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

Answer 2

不需要递归。只是对对象进行简单的循环。对于每个对象，如果其parent_id为0，则将其复制到answer数组。否则，通过父对象在数组中的位置来访问父对象，并将当前对象附加到其子对象列表中。

以下是您的阵列的工作原理。请仔细注意更新对象一次会更新该对象的所有副本这一事实的结果。

0: Start
    answer = []
    objects = [
        {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}
    ]

1: Append object 1 to answer
    answer = [
        {id : 1, parent_id : 0}
    ]
    objects = [
        {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}
    ]

2: Append object 2 to children of object 1
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1}
        ]},
        {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}
    ]

3: Append object 3 to children of object 1
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1}
        ]},
        {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}
    ]

4: Append object 4 to children of object 2
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3}
            ]}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3}
        ]},
        {id : 4, parent_id : 2},
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

5: Append object 5 to children of object 4
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3, children : [
                {id : 5, parent_id : 4}
            ]}
        ]},
        {id : 4, parent_id : 3, children : [
            {id : 5, parent_id : 4}
        ]}
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]

6: Append object 6 to answer
    answer = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 6, parent_id : 0}
    ]
    objects = [
        {id : 1, parent_id : 0, children : [
            {id : 2, parent_id : 1},
            {id : 3, parent_id : 1, children : [
                {id : 4, parent_id : 3, children : [
                    {id : 5, parent_id : 4}
                ]}
            ]}
        ]},
        {id : 2, parent_id : 1},
        {id : 3, parent_id : 1, children : [
            {id : 4, parent_id : 3, children : [
                {id : 5, parent_id : 4}
            ]}
        ]},
        {id : 4, parent_id : 3, children : [
            {id : 5, parent_id : 4}
        ]}
        {id : 5, parent_id : 4},
        {id : 6, parent_id : 0}
    ]