Envolver mi cabeza alrededor de padres-N> asociaciones niño

Question

Voy a tratar de explicar esto lo mejor que pueda. Estoy teniendo un poco de dificultad tratando de averiguar esta lógica.

Básicamente, tengo una colección que incluye miles de objetos que están compuestos a su vez de un padre y una propiedad secundaria.

Así que, más o menos, lo siguiente:

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

Lo que estoy tratando de averiguar es cómo construir esto en un control TreeView simple. Tengo que construir las relaciones, pero no puedo encontrar la manera de porque pueden ser mixtos. Es probable que pueda explicar esto mejor con lo que el árbol debe ser similar a:

Así que si tengo los siguientes elementos en el interior de mi colección:

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

Me gustaría que mi árbol para mirar esto como:

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

¿Cómo puedo hacer esto en C #? Que lo necesitaría para soportar hasta las relaciones N ya que tenemos algunas ramas que cabe esperar que alcance alrededor de 50 nodos de profundidad.

Answer 1

Actualizar

Este problema en realidad resultó ser bastante más compleja de lo que originalmente di cuenta, dado el requisito de repetir el el árbol completo para cada ruta. simplemente he borrado el código antiguo, ya que no quiero añadir más confusión.

Yo quiero seguir constancia de que el uso de una estructura de datos recursiva hace que esto sea más fácil:

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

Se va a ver muy claramente ¿Por qué esto es más fácil después de leer el código de implementación a continuación:

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

En primer lugar, me di cuenta de que el diccionario contiene las claves para los nodos intermedios, así como sólo los nodos raíz, por lo que no necesitamos dos llamadas recursivas en el método AddToTree recursiva con el fin de obtener los nodos "B" como raíces; la caminata inicial en el método PopulateTree ya lo hace.

Lo que hacer necesidad de evitar es la adición de nodos hoja en el paseo inicial; utilizando la estructura de datos en cuestión, estos son detectables mediante la comprobación de si existe o no una clave en el diccionario padres. Con una estructura de datos recursiva, esto sería manera más fácil: Sólo cheque por Parent == null. Sin embargo, una estructura recursiva no es lo que tenemos, por lo que el código anterior es lo que tenemos a su uso.

El AddTreeNode es sobre todo un método de utilidad, por lo que no tenemos que repetir esta lógica nulo comprobar más tarde.

La fealdad real está en el segundo método, AddToTree recursiva. Debido a que estamos tratando de crear una copia única de cada rama del árbol, no podemos simplemente añadir un nodo del árbol y luego recursivamente con ese nodo como el padre. "A" sólo tiene un niño aquí, "B", pero "B" tiene dos hijos, "C" y "D". Es necesario que haya dos copias de "A", pero no hay manera de saber de que cuando "A" está aprobado originalmente para el método AddToTree.

Así que lo que realmente tenemos que hacer es no crear cualquier linfáticos hasta la fase final, y almacenar una ruta temporal, para el que he elegido IEnumerable<string> porque es inmutable y, por tanto, imposible echar a perder. Cuando hay más niños que añadir, este método se limita a añadir a la ruta y recursivamente; cuando no hay más niños, que recorre toda la trayectoria de salvado y añade un nodo para cada uno.

Este es muy ineficientes porque estamos creando un nuevo enumerable en cada llamada de AddToTree. Para un gran número de nodos, es probable que masticar una gran cantidad de memoria. Esto funciona, pero sería mucho más eficiente con una estructura de datos recursiva. Usando el ejemplo de estructura en la parte superior, que no tiene que guardar la ruta en absoluto, o crear el diccionario; cuando no hay niños se quedan, simplemente caminar por el sendero en un bucle while utilizando la referencia Parent.

De todos modos, supongo que es académica, porque esto no es un objeto recursivo, pero pensé que valía la pena señalar de todos modos como algo a tener en cuenta para futuros diseños. El código anterior producir exactamente los resultados que desea, no tengo por delante se ha ido y comprobado en un TreeView real.

---

ACTUALIZACIÓN 2 - Así resulta que la versión anterior es bastante brutal con respecto a la memoria / pila, probablemente el resultado de la creación de todos esos casos IEnumerable<string>. Aunque no es un gran diseño, podemos eliminar ese tema en particular mediante el cambio a un List<string> mutable. A continuación se muestra fragmento de las diferencias:

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

Al igual que Rubens, he intentado tanto, pero un poco mejor, creo Una colección del árbol genérico

árbol de esta colección tiene algunas funciones agradable acumulación de moverse alrededor del árbol, ve a leer el resto del artículo

muestra con el enlace anterior

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

sería exactamente lo que acaba de aparecer

  

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

Answer 3

Si entiendo esto correctamente, lo que estamos tratando de hacer es tomar un árbol y transformarla en otra. La transformación se lleva a esencialmente cada no hoja-nodo en el árbol de entrada y crea un nodo para él (y sus descendientes) en el árbol de salida.

En primer lugar, usted será más feliz si se quiere diseñar una estructura de datos para sus nodos que es genuinamente recursiva:

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

Su clase MyObject representa relaciones padre / hijo entre los valores de cadena. Mientras que es capaz de poner en práctica un método FindChildren() que devuelve los valores niño para un valor determinado de los padres, usando esta clase de racionalizar las relaciones padre / hijo es sencillo:

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

Es muy sencillo de implementar una propiedad que devuelve descendientes de un nodo:

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

Para añadir un Node a un TreeView, se necesitan dos métodos. (Tenga en cuenta que estos no son métodos de la clase Node!) Que he hecho ellos sobrecargas, sino un argumento puede ser hecho por darles diferentes nombres:

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

Soy la creación de la Tag en cada TreeNode para que pueda encontrar su camino de regreso a la Node originales.

Así que para inicializar su TreeView de una lista de claves ascendentes de alto nivel, se necesita un método como este:

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

Editar

Yo no entiendo muy bien cómo su clase MyObject estaba trabajando; Creo que hago ahora, y yo he editado esta consecuencia.