Flache Organisationsstruktur zu Baumansicht in java

Question

ich meine Organisationsstruktur haben, wie unten angegeben -

 T1 
|'''' ''''| 
T2   T3 
| 
T4 

in der Datenbank gespeichert, wie -

+----+---------+-----------+-----------+ 
| ID | TEAM_ID | PARENT_ID | TEAM_NAME | 
+----+---------+-----------+-----------+ 
| 1 |  1 |   1 | T1  | 
| 2 |  2 |   2 | T2  | 
| 3 |  2 |   1 | T2  | 
| 4 |  3 |   1 | T3  | 
| 5 |  3 |   3 | T3  | 
| 6 |  4 |   4 | T4  | 
| 7 |  4 |   2 | T4  | 
| 8 |  4 |   1 | T4  | 
+----+---------+-----------+-----------+ 

Und ich möchte die oben Baum neu bauen aus flache Daten in der Tabelle oben angegeben.

Mein aktueller Ansatz ist -

Map<Long, List<TeamHierarchy>> tree = new HashMap<>(); 
     for (TeamHierarchy n : flatTeamStructure) { 
      if (n.getParentTeamId() == n.getTeamId()) { 
       if (!tree.containsKey(n.getParentTeamId())) { 
        tree.put(n.getParentTeamId(), new ArrayList<TeamHierarchy>()); 
       } 
      } else { 
       if (!tree.containsKey(n.getParentTeamId())) { 
        tree.put(n.getParentTeamId(), new ArrayList<TeamHierarchy>()); 
       } 
       tree.get(n.getParentTeamId()).add(n); 
      } 
     } 

Was nicht ganz korrekt ist, weil ich T4 auch in T1 Kind bekommen. Ich möchte nur sofort Kind haben. Jeder Vorschlag ohne Rekursion wäre hilfreich.

Answer 1

Ich bin mir nicht sicher, es ist der effizienteste Weg, aber es sollte funktionieren. Ich würde versuchen, jede Team-ID ihrem richtigen Elternteil zuzuordnen. Die Schwierigkeit hier ist Ihre Tabelle enthält redundante Informationen, so dass Sie in der Lage sein müssen, es auszusortieren.

Die Idee ist es, den Baum von der Wurzel aus rekursiv zu erstellen, indem man den Elternbaum modifiziert, wenn man einen besseren Baum tiefer findet. Hier ist ein schnelles Beispiel-Standalone-Programm, das Sie in Gang bringen sollte.

public class TestTree { 
    private static List<Entry> entries = new ArrayList<Entry>(); 

    public static void main(String[] args) throws Exception { 
     // simulate the DB entries 
     entries.add(new Entry(1, 1, 1, "T1")); 
     entries.add(new Entry(2, 2, 2, "T2")); 
     entries.add(new Entry(3, 2, 1, "T2")); 
     entries.add(new Entry(4, 3, 1, "T3")); 
     entries.add(new Entry(5, 3, 3, "T3")); 
     entries.add(new Entry(6, 4, 4, "T4")); 
     entries.add(new Entry(7, 4, 2, "T4")); 
     entries.add(new Entry(8, 4, 1, "T4")); 

     // the root is the one entry with no parent other than self 
     int root = 1; 

     // map all relationships to the root 
     Map<Integer, Integer> tree = new HashMap<Integer, Integer>(); // ID -> parent ID 
     buildTree(tree, root); 

     System.out.println(tree); 

     // From this Map, it should be pretty obvious how to build the tree. 
    } 

    private static void buildTree(Map<Integer, Integer> tree, int parentId) { 
     boolean dirty = false; 
     for(Entry entry : entries) { 
      if(entry.parentId == parentId && entry.teamId != parentId) { 
       tree.put(entry.teamId, parentId); 
       dirty = true; 
      } 
     } 

     if(dirty) { 
      // Continue building the tree from each node that was updated 
      for(Integer nodeId : tree.keySet()) { 
       if(tree.get(nodeId) == parentId) buildTree(tree, nodeId); 
      } 
     } 
    } 

    private static class Entry { 
     int id; 
     int teamId; 
     int parentId; 
     String teamName; 

     Entry(int id, int teamId, int parentId, String teamName) { 
      this.id = id; 
      this.teamId = teamId; 
      this.parentId = parentId; 
      this.teamName = teamName; 
     } 
    } 

aktualisieren

Für die rekursive Methode Hasser (und im Fall, dass Sie Baum so tief ist, dass es den Methodenaufruf Stapel sprengt):

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 
import java.util.Stack; 

public class TestTree { 
    private static List<Entry> entries = new ArrayList<Entry>(); 

    public static void main(String[] args) throws Exception { 
     // simulate the DB entries 
     entries.add(new Entry(1, 1, 1, "T1")); 
     entries.add(new Entry(2, 2, 2, "T2")); 
     entries.add(new Entry(3, 2, 1, "T2")); 
     entries.add(new Entry(4, 3, 1, "T3")); 
     entries.add(new Entry(5, 3, 3, "T3")); 
     entries.add(new Entry(6, 4, 4, "T4")); 
     entries.add(new Entry(7, 4, 2, "T4")); 
     entries.add(new Entry(8, 4, 1, "T4")); 

     // the root is the one entry with no parent other than self 
     int root = 1; 

     // map all relationships to the root 
     Map<Integer, Integer> tree = new HashMap<Integer, Integer>(); // ID -> parent ID 
     Stack<Integer> stack = new Stack<Integer>(); 

     stack.push(root); 
     do { 
      int parentId = stack.pop(); 

      if(buildTree(tree, parentId)) { 
       // Continue building the tree from each node that was updated 
       for(Integer nodeId : tree.keySet()) { 
        if(tree.get(nodeId) == parentId) stack.push(nodeId); 
       } 
      } 
     } while(!stack.isEmpty()); 

     System.out.println(tree); 

     // From this Map, it should be pretty obvious how to build the tree. 
    } 

    private static boolean buildTree(Map<Integer, Integer> tree, int parentId) { 
     boolean dirty = false; 
     for(Entry entry : entries) { 
      if(entry.parentId == parentId && entry.teamId != parentId) { 
       tree.put(entry.teamId, parentId); 
       dirty = true; 
      } 
     } 

     return dirty; 
    } 

    private static class Entry { 
     int id; 
     int teamId; 
     int parentId; 
     String teamName; 

     Entry(int id, int teamId, int parentId, String teamName) { 
      this.id = id; 
      this.teamId = teamId; 
      this.parentId = parentId; 
      this.teamName = teamName; 
     } 
    } 
}