Generic Tree Structure - Wie man ein Organigramm bevölkert

Question

Ich habe, was ein ziemlich triviales Problem sein sollte, aber ich möchte sicherstellen, dass ich das auf die "eleganteste" Weise mache, die in .Net 4.5 möglich ist und ich möchte einige Meinungen von Leuten, die schlauer sind als ich.

Ich habe eine Klasse, die eine generische Baumstruktur als solche darstellt:

public class TreeNode<T> 
    { 
     List<TreeNode<T>> Children; 

     T Item {get;set;} 

     public TreeNode (T item) 
     { 
      Item = item; 
     } 

     public TreeNode<T> AddChild(T item) 
     { 
      TreeNode<T> nodeItem = new TreeNode<T>(item); 
      Children.Add(nodeItem); 
      return nodeItem; 
     } 
    } 

Nun, ich habe eine Person-Klasse, die einen Mitarbeiter der Organisation darstellt. Jedes Person Objekt hat eine ID und eine BossID, die auf ihre Superior zeigt.

Mehrere Mitarbeiter können den gleichen Chef haben, weshalb ich versuche, ein Organigramm mit dieser Baumstruktur zu erstellen.

Der oberste Knoten wird das Objekt Person sein, wobei BossID null ist (es ist ein int?). Das kann ich schnell mit LINQ erreichen.

Es ist der nächste Schritt, der mich ein wenig verwirrt. Es gibt mehrere Ansätze, aber sie scheinen etwas schlampig zu sein und ich weiß, dass es eine viel einfachere/elegantere Möglichkeit geben muss, den Rest des Organigramms auszufüllen.

So jetzt habe ich ein generisches Objekt von List<Person> hält alle Mitarbeiter, mit ihren verschiedenen BossID s und diese generische Baumstruktur, die ich Kindknoten hinzufügen kann.

Es ist alles sehr einfach, aber was ist die richtige Reihenfolge, um den Baum zu füllen? Soll ich rekursiv die Linie durchlaufen? Ich weiß, dass hier ein Backtracking involviert ist, wo ich ratlos bin.

Ich entschuldige mich, mein Hintergrund ist nicht in der Informatik, und wenn es war, merke ich, dass Baumstrukturen, verknüpfte Listen und alles andere triviale Sachen sind. Aber das ist mein erster Versuch und ich möchte sehen, wie es richtig gemacht wird.

Ich schätze jede Anleitung.

Answer 1

Gegeben, so haben Sie eine Person Klasse wie folgt definiert:

public class Person 
{ 
    public int ID; 
    public int? BossID; 
} 

... und Sie haben eine List<Person> definiert als people dann funktioniert dies:

var lookup = people.ToLookup(p => p.BossID); 

Action<TreeNode<Person>> addChildren = null; 
addChildren = p => 
{ 
    foreach (var child in lookup[p.Item.ID]) 
    { 
     var childNode = p.AddChild(child); 
     addChildren(childNode); 
    } 
}; 

var trees = 
    from boss in lookup[null] 
    select new TreeNode<Person>(boss); 

foreach (var tree in trees) 
{ 
    addChildren(tree); 
} 

Dies setzt voraus, dass Sie kann haben mehr als eine Person mit einem null Chef. Wenn das nicht in Ordnung ist, führe einfach diesen Code aus und mache trees.First().

Die Definition von TreeNode<T> Ich war benutzten:

public class TreeNode<T> 
{ 
    private List<TreeNode<T>> Children; 

    public T Item { get; set; } 

    public TreeNode(T item) 
    { 
     this.Item = item; 
     this.Children = new List<TreeNode<T>>(); 
    } 

    public TreeNode<T> AddChild(T item) 
    { 
     var nodeItem = new TreeNode<T>(item); 
     this.Children.Add(nodeItem); 
     return nodeItem; 
    } 
} 

Sie TreeNode<T> zu diesem obwohl verkürzen könnte:

public class TreeNode<T> : List<TreeNode<T>> 
{ 
    public T Item { get; set; } 

    public TreeNode(T item) 
    { 
     this.Item = item; 
    } 
} 

... dann Ihre Notwendigkeit addChildren dazu zu ändern:

Action<TreeNode<Person>> addChildren = null; 
addChildren = p => 
{ 
    foreach (var child in lookup[p.Item.ID]) 
    { 
     var childNode = new TreeNode<Person>(child); 
     p.Add(childNode); 
     addChildren(childNode); 
    } 
}; 

... aber dann hätten Sie alle Standa rd List<> Operatoren verfügbar für TreeNode<T>.