围绕着 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

更新

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

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

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因为它是不可变的因此不可能搞砸。当需要添加更多子节点时，此方法只需添加到路径并递归；当没有更多的子节点时，它会遍历整个保存的路径并为每个子节点添加一个节点。

这是非常低效的，因为我们现在在每次调用 AddToTree 时都会创建一个新的枚举。对于大量节点来说，很可能会消耗大量内存。这是可行的，但使用递归数据结构会更有效。使用顶部的示例结构，您根本不必保存路径或创建字典；当没有子节点时，只需使用 Parent 引用在 while 循环中沿着路径向上走即可。

不管怎样，我想这是学术性的，因为这不是一个递归对象，但我认为无论如何都值得指出，作为未来设计中需要记住的事情。上面的代码将完全产生您想要的结果，我已经在真实的 TreeView 上对其进行了测试。

---

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

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

Answer 2

像鲁本斯一样，我都尝试了，但我认为更好一点通用树集合

这个树集合有一些很好的内置功能，可以在树上移动，请阅读

上面链接的整篇文章示例，

Static Class Module1
{

    public static void Main()
    {
        Common.ITree<myObj> myTree = default(Common.ITree<myObj>);
        myObj a = new myObj("a");
        myObj b = new myObj("b");
        myObj c = new myObj("c");
        myObj d = new myObj("d");

        myTree = Common.NodeTree<myObj>.NewTree;
        myTree.InsertChild(a).InsertChild(b).InsertChild(c).Parent.Parent.InsertNext(a).InsertChild(b).InsertChild(d).Parent.Parent.InsertNext(b).InsertChild(c).Parent.InsertNext(b).InsertChild(d);

        Console.WriteLine(myTree.ToStringRecursive);

        Console.ReadKey();
    }
}

Class myObj
{
    public string text;

    public myObj(string value)
    {
        text = value;
    }

    public override string ToString()
    {
        return text;
    }
}

这正是您刚刚展示的内容

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

Answer 3

如果我理解正确的话，你要做的就是把一棵树变成另一棵树。该转换实质上采用输入树中的每个非叶节点，并在输出树中为其（及其后代）创建一个节点。

首先，如果您为节点设计一个真正递归的数据结构，您会更高兴：

public class Node
{
   public Node Parent { get; private set; }
   public IEnumerable<Node> Children { get; private set; }
   public bool HasChildren { get { return Children.Count() > 0; } }

   public Node()
   {
      Children = new List<Node>();
   }
}

您的 MyObject 类表示字符串值之间的父/子关系。只要您能够实现一个 FindChildren() 方法来返回给定父值的子值，使用此类来合理化父/子关系就很简单：

public string Value { get; set; }
public static Node Create(string parentKey)
{
   Node n = new Node();
   n.Value = parentKey;
   foreach (string childKey in FindChildren(parentKey))
   {
      Node child = n.Children.Add(Node.Create(childKey));
      child.Parent = n;
   } 
   return n;
}

实现一个返回节点后代的属性：

public IEnumerable<Node> Descendants
{
   get
   {
      foreach (Node child in Children)
      {
         yield return child;
         foreach (Node descendant in child.Descendants)
         {
            yield return descendant;
         }
      }
   }
}

要将 Node 添加到 TreeView，您需要两个方法。 （请注意，这些不是 Node 类的方法！）我已经对它们进行了重载，但是可以为它们提供不同的名称：

public void AddNode(Node n, TreeView tv)
{
   TreeNode tn = tv.Nodes.Add(n.Value);
   tn.Tag = n;
   foreach (Node child in n.Children)
   {
      AddNode(child, tn);
   }
}

public void AddNode(Node n, TreeNode parent)
{
   TreeNode tn = parent.Nodes.Add(n.Value);
   parent.Tag = n;
   foreach (Node child in n.Children)
   {
      AddNode(child, tn);
   }
}

我正在设置 Tag< /code> 在每个 TreeNode 上，以便您可以找到返回原始 Node 的路。

因此，要从顶级父键列表初始化您的 TreeView，您需要这样的方法：

public void PopulateTreeView(IEnumerable<string> parents, TreeView t)
{
   foreach (string parentKey in parents)
   {
      Node n = Node.Create(parentKey);
      AddNode(n, t);
      foreach (Node descendant in n.Descendants)
      {
         if (n.HasChildren)
         {
            AddNode(descendant, t);
         }
      }
   }
}

编辑：

我不太明白您的 MyObject 如何 类正在工作；我想我现在已经这样做了，并且我已经相应地对此进行了编辑。