Baumstruktur aus Liste erzeugen

[fillibuster]

Hallo,

ich versuche gerade eine Baumstruktur (Treeview) aus einer Liste zu erzeugen. Diese hat folgendes Format:

1;Beschreibung 1
1;Beschreibung 2
2;Beschreibung 3
2;Beschreibung 4
3;Beschreibung 5
1;Beschreibung 6
2;Beschreibung 7

Das einlesen und erzeugen von Knoten ist kein Problem, aber ich weiß nicht, wie ich die Struktur erzeugen kann. Sollte so aussehen:

Code:

Beschreibung 1
Beschreibung 2
  |- Beschreibung 3
  |- Beschreibung 4
         |- Beschreibung 5
Beschreibung 6
  |- Beschreibung 7

Hat jemand einen Tipp für mich? Danke!

[baumina]

So richtig hab ich deine Frage nicht verstanden, du kannst die Liste einlesen und du kannst Knoten erzeugen wie in diesem Codebeispiel. Was fehlt denn jetzt noch genau?

EDIT: Achso für C# natürlich dann z.B. hier

[fillibuster]

Hi,

ich habe ein Problem die Baumstruktur zu erzeugen. Die Nodes sollen ja nicht alle einfach auf die oberste Ebene gepackt werden!

Viele Grüße ...

[JasonDX]

Hier ein Stück Pseudocode das das ganze Lösen sollte:

Code:

var recentNode = root(); // depth = 0
for ([depth, element] in list)
  parentNode = recentNode
  while (parentNode.depth >= depth)
    parentNode = parentNode.parent
  parentNode.addChild(element)
  recentNode = element

(ungetestet, erwartet gültige Tiefenangaben)

[add]Erklärung: Der Code merkt sich den zuletzt hinzugefügten Knoten. Dann hangelt er sich den Baum hoch, bis die richtige Tiefe erreicht ist, und fügt dann das nächste Kind ein.

[fillibuster]

Hallo,

danke werde ich mal in Ruhe testen :thumb:

Viele Grüße ...

[Sir Rufo]

Grundsätzlich gesehen ist diese Art der Liste für einen Baum relativ wackelig.

Besser wäre es eine Liste mit einem Index und ParentIndex zu verwenden

idx	pidx	Description
1	0	Beschreibung 1
2	0	Beschreibung 2
3	2	Beschreibung 3
4	2	Beschreibung 4
5	4	Beschreibung 5
6	0	Beschreibung 6
7	6	Beschreibung 7

Dabei sind in diesem Beispiel die Root-Elemente, die mit pidx=0.

Nun ist es völlig egal, in welcher Reihenfolge diese Daten vorliegen, der Baum kann immer korrekt erstellt werden.

[fillibuster]

Hallo,

@Sir Rufo: mach ich immer so, wenn eine Datenbank im Programm vorhanden ist - find ich auch einfacher!

Jetzt habe ich aber dazu noch eine Frage. Weiß jemand, wie ich diese Struktur am einfachsten nach JSON bekomme? Also komplett ohne Treeview (Baumstruktur soll aber in JSON enthalten sein). Json.net habe ich jetzt erstmal installiert und eine Klasse für die Einträge erstellt:

Code:

    public class navigationItem
    {
        public string key { get; set; }
        public string title { get; set; }
        public string meta { get; set; }
        public string icon { get; set; }
        public string tooltip { get; set; }
        public string document { get; set; }
        public string mime { get; set; }
        public string filetype { get; set; }
        public List<navigationItem> children { get; set; }
    }

Jetzt sitze ich an einer rekursiven Funktion und brauch nen Denkanstoss (configList ist die eingelesene Liste):

Code:

   private string createTree(List<string> configList, List<navigationItem> navigationList)
   {   
       return JsonConvert.SerializeObject(navigationList);
   }

Danke

[Phoenix]

Also erstmal die Baumstruktur:

Code:

// create test data
   var list = new [] {
      new Node() { Id=1, Description="Beschreibung 1", ParentId = 0 },
      new Node() { Id=2, Description="Beschreibung 2", ParentId = 0 },
      new Node() { Id=3, Description="Beschreibung 3", ParentId = 2 },
      new Node() { Id=4, Description="Beschreibung 4", ParentId = 2 },
      new Node() { Id=5, Description="Beschreibung 5", ParentId = 4 },
      new Node() { Id=6, Description="Beschreibung 6", ParentId = 0 },
      new Node() { Id=7, Description="Beschreibung 7", ParentId = 6 },   
   };
   
   // make a lookup to quickly build the structure -> O(n)
   var lookup = list.ToLookup(node => node.ParentId);
   
   // hook up the nodes (also O(n))
   var tree = new List<Node>();   
   foreach (var node in list)
   {
      // if root node, add to tree
      if (node.ParentId == 0)
         tree.Add(node);

      // hook in all children
      node.Children = lookup[node.Id].ToList();
   }

Was das serialisieren nach Json angeht, schau Dir am besten mal Newtonsoft.Json an: https://www.nuget.org/packages/Newtonsoft.Json/
Das ist *das* Library in .NET wenn es um Json geht. Selbst Microsoft setzt in vielen Teilen seiner Web-Libraries inzwischen darauf.

Das ist dann ein Einzeiler:

Code:

string jsonString = JsonConvert.SerializeObject(tree);

Der JsonString sieht dann so aus:

Code:

[
   {"Id":1,"ParentId":0,"Description":"Beschreibung 1","Children":[]},
   {"Id":2,"ParentId":0,"Description":"Beschreibung 2","Children":
      [
         {"Id":3,"ParentId":2,"Description":"Beschreibung 3","Children":[]},
         {"Id":4,"ParentId":2,"Description":"Beschreibung 4","Children":
            [
               {"Id":5,"ParentId":4,"Description":"Beschreibung 5","Children":[]}
            ]
         }
      ]
   },
   {"Id":6,"ParentId":0,"Description":"Beschreibung 6","Children":
      [
         {"Id":7,"ParentId":6,"Description":"Beschreibung 7","Children":[]}
      ]
   }
]

[fillibuster]

Hi Phoenix,

wow fett, vielen Dank dafür :thumb:. Der Punkt, an dem ich gerade stocke ist, dass die ID's in der Ausgangsliste nicht eindeutig sind - sie geben sozusagen nur die Tiefe vor. Die Reihenfolge aber schon!

[Phoenix]

Inwiefern sind die ID's nicht eindeutig?

Wenn die Reihenfolge passt, dann nimm doch einfach ne klassische Zählerschleife über (i = 0; i < list.Count; i++) und benutz den index als ID.