.net - tratar - pautas de crianza para padres psicologia

Construir objetos de jerarquía a partir de la lista plana de padres/hijos

Question

Tengo una lista de elementos en una jerarquía, y estoy tratando de analizar esta lista en una jerarquía real de objetos. Estoy usando un recorrido de árbol preordenado modificado para almacenar / iterar a través de esta lista, y entonces lo que tengo es un subconjunto del árbol, incluidos todos los elementos secundarios, ordenados por su valor "izquierdo".

Por ejemplo, dado el árbol:

• Artículo A
  • Ítem ​​A.1
  • Punto A.2
    • Artículo A.2.2
• Artículo B
  • Artículo B.1
• Artículo C

Obtengo la lista:

• Artículo A, punto A.1, punto A.2, punto A.2.2, punto B, punto B.1, punto C

(Esto está en el orden del valor "izquierda" de la configuración modificada del árbol de pre orden).

Lo que quiero hacer es analizar esto en objetos que contienen la estructura real del árbol, por ejemplo:

Class TreeObject {
    String Name;
    Guid ID; 
    Guid ParentID;
    List<TreeObject> Children;
}

La lista plana se devuelve como una Lista de TreeObjects, y cada TreeObject tiene propiedades para ID, ParentID, Left y Right. Lo que estoy buscando es una función:

List<TreeObject> FlatToHeirarchy(List<TreeObject> list); 

que toma la lista plana y devuelve una lista anidada.

En otras palabras:

List<TreeObject> flatSet = LoadTreeObjectsFromDatabase(); 
// flatSet.count == 7; flatSet(0).Children == null
List<TreeObject> nestedSet = FlatToHeirarchy(flatSet);
// nestedSet.count == 3; nestedSet(0).Children.count == 2

No sé cómo hacer esto: hacer un seguimiento de los padres y poder hacer frente a un salto más grande (por ejemplo, el punto A.2.2 -> artículo B).

Edición: estoy buscando una solución que no sea de fuerza bruta aquí (por ejemplo, no hacer bucles varias veces, mover elementos a nodos secundarios, hasta que solo queden los padres de nivel superior). Supongo que hay un método elegante que puede realizar bucles una sola vez, y simplemente colocar elementos según sea necesario.

Recuerde, siempre están en un orden jerárquico (ya que estoy usando MPTT), por lo que un elemento dado siempre será un hijo o hermano del elemento anterior, o al menos compartir un padre con el elemento anterior. Nunca va a venir a otro lugar en el árbol.

Answer 1

Aquí hay un ejemplo, espero que esto ayude

class Program
{
    static void Main(string[] args)
    {
        TreeObject a  = new TreeObject() { Name = "Item A" };
        a.Children.Add( new TreeObject() { Name = "Item A.1" });
        a.Children.Add( new TreeObject() { Name = "Item A.2" });

        TreeObject b = new TreeObject() { Name = "Item B" };
        b.Children.Add(new TreeObject() { Name = "Item B.1" });
        b.Children.Add(new TreeObject() { Name = "Item B.2" });

        TreeObject c = new TreeObject() { Name = "Item C" };

        List<TreeObject> nodes = new List<TreeObject>(new[] { a, b, c });

        string list = BuildList(nodes);
        Console.WriteLine(list); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C

        List<TreeObject> newlist = new List<TreeObject>();
        TreeObject temp = null;

        foreach (string s in list.Split('',''))
        {
            if (temp == null || !s.Contains(temp.Name) || temp.Name.Length != s.Length)
            {
                temp = new TreeObject() { Name = s };
                newlist.Add(temp);
            }
            else
            {
                temp.Children.Add(new TreeObject() { Name = s });
            }                              
        }

        Console.WriteLine(BuildList(newlist)); // Item A,Item A.1,Item A.2,Item B,Item B.1,Item B.2,Item C
    }

    static string BuildList(List<TreeObject> nodes)
    {
        StringBuilder output = new StringBuilder();
        BuildList(output, nodes);
        return output.Remove(output.Length - 1, 1).ToString();
    }

    static void BuildList(StringBuilder output, List<TreeObject> nodes)
    {
        foreach (var node in nodes)
        {
            output.AppendFormat("{0},", node.Name);
            BuildList(output, node.Children);
        }
    }
}

public class TreeObject
{
    private List<TreeObject> _children = new List<TreeObject>();

    public string Name { get; set; }
    public Guid Id { get; set; }
    public List<TreeObject> Children { get { return _children; } }
}

}

Answer 2

Versión alternativa que compila normalmente, no estaba seguro de si había algún problema con el código anterior.

private List<Page> FlatToHierarchy(List<Page> list) {
      // hashtable lookup that allows us to grab references to the parent containers, based on id
        Dictionary<int, Page> lookup = new Dictionary<int, Page>();
      // actual nested collection to return
      List<Page> nested = new List<Page>();

      foreach(Page item in list) {
        if (lookup.ContainsKey(item.parentId)) {
          // add to the parent''s child list 
          lookup[item.parentId].children.Add(item); //add item to parent''s childs list
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        } else {
          // no parent added yet (or this is the first time)
          nested.Add(item);     //add item directly to nested list                
          lookup.Add(item.pageId, item); //add reference to page in lookup table
        }
      }
    return nested;
    }

Answer 3

Corregir el ejemplo dado por gregmac

IList<TreeObject> FlatToHierarchy(IQueryable<lcc_classe> list, int? parentId)
    {
        var q = (from i in list
                where i.parent_id == parentId
                select new
                {
                    id = i.id,
                    parent_id = i.parent_id,
                    kks = i.kks,
                    nome = i.nome
                }).ToList();
        return q.Select(x => new TreeObject
            {
                children = FlatToHierarchy(list, x.id)
            }).ToList();
    }

Answer 4

Aquí está la función que terminé escribiendo. Estoy usando MPTT para almacenar objetos, por lo que la lista está en orden del valor ''izquierda'', lo que básicamente significa que el padre siempre viene antes que cualquier elemento dado en la lista. En otras palabras, el elemento al que se hace referencia por artículo.ParentID siempre se ha agregado (excepto en el caso de los nodos de nivel superior o raíz).

public class TreeObject
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
    public IList<TreeObject> Children { get; set; } = new List<TreeObject>();
}

public IEnumerable<TreeObject> FlatToHierarchy(List<TreeObject> list)
{
    // hashtable lookup that allows us to grab references to containers based on id
    var lookup = new Dictionary<int, TreeObject>();
    // actual nested collection to return
    var nested = new List<TreeObject>();

    foreach (TreeObject item in list)
    {
        if (lookup.ContainsKey(item.ParentId))
        {
            // add to the parent''s child list 
            lookup[item.ParentId].Children.Add(item);
        }
        else
        {
            // no parent added yet (or this is the first time)
            nested.Add(item);
        }
        lookup.Add(item.Id, item);
    }

    return nested;
}

y una prueba simple (que funciona en LinqPad):

void Main()
{
    var list = new List<TreeObject>() {
        new TreeObject() { Id = 1, ParentId = 0, Name = "A" },
        new TreeObject() { Id = 2, ParentId = 1, Name = "A.1" },
        new TreeObject() { Id = 3, ParentId = 1, Name = "A.2" },
        new TreeObject() { Id = 4, ParentId = 3, Name = "A.2.i" },
        new TreeObject() { Id = 5, ParentId = 3, Name = "A.2.ii" }
    };

    FlatToHierarchy(list).Dump();
}

Resultados:

Como estoy actualizando esto 5 años después, aquí hay una versión recursiva de LINQ:

public IList<TreeObject> FlatToHierarchy(IEnumerable<TreeObject> list, int parentId = 0) {
    return (from i in list 
            where i.ParentId == parentId 
            select new TreeObject {
                Id = i.Id, 
                ParentId = i.ParentId,
                Name = i.Name,
                Children = FlatToHierarchy(list, i.Id)
            }).ToList();
}

Answer 5

Supongo que ya conoce al padre de todos los artículos .

Todo lo que necesita hacer es recorrer una vez todos los elementos de la lista y agregar el elemento actual a la lista de elementos secundarios de sus padres. Solo mantenga los elementos sin padres en la lista anidada como objetivo.

Aquí hay un pseudo código:

foreach Item item in flatlist
   if item.Parent != null
      Add item to item.Parent.ChildrenList
      Remove item from flatlist
   end if
end for

En cuanto a los padres, por lo que puedo ver en su ejemplo, es posible que deba analizar el nombre y crear una pila a medida que avance en la lista.

Este problema parece difícil pero realmente no lo es. Mucha gente ve este problema desde el ángulo equivocado; no debe tratar de completar cada lista de niños, sino deshacerse de los elementos de los niños de la lista plana, luego se vuelve fácil.