Wrapping meinen Kopf um N Eltern-> Kind Verbände

Question

Ich werde versuchen, das Geheimnis der besten erklären kann ich. Ich habe ziemlich viel Mühe, um herauszufinden, dieser Logik zu versuchen.

Grundsätzlich habe ich eine Sammlung, die Tausende von Objekten enthält, die jeweils aus einem Elternteil und einem Kind Eigentum sind.

So etwa diese:

public class MyObject{
     public string Parent { get; set; }
     public string Child { get; set; }
}

Was ich versuche, um herauszufinden, ist, wie diese aus in einem einfachen TreeView-Steuerelement zu bauen. Ich brauche die Beziehungen zu bauen, aber ich kann nicht herausfinden, wie man, weil sie gemischt werden kann. Ich kann wahrscheinlich erklären, das besser mit dem, was der Baum aussehen sollte:

Also, wenn ich die folgenden Elemente in meiner Sammlung:

0. Parent: "A", Child: "B"
1. Parent: "B", Child: "C"
2. Parent: "B", Child: "D"

Ich würde mein Baum möchte dies wie folgt aussehen:

-A
--B
---C
-A
--B
---D
-B
--C
-B
--D

Wie kann ich dies in C #? Ich würde es brauchen, um N Beziehungen zu unterstützen, wie wir einige Zweige haben ich erwarten würde etwa 50 Knoten tief zu erreichen.

Answer 1

UPDATE

Dieses Problem tatsächlich erwies sich als wesentlich komplexer zu sein, als ich ursprünglich realisiert, da die Anforderung der Wiederholung des ganzen Baum für jeden Pfad. Ich habe gelöscht einfach den alten Code, wie ich keine weitere Verwirrung hinzufügen will.

Ich will es auf Rekord halten, dass eine rekursive Datenstruktur macht dies einfacher:

public class MyRecursiveObject
{
    public MyRecursiveObject Parent { get; set; }
    public string Name { get; set; }
    public List<MyRecursiveObject> Children { get; set; }
}

Sie werden sehen, sehr klar Warum das ist einfacher nach Beginn der Umsetzung Code unten zu lesen:

private void PopulateTree(IEnumerable<MyObject> items)
{
    var groupedItems =
        from i in items
        group i by i.Parent into g
        select new { Name = g.Key, Children = g.Select(c => c.Child) };
    var lookup = groupedItems.ToDictionary(i => i.Name, i => i.Children);
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, Enumerable.Empty<string>(), parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        IEnumerable<string> newPath = path.Concat(new string[] { name });
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
    }
    else
    {
        TreeNode parentNode = null;
        foreach (string item in path)
            parentNode = AddTreeNode(parentNode, item);
        AddTreeNode(parentNode, name);
    }
}

private TreeNode AddTreeNode(TreeNode parent, string name)
{
    TreeNode node = new TreeNode(name);
    if (parent != null)
        parent.Nodes.Add(node);
    else
        treeView1.Nodes.Add(node);
    return node;
}

Zunächst einmal wurde mir klar, dass die Dictionary-Schlüssel für Zwischenknoten sowie nur die Wurzelknoten enthalten, so dass wir die „B“ Knoten nicht zwei rekursiven Aufrufe in der rekursiven AddToTree Methode müssen, um zu bekommen Wurzeln; der anfängliche Spaziergang im PopulateTree Methode bereits tut es.

Was wir tun Notwendigkeit zum Schutz vor ist das Hinzufügen von Blattknoten in dem Anfang zu Fuß; die Datenstruktur in Frage verwendet, ist diese nachweisbar durch Prüfen, ob es ein Schlüssel im Stammverzeichnis ist. Mit einer rekursiven Datenstruktur würde auf diese Weise leichter: Just-Check für Parent == null. Aber eine rekursive Struktur ist nicht das, was wir haben, so dass der Code oben ist, was wir zu verwenden.

Die AddTreeNode ist meist eine Hilfsmethode, also müssen wir nicht halten diese Null-Prüfung zu wiederholen Logik später.

Die eigentliche Hässlichkeit ist in der zweiten, rekursive AddToTree Methode. Weil wir eine eindeutige Kopie jeder einzelnen Teilstruktur zu schaffen versuchen, können wir nicht einfach einen Baum Knoten hinzufügen und dann mit diesem Knoten als Mutter Rekursion. „A“ hat nur ein Kind hier, „B“, aber „B“ hat zwei Kinder, „C“ und „D“. Es braucht zwei Kopien von „A“ zu sein, aber es gibt keinen Weg, um zu wissen, dass, wenn „A“ ursprünglich die AddToTree Methode übergeben wird.

Also, was wir wirklich tun müssen, ist erstellen nicht jeder Knoten bis zur letzten Phase, und speichern Sie einen temporären Pfad, für die ich IEnumerable<string> entschieden, weil es ist unveränderlich und daher unmöglich zu vermasseln. Wenn es mehr Kinder hinzuzufügen, diese Methode fügt einfach auf den Pfad und rekursiv; wenn es keine Kinder mehr sind, es den gesamten gespeicherten Pfad geht und fügt einen Knoten für jeden.

Dies ist extrem ineffizient, weil wir jetzt einen neuen enumerable bei jedem Aufruf von AddToTree zu schaffen. Für eine große Anzahl von Knoten, ist es wahrscheinlich eine Menge Speicher kauen. Dies funktioniert, aber es wäre viel effizienter mit einer rekursiven Datenstruktur sein. Am Beispiel Struktur an der Spitze, würden Sie nicht den Weg überhaupt speichern müssen oder das Wörterbuch erstellen; wenn keine Kinder bleiben, einfach zu Fuß des Weges in einer while Schleife mit der Parent Referenz auf.

Wie auch immer, ich denke, dass die akademische ist, weil dies kein rekursiven Objekt ist, aber ich dachte, dass es wert war ohnehin als etwas unter Hinweis darauf, für zukünftige Designs im Auge zu behalten. Der obige Code wird produziert genau die gewünschten Ergebnisse, habe ich weitergemacht und getestet es auf einem echten TreeView.

---

UPDATE 2 - So stellt sich heraus, dass die Version über ziemlich brutal ist in Bezug auf Speicher / Stapel, wahrscheinlich aufgrund der alle jene IEnumerable<string> Instanzen zu schaffen. Obwohl es nicht großer Entwurf ist, können wir diese besondere Ausgabe entfernen auf ein veränderbares List<string> durch Veränderung. Der folgende Ausschnitt zeigt die Unterschiede:

private void PopulateTree(IEnumerable<MyObject> items)
{
    // Snip lookup-generation code - same as before ...

    List<string> path = new List<string>();
    foreach (string parent in lookup.Keys)
    {
        if (lookup.ContainsKey(parent))
            AddToTree(lookup, path, parent);
    }
}

private void AddToTree(Dictionary<string, IEnumerable<string>> lookup,
    IEnumerable<string> path, string name)
{
    IEnumerable<string> children;
    if (lookup.TryGetValue(name, out children))
    {
        path.Add(name);
        foreach (string child in children)
            AddToTree(lookup, newPath, child);
        path.Remove(name);
    }
    // Snip "else" block - again, this part is the same as before ...
}

Answer 2

wie rubens, habe ich versucht, beide, aber ein wenig besser ich denke A Generisches Tree Collection

dieser Baum Sammlung bekam einige nette Funktionen build-in den Baum zu bewegen, den ganzen Artikel lesen go

Probe mit dem obigen Link

Static Class Module1
{

    public static void Main()
    {
        Common.ITree<myObj> myTree = default(Common.ITree<myObj>);
        myObj a = new myObj("a");
        myObj b = new myObj("b");
        myObj c = new myObj("c");
        myObj d = new myObj("d");

        myTree = Common.NodeTree<myObj>.NewTree;
        myTree.InsertChild(a).InsertChild(b).InsertChild(c).Parent.Parent.InsertNext(a).InsertChild(b).InsertChild(d).Parent.Parent.InsertNext(b).InsertChild(c).Parent.InsertNext(b).InsertChild(d);

        Console.WriteLine(myTree.ToStringRecursive);

        Console.ReadKey();
    }
}

Class myObj
{
    public string text;

    public myObj(string value)
    {
        text = value;
    }

    public override string ToString()
    {
        return text;
    }
}

wäre genau das, was Sie gerade zeigte

  

-A
  -B
  --- C
  -A
  -B
  --- D
  -B
  -C
  -B
  -DE

Answer 3

Wenn ich das richtig verstehen, was Sie versuchen, einen Baum zu tun ist, nehmen und es in einer anderen umwandeln. Die Transformation erfolgt im wesentlichen jeden Nicht-Blattknoten in dem Eingangsbaum und erzeugt einen Knoten für sie (und ihre Nachkommen) in dem Ausgabebaum.

Als erstes werden Sie glücklicher sein, wenn Sie eine Datenstruktur für Ihre Knoten Design, das wirklich rekursiv ist:

public class Node
{
   public Node Parent { get; private set; }
   public IEnumerable<Node> Children { get; private set; }
   public bool HasChildren { get { return Children.Count() > 0; } }

   public Node()
   {
      Children = new List<Node>();
   }
}

Ihre MyObject Klasse repräsentiert Eltern / Kind-Beziehungen zwischen String-Werten. Solange Sie sind in der Lage eine FindChildren() Methode zu implementieren, dass die Renditen der Kinder Werte für einen bestimmten übergeordneten Wert, diese Klasse mit den Eltern / Kind-Beziehungen zu rationalisieren ist einfach:

public string Value { get; set; }
public static Node Create(string parentKey)
{
   Node n = new Node();
   n.Value = parentKey;
   foreach (string childKey in FindChildren(parentKey))
   {
      Node child = n.Children.Add(Node.Create(childKey));
      child.Parent = n;
   } 
   return n;
}

Es ist einfach eine Eigenschaft, dass die Rendite eines Knotens Nachkommen zu implementieren:

public IEnumerable<Node> Descendants
{
   get
   {
      foreach (Node child in Children)
      {
         yield return child;
         foreach (Node descendant in child.Descendants)
         {
            yield return descendant;
         }
      }
   }
}

Um ein Node zu einem TreeView hinzuzufügen, müssen Sie zwei Methoden. (Beachten Sie, dass diese nicht Methoden der Node Klasse!) Ich habe sie Überlastungen gemacht, aber ein Argument, können sie verschiedene Namen zu geben gemacht werden:

public void AddNode(Node n, TreeView tv)
{
   TreeNode tn = tv.Nodes.Add(n.Value);
   tn.Tag = n;
   foreach (Node child in n.Children)
   {
      AddNode(child, tn);
   }
}

public void AddNode(Node n, TreeNode parent)
{
   TreeNode tn = parent.Nodes.Add(n.Value);
   parent.Tag = n;
   foreach (Node child in n.Children)
   {
      AddNode(child, tn);
   }
}

Ich gründe die Tag auf jedem TreeNode, so dass Sie Ihren Weg zurück zum ursprünglichen Node finden.

So Ihre TreeView aus einer Liste von Top-Level-Mutterschlüssel zu initialisieren, müssen Sie eine Methode wie folgt:

public void PopulateTreeView(IEnumerable<string> parents, TreeView t)
{
   foreach (string parentKey in parents)
   {
      Node n = Node.Create(parentKey);
      AddNode(n, t);
      foreach (Node descendant in n.Descendants)
      {
         if (n.HasChildren)
         {
            AddNode(descendant, t);
         }
      }
   }
}

Edit:

Ich habe nicht ganz verstanden, wie Sie Ihre MyObject Klasse Arbeit war; Ich denke, dass ich jetzt, und ich habe dies entsprechend bearbeitet werden.