Erstellen untergeordnete Knoten mit Rekursion

Question

Ich versuche, eine Hierarchie aus flachen Daten zu erstellen. Ich habe folgende Node Definition:

public class Node { 
     public String name; 
     public List<Node> children = new ArrayList<>(); 
    } 

diese Daten Gegeben: [Person,Manager,Hourly,New], wo der Baum sein sollte wie:

Person 
    |--Manager 
     |--Hourly 
      |--New 

Ich habe versucht, die folgenden:

public void run() 
    { 
     List<List<String>> objects = new ArrayList<>(); 

     String[] str = {"Person","Manager","Hourly","New"}; 
     objects.add(Arrays.asList(str)) ; 

     String[] str2 = {"Person","Manager","Salary"}; 
     objects.add(Arrays.asList(str2)) ; 

     String[] str3 = {"Person","Manager","Salary", "New"}; 
     objects.add(Arrays.asList(str3)) ; 

     // Create a Node with the sequence 
     myNode = new Node(); 
     createNode(objects.get(0), 0, myNode, myNode); 
     LOG.debug(myNode.name); 
} 

Und mein createNode Methode ist:

public Node createNode(List<String> seq, Integer start, Node parentNode, Node childNode) 
    { 
     // do something and return a Node? 
    } 

Aber konzeptionell verstehe ich nicht, wie man die Struktur erhält, wenn Java Return-by-Value ist. Was füge ich zu createNode so, dass ich eine Manager- hinzufügen> Stunden-> Neue Hierarchie als Kind Person

Answer 1

Sie brauchen nicht sowohl einen Node Rückgabetyp und ein Node Argument für Ihr Verfahren.

Hier ist eine Möglichkeit, es zu tun:

//in run() 
myNode = new Node(); 
myNode.name = "Root"; 
createNode(objects.get(0), 0, myNode, myNode); 



public void createNode(List<String> seq, Integer start, Node parentNode) 
{ 
    Node childNode = new Node(); 
    childNode.name = seq[start]; 
    parentNode.children.Add(childNode); 
    createNode(seq, start+1, childNode); 
} 

Sie brauchen nichts von createNode() zurückzukehren - da Sie parentNode als Variable haben, können Sie die Dinge auf seine children Mitglied hinzuzufügen. Ein Aufruf an createNode() wird rekursiv untergeordnete Knoten hinzufügen, die Ihrem String-Array bis zum Ende folgen.

Eine andere Möglichkeit, es zu tun ist dies wie:

public Node createNode(List<String> seq, Integer start) 
{ 
    if (start >= seq.Length) { 
     return null; 
    } 
    Node node = new Node(); 
    node.name = seq[start]; 
    node.children.Add(createNode(seq, start+1); 

    return node; 
} 

In diesem Fall brauchen Sie nicht in node Referenzen passieren; Das Aufrufen von createNode() generiert ein neues Knotenobjekt, füllt seinen children-Baum rekursiv und gibt die neu generierte Knotenstruktur zurück.

Answer 2

Wie ich sehen kann, ist Ihre Definition von Knoten etwas ähnlich wie die Adjazenzliste im Diagramm. Fügen Sie im Zielknoten den zugehörigen Knoten in der Liste hinzu, die dem Zielknoten zugeordnet ist. Dies gilt für jeden Knoten, der zu allen Knoten gehört.

Für jedes Objekt, das zum Objekt-Array (Array-Parameter) in Ihrer createNode-Methode gehört, müssen Sie das Node-Objekt erstellen. übergeben Sie einfach ein String-Array und den Taeget-Knoten. Iterieren Sie die Liste und erstellen Sie einen Knoten. Fügen Sie den Knoten in der Liste hinzu.

Um Duplikate beim Erstellen eines Knotens zu vermeiden, fügen Sie sie in einer Karte hinzu. Der Schlüssel für die Karte sollte String und der Wert sollte ein Node-Objekt sein. Bevor Sie das Objekt des Knotens erstellen, versuchen Sie einfach, das Objekt aus der Karte zu holen, machen Sie das Objekt nur dann, wenn das Objekt nicht in der Karte gefunden wird (in diesem Fall erstellen und fügen Sie es der Karte hinzu). Falls das Objekt auf der Karte gefunden wird, wird es vom SAMEDO nicht neu erstellt.