algorithme pour convertir des données plates hiérarchiques (p/ParentID) dans la liste plate triés w/niveaux d'indentation

Question

I ont la structure suivante:

MyClass { 
    guid ID 
    guid ParentID 
    string Name 
} 

je voudrais créer un tableau qui contient les éléments dans l'ordre ils devraient être affichés dans une hiérarchie (par exemple en fonction de leurs valeurs "à gauche"), ainsi qu'un hachage qui mappe le guid au niveau d'indentation.

Par exemple:

ID  Name  ParentID 
------------------------ 
1  Cats  2 
2  Animal NULL 
3  Tiger 1 
4  Book  NULL 
5  Airplane NULL 

Ce serait essentiellement produire les objets suivants:

// 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 

Pour plus de clarté, voici ce que la hiérarchie ressemble:

Airplane 
Animal 
    Cats 
    Tiger 
Book 

I'D aime à parcourir les articles le moins de fois possible. Je ne veux pas non plus créer une structure de données hiérarchique. Je préfère utiliser des tableaux, des hachages, des piles ou des files d'attente.

Les deux objectifs sont les suivants:

1. magasin un hachage de l'ID au niveau de retrait.
2. Triez la liste contenant tous les objets en fonction de leurs valeurs de gauche.

Lorsque j'obtiens la liste des éléments, ils ne sont pas dans un ordre particulier. Les frères et sœurs doivent être classés par leur propriété Name.

Mise à jour: Cela peut paraître comme si je n'avais pas essayé de trouver moi-même une solution et que je voulais simplement que les autres fassent le travail pour moi. Cependant, j'ai essayé de trouver trois solutions différentes, et je me suis retrouvé coincé sur chacune d'entre elles. Une raison pourrait être que j'ai essayé d'éviter la récursivité (peut-être à tort). Je ne publie pas les solutions partielles que j'ai jusqu'à présent car elles sont incorrectes et peuvent influencer les solutions des autres.

Answer 1

Le message de Wonsungi a beaucoup aidé, mais c'est pour un graphique générique plutôt qu'un arbre. Donc, je l'ai modifié un peu pour créer un algorithme conçu spécifiquement pour un arbre:

// Data strcutures: 
nodeChildren: Dictionary['nodeID'] = List<Children>; 
indentLevel: Dictionary['nodeID'] = Integer; 
roots: Array of nodes; 
sorted: Array of nodes; 
nodes: all nodes 

// Step #1: Prepare the data structures for building the tree 
for each node in nodes 
    if node.parentID == NULL 
    roots.Append(node); 
    indentLevel[node] = 0; 
    else 
    nodeChildren[node.parentID].append(node); 

// Step #2: Add elements to the sorted list 
roots.SortByABC(); 
while roots.IsNotEmpty() 
    root = roots.Remove(0); 
    rootIndentLevel = indentLevel[root]; 
    sorted.Append(root); 
    children = nodeChildren[root]; 
    children.SortByABC(); 
    for each child in children (loop backwards) 
    indentLevel[child] = rootIndentLevel + 1 
    roots.Prepend(child) 

Answer 2

Pour les structures hiérarchiques, vous aurez probablement besoin d'une récursivité (si vous autorisez une profondeur arbitraire). Je me suis vite piraté en place un code de rubis pour illustrer comment vous pourriez y parvenir ( bien que je ne l'ai pas fait l'indentation):

# setup the data structure 
class S < Struct.new(:id, :name, :parent_id);end 

class HierarchySorter 

    def initialize(il) 
     @initial_list = il 
     first_level = @initial_list.select{|a| a.parent_id == nil}.sort_by{|a| a.name } 
     @final_array = subsort(first_level, 0) 
    end 

    #recursive function 
    def subsort(list, indent_level) 
     result = [] 
     list.each do |item| 
      result << [item, indent_level] 
      result += subsort(@initial_list.select{|a| a.parent_id == item.id}.sort_by{|a| a.name }, indent_level + 1) 
     end 
     result 
    end 

    def sorted_array 
     @final_array.map &:first 
    end 

    def indent_hash 
     # magick to transform array of structs into hash 
     Hash[*@final_array.map{|a| [a.first.id, a.last]}.flatten] 
    end 

end 

hs = HierarchySorter.new [S.new(1, "Cats", 2), S.new(2, "Animal", nil), S.new(3, "Tiger", 1), S.new(4, "Book", nil), 
    S.new(5, "Airplane", nil)] 

puts "Array:" 
puts hs.sorted_array.inspect 

puts "\nIndentation hash:" 
puts hs.indent_hash.inspect 

Si vous ne parlez pas ruby ​​je peux re-craft dans autre chose .

Modifier: J'ai mis à jour le code ci-dessus pour afficher les deux structures de données.

Sorties:

Array: 
[#<struct S id=5, name="Airplane", parent_id=nil>, #<struct S id=2, name="Animal", parent_id=nil>, #<struct S id=1, name="Cats", parent_id=2>, #<struct S id=3, name="Tiger", parent_id=1>, #<struct S id=4, name="Book", parent_id=nil>] 

Indentation hash: 
{5=>0, 1=>1, 2=>0, 3=>2, 4=>0} 

Answer 3

je besoin d'un algorithme similaire pour trier les tâches avec dépendances (chaque tâche pourrait avoir une tâche parent qui devait être fait en premier). J'ai trouvé tri topologique. Voici un iterative implementation in Python avec des commentaires très détaillés.

Le niveau d'indentation peut être calculé lors du tri topologique.Définissez simplement le niveau d'indentation d'un noeud sur le niveau d'indentation de son noeud parent + 1 lors de son ajout à l'ordre topologique.

Notez qu'il peut exister de nombreux ordres topologiques valides. Pour garantir l'ordre topologique résultant des groupes de nœuds parents avec des nœuds enfants, sélectionnez un algorithme de tri topologique basé sur la traversée en profondeur du graphique produit par les informations d'ordre partiel.

Wikipedia donne two more algorithms for topological sort. Notez que ces algorithmes ne sont pas aussi bons parce que le premier est traversée en largeur et le second est récursif.