围绕N父母 - >儿童协会缠头

Question

我会尽力解释这个问题.我试图找出这个逻辑时遇到了很多困难.

基本上,我有一个包含数千个对象的集合,每个对象都由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个节点.

Answer 1

UPDATE

考虑到为每条路径重复整个树的要求,这个问题实际上比我最初实现的要复杂得多.我只是删除了旧代码,因为我不想再添加任何混淆.

我确实希望保持记录,使用递归数据结构使这更容易:

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