Construção de objetos de hierarquia de lista simples de pai / filho

Question

Eu tenho uma lista de itens em uma hierarquia, e eu estou tentando analisar esta lista para fora em uma hierarquia real de objetos. Estou usando travessia para loja / iterate através desta lista, e assim o que eu tenho é um subconjunto da árvore, incluindo todas as crianças, ordenados por seu valor de "esquerda".

Por exemplo, dada a árvore:

• Item A
  • A.1 item
  • item a.2
    • A.2.2 item
• Item B
  • B.1 item
• Item C

Eu obter a lista:

• Item A, A.1 Item, A.2 Item, A.2.2 Item, item B, B.1 Item, item C

(Isto é, a fim do valor "esquerda" a partir da configuração modificada árvore de pré-encomenda).

O que eu quero fazer é analisar isso em objetos que contêm a estrutura real da árvore, por exemplo:

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

A lista plana é devolvido como uma lista de TreeObjects - e cada TreeObject tem propriedades para ID, ParentID, Esquerda e Direita. O que eu estou procurando é uma função:

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

que leva a lista plana, e retorna uma lista aninhada.

Em outras palavras:

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

Eu estou em uma perda de como fazer isso - Manter o controle de pais, e ser capaz de lidar com um salto ainda maior. (Por exemplo, A.2.2 item -> Item B)

---

Edit: Eu estou procurando uma solução de força bruta não aqui (por exemplo, não loop várias vezes, movendo itens em nós filhos, até que haja apenas os pais de nível superior esquerda). Eu estou supondo que existe um método elegante que pode fazer um loop uma vez, e basta colocar itens conforme necessário.

Lembre-se, eles estão sempre em uma ordem hierárquica (desde que eu estou usando MPTT), de modo que um determinado item vai ser sempre um filho ou irmão do item anterior, ou pelo menos compartilhar um pai com o item anterior. Ela nunca vai vir em algum outro lugar na árvore.

Answer 1

Aqui está a função acabei escrevendo. Estou usando MPTT para armazenar objetos, de modo que a lista está em ordem do valor 'esquerda', que basicamente significa que o pai vem sempre antes de qualquer item na lista. Em outras palavras, o item referenciado pelo item.ParentID sempre já foram adicionados (excepto no caso de nível superior ou nós de raiz).

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

e um teste simples (que funciona em 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();
}

Resultado:

Desde que eu estou atualizando este 5 anos depois, aqui está uma versão LINQ recursiva:

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 2

Eu suponho que você já sabe o pai de todos os itens .

Tudo que você precisa fazer é para percorrer todos os itens da lista uma vez e adicionar o item atual à lista filhos de seu pai. Apenas manter os itens sem os pais na lista aninhada alvo.

Aqui está um código pseudo:

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

Como para obter os pais, pelo que posso ver no seu exemplo, talvez seja necessário analisar o nome e construir uma pilha à medida que avançar na lista.

Este problemas Looks difícil, mas ele realmente não é. Um monte de gente ver este problema a partir do ângulo errado; você não deve tentar preencher todas as listas de crianças, mas sim se livrar dos itens Crianças a partir da lista plana, então torna-se fácil.

Answer 3

Versão alternativa que compila normalmente, eu não tinha certeza se havia um problema com o código acima.

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 4

Aqui está um exemplo, espero que isso ajude

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 5

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