Algorithmus rekursiv durch einen Wald von Kindern gehen

Question

Bitte lassen Sie mich wissen, wenn dies schlechte Praxis oder in irgendeiner Weise eine schlechte Sache zu tun ist. Die Sache ist in meinem Programm Ich muss eine Methode machen, die durch das Wurzelelement und alle Kindknoten dieses Elements geht. Meine Elemente sind wie folgt aus:

|--ID--|--Parent--|--Additinal info--| 
| 1 | 0  | root element  | 
| 2 | 0  | root elemnet  | 
| 3 | 1  |child element of 1| 
| 4 | 1  |child element of 1| 
| 5 | 3  |child element of 3| 
-------------------------------------- 

Jetzt Wenn ich alle Kinder des Elements mit der ID empfangen will 1 (egal ob es hat 1000 Kinder oder auch nur 2 wie in diesem Beispiel) Ich mag, dass meine Methode, dies zu bringen Ich, aber ich bin mir nicht sicher, wie es geht? Alle diese Elemente befinden sich in einer Liste, und damit arbeite ich. Jedes Mal, wenn ich ein Element finde, muss ich prüfen, ob es Kinder hat, das gleiche gilt für die Kinder. Dies liegt daran, dass ich die Elemente in der richtigen Reihenfolge ausgeben muss. Ich habe darüber nachgedacht, es vielleicht so zu machen, dass ich zuerst eine Karte des Layouts male und dann die Karte für die Ausgabe verwende, aber ich bin irgendwie bei der Idee geblieben.

Irgendwelche Hinweise?

Answer 1

Wie viele dieser Baumprobleme ist das Zauberwort Rekursion. Die Reihenfolge, die Sie in der Tabelle beschreiben, ist die Reihenfolge nach IDs, die zuerst nicht genau der Tiefe oder Breite entspricht. Aber das ist in Ordnung, alles, was Sie brauchen, ist, die Knoten in eine Datenstruktur zu bringen, die sie in der von Ihnen gewünschten Reihenfolge zurückgibt. So ist der allgemeine Plan

• rekursiv 'gehen' den Baum, um alle Knoten zu finden; einzufügen, die die Knoten in einem Daten strcuture, die sie von ID
• Druck die bestellten Knoten

rekursiven Teil leicht anordnet ist auch:

• Start mit dem Wurzelknoten

• wenn Der Root-Knoten ist nicht in der Liste der Knoten, fügen Sie ihn

• nehmen Sie den ersten Kind-Knoten und das gleiche tun.

So etwas wie (Pseudo-Code):

dfs(node, nodelist): 
    if node not in nodelist 
     insert node in nodelist 
    for each child node n 
     dfs(n, nodelist) 

Answer 2

Es klingt wie ein Graph-Traversal-Problem, also würde ich diese Liste in eine Graphen-Struktur umwandeln (unter Verwendung von adjacency lists) und dann mit DFS oder BFS durchqueren.

Answer 3

Ihr Ansatz zur Darstellung hierarchischer Daten ist sehr ineffizient, wenn es darum geht, die Kindknoten eines Knotens zu durchlaufen. Sie müssen grundsätzlich eine Abfrage pro Knoten ausgeben.

Ich empfehle dringend, das verschachtelte Set-Modell (explained in this page) zu betrachten. Wenn Sie diesen Ansatz verwenden, können Sie die untergeordneten Elemente eines Knotens mit einer Abfrage durchsuchen, unabhängig von der Tiefe der Struktur oder der Anzahl der untergeordneten Elemente.

Answer 4

Sie haben so etwas wie zu implementieren, in der Liste Looping und für jedes der aktuellen Element der Liste, der Suche nach der Anzahl der Kinder, wie Die Anzahl der Elemente in der Liste, in der element.Parent = currentElementofList.Id. Wenn dieses Element Anzahl der untergeordneten Elemente größer als null ist, müssen Sie diese untergeordneten Elemente abrufen, und dies wird fortgesetzt, bis keine Elemente mehr in der Liste geloopt werden.

Answer 5

Was Sie brauchen, ist die adjacency list model.

Überprüfen Sie den Artikel für Details, aber diese Methode ermöglicht es Ihnen, Ihren Baum mit einer Abfrage abzurufen, und das Ergebnis ist leicht mit Ihrem Code zu durchlaufen. Dies ist die schnellste Methode für den Zugriff auf beliebige Bäume.