c# - 围绕着 N 个父-> 子关联

Question

我会尽力解释这一点。我很难弄清楚这个逻辑。

基本上，我有一个包含数千个对象的集合，每个对象都由一个父属性和一个子属性组成。

所以，大致是这样的:

public class MyObject{
     public string Parent { get; set; }
     public string Child { get; set; }
}

我想弄清楚的是如何将其构建到一个普通的 TreeView 控件中。我需要建立关系，但我不知道该怎么做，因为它们可以混合在一起。我可能可以用树应该是什么样子来更好地解释这一点:

所以如果我的收藏中有以下元素:

0. Parent: "A", Child: "B"
1. Parent: "B", Child: "C"
2. Parent: "B", Child: "D"

我希望我的树看起来像这样:

-A
--B
---C
-A
--B
---D
-B
--C
-B
--D

我如何在 C# 中执行此操作？我需要它来支持多达 N 个关系，因为我们有一些分支，我希望达到大约 50 个节点的深度。

Answer 1

更新

考虑到需要为每条路径重复整个树，这个问题实际上比我最初意识到的要复杂得多。我只是删除了旧代码，因为我不想增加任何进一步的困惑。

我确实想记录下来，使用递归数据结构使这更容易:

public class MyRecursiveObject
{
    public MyRecursiveObject Parent { get; set; }
    public string Name { get; set; }
    public List<MyRecursiveObject> Children { get; set; }
}

阅读下面的实现代码后，您会很清楚为什么这会更容易:

private void PopulateTree(IEnumerable<MyObject> items)
{
    var groupedItems =
        from i in items
        group i by i.Parent into g
        select new { Name = g.Key, Children = g.Select(c => c.Child) };
    var lookup = groupedItems.ToDictionary(i => i.Name, i => i.Children);
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, Enumerable.Empty<string>(), parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        IEnumerable<string> newPath = path.Concat(new string[] { name });
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
    }
    else
    {
        TreeNode parentNode = null;
        foreach (string item in path)
            parentNode = AddTreeNode(parentNode, item);
        AddTreeNode(parentNode, name);
    }
}

private TreeNode AddTreeNode(TreeNode parent, string name)
{
    TreeNode node = new TreeNode(name);
    if (parent != null)
        parent.Nodes.Add(node);
    else
        treeView1.Nodes.Add(node);
    return node;
}

首先，我意识到字典将包含中间节点的键以及根节点，因此我们不需要在递归 AddToTree 中进行两次递归调用。获取“B”节点作为根的方法；初次走进PopulateTree方法已经做到了。

我们做需要防止的是在初始遍历中添加叶节点；使用有问题的数据结构，可以通过检查父字典中是否有键来检测这些。使用递归数据结构，这会更容易:只需检查 Parent == null .但是，我们没有递归结构，所以我们必须使用上面的代码。

AddTreeNode主要是一个实用方法，所以我们以后不必再重复这个空值检查逻辑。

真正的丑陋在第二，递归AddToTree方法。因为我们试图为每个子树创建一个唯一的副本，所以我们不能简单地添加一个树节点，然后以该节点作为父节点进行递归。 “A”在这里只有一个 child ，“B”，但是“B”有两个 child ，“C”和“D”。 “A”需要有两个副本，但是当“A”最初传递给 AddToTree 时，无法知道这一点。方法。

所以我们实际上要做的是在最后阶段之前不创建任何节点，并存储一个临时路径，为此我选择了IEnumerable<string>。因为它是不可变的，因此不可能搞砸。当有更多 child 要添加时，此方法只是简单地添加到路径并递归；当没有更多 child 时，它会遍历整个保存的路径并为每个 child 添加一个节点。

这极度效率低下，因为我们现在在每次调用 AddToTree 时都会创建一个新的枚举对象.对于大量节点，很可能会占用大量内存。这可行，但使用递归数据结构会更有效。使用顶部的示例结构，您根本不必保存路径或创建字典；当没有 child 留下时，只需沿着 while 的路径走使用 Parent 循环引用。

无论如何，我想这是学术性的，因为这不是递归对象，但我认为无论如何都值得指出，作为 future 设计的注意事项。上面的代码将产生您想要的结果，我已经在真实的 TreeView 上进行了测试。

---

UPDATE 2 - 结果证明上面的版本在内存/堆栈方面相当残酷，很可能是创建所有这些 IEnumerable<string> 的结果实例。虽然这不是很好的设计，但我们可以通过更改为可变的 List<string> 来消除该特定问题。 .以下代码段显示了差异:

private void PopulateTree(IEnumerable<MyObject> items)
{
    // Snip lookup-generation code - same as before ...

    List<string> path = new List<string>();
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, path, parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        path.Add(name);
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
        path.Remove(name);
    }
    // Snip "else" block - again, this part is the same as before ...
}