Algoritmo para converter dados simples hierárquicos (com ParentID) em lista simples classificada com níveis de indentação
Eu tenho a seguinte estrutura:
MyClass {
guid ID
guid ParentID
string Name
}
Gostaria de criar uma matriz que contenha os elementos na ordem em que devem ser exibidos em uma hierarquia (por exemplo, de acordo com seus valores "esquerdos"), bem como um hash que mapeia o guid para o nível de indentação.
Por exemplo:
ID Name ParentID
------------------------
1 Cats 2
2 Animal NULL
3 Tiger 1
4 Book NULL
5 Airplane NULL
Isso essencialmente produziria os seguintes objetos:
// Array is an array of all the elements sorted by the way you would see them in a fully expanded tree
Array[0] = "Airplane"
Array[1] = "Animal"
Array[2] = "Cats"
Array[3] = "Tiger"
Array[4] = "Book"
// IndentationLevel is a hash of GUIDs to IndentationLevels.
IndentationLevel["1"] = 1
IndentationLevel["2"] = 0
IndentationLevel["3"] = 2
IndentationLevel["4"] = 0
IndentationLevel["5"] = 0
Para maior clareza, é assim que a hierarquia se parece:
Airplane
Animal
Cats
Tiger
Book
Eu gostaria de percorrer os itens o mínimo de vezes possível. Também não quero criar uma estrutura de dados hierárquica. Eu preferiria usar matrizes, hashes, pilhas ou filas.
Os dois objetivos são:
Armazene um hash do ID no nível de indentação.Classifique a lista que contém todos os objetos de acordo com os valores à esquerda.Quando recebo a lista de elementos, eles não estão em uma ordem específica. Os irmãos devem ser ordenados por sua propriedade Nome.
Atualizar: Pode parecer que eu ainda não tentei encontrar uma solução e simplesmente quero que os outros façam o trabalho por mim. No entanto, tentei encontrar três soluções diferentes e fiquei presa em cada uma. Um motivo pode ser o fato de eu ter tentado evitar recursões (talvez de maneira errada). Não estou postando as soluções parciais que tenho até agora, pois elas estão incorretas e podem influenciar muito as soluções de outras pessoas.