C# 手动对列表中的父/子树元素进行排序

Question

我正在尝试生成一个元素列表，如果可视化，这些元素将生成树结构。

例子：

Element 1 -> 1, 0 //ID is 1 & Parent ID is 0 (0 = root)
Element 2 -> 2, 0 //ID is 2 & Parent ID is 0 (0 = root)
Element 3 -> 3, 1 //ID is 3 & Parent ID is 1
Element 4 -> 4, 3
Element 5 -> 5, 2

如果要用这种结构来可视化一棵树：

为了实现这一点，节点类如下：

public class Node
{
    public string id;
    public string parentId;
    public List<Node> children = new List<Node>();  
}

与树类似，一个节点可能包含一个父节点，也可能包含多个其他子节点

任务是将元素排序到适当的层次结构并将子元素添加到其各自父级的子级集合中。我的想法有2种方法：

1) 循环法

i) 循环并查找 Base/root 节点（父节点为 0 的节点）

ii) 循环并查找以基本节点为父节点的节点

iii) 将它们添加到基本节点的子节点集合中

然而，上述方法最适用于深度为 2 的树，即根及其直接子级别。想象一棵具有多个复杂级别的树。这个方法对此不起作用。

这就是我到目前为止所尝试过的。

2）“递归”方法

第二种方法是“递归”方法。这就是我似乎还无法弄清楚的。谁能帮我解决这个问题吗？

以前有人尝试过解决这个问题吗？如何排列包含“n”个元素的列表，并定义了它们的父 ID 和 ID？

Answer 1

如果我理解正确的话，您有一个公寓List<Node>，并且想要填充children属性并最终得到根节点的列表。

id这可以通过（如Dictionary）和对源列表的单次迭代构建快速查找结构来有效地实现。对于每个节点，您将找到父节点并将该节点添加到父列表children（如果没有父节点，则添加到根列表）。该算法的时间复杂度为 O(N)。

static List<Node> BuildTree(List<Node> nodes)
{
    var nodeMap = nodes.ToDictionary(node => node.id);
    var rootNodes = new List<Node>();
    foreach (var node in nodes)
    {
        Node parent;
        if (nodeMap.TryGetValue(node.parentId, out parent))
            parent.children.Add(node);
        else
            rootNodes.Add(node);
    }
    return rootNodes;
}