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

<分区>

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

示例:

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>();  
}

Similar to a tree, a node may contain a parent and it also may contain multiple other children nodes

任务是将元素排序到它们适当的层次结构中，并将子元素添加到它们各自父元素的子元素集合中。我想到了2种方法:

1) 循环法

i) Loop & find the Base/root nodes (nodes with parent as 0)

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

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

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

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

2)“递归”方法

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

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

最佳答案

如果我没理解错的话，你有一套公寓 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;
}

关于C# 手动排序列表中的父/子树元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40027390/

上一篇：algorithm - 字符串转换的最低成本

下一篇：algorithm - 插入排序——阅读麻省理工学院算法简介时遇到的麻烦

相关文章：

Haskell:使用埃拉托斯特尼筛法的非详尽模式

c# - "open/close"SqlConnection 还是保持打开状态？

c# - 在每个非查询或整个连接之前打开连接？

algorithm - 您将如何从单向链表(一次遍历)中的尾部获取第 n 个节点？

arrays - 如何用函数递归地填充数组？

haskell - 定义与此 Haskell 函数等效的尾递归函数

c# - GroupBy 元组列表 C#

c# - 在c#中使用openxml和pdfcreator将docx转换为pdf

c - 邻接矩阵中的传递关系

Java扫描仪从文件中读取字符频率