c# - 将我的头缠在N个家长/ child 协会上

我将尽力解释这一点。我在弄清楚这种逻辑时遇到了很多困难。

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

因此，大致而言：

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个节点的深度。

最佳答案

更新

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

我确实希望将其记录在案，因为使用递归数据结构可以使此操作更容易：

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”在这里只有一个孩子，“ B”，但是“ B”有两个孩子，“ C”和“ D”。必须有两个“ A”的副本，但是当“ A”最初传递给AddToTree方法时，没有办法知道。

因此，我们实际上要做的是直到最后阶段才创建任何节点，并存储一个临时路径，为此我选择了IEnumerable<string>，因为它是不可变的，因此不可能弄乱。当要添加的子项更多时，此方法将简单地添加到路径并递归。当没有更多孩子时，它将遍历整个保存的路径并为每个添加一个节点。

这是非常低效的，因为我们现在在每次AddToTree调用时都创建一个新的枚举。对于大量节点，可能会占用大量内存。这行得通，但是使用递归数据结构会更有效率。使用顶部的示例结构，您完全不必保存路径或创建字典。当没有孩子时，只需使用while引用在Parent循环中沿路径行进即可。

无论如何，我认为这是学术性的，因为这不是递归对象，但我认为无论如何值得指出的是将来设计时要牢记的东西。上面的代码将完全产生您想要的结果，我已经在真实的TreeView上进行了测试。



更新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 ...
}

关于c# - 将我的头缠在N个家长/ child 协会上，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2166843/