Come visualizzare la struttura di dati flat nella struttura gerarchica dei dati (Java)?

Question

Ho recentemente affrontato questa domanda in un test pratico per un lavoro.

Supponiamo si è data una struttura di dati piatto come questo:

**Category**   **Name**   **Parent** 
1     electronics   0 
2     Television   1 
3     21inch    2 
4     23inch    2 
5     LCD display   2 
6     player    1 
7     mp3player   6 
8     vcd player   6 
9     dvd player   6 
10     hd quality   8 

Ora dalla struttura dati sopra piatta Vogliamo mostrare qualcosa di simile al di sotto struttura gerarchica ad albero.

-Electronics 
| -Television 
| | -21 inch 
| | -23 inch 
| | -lcd display 
| -Player 
| | -mp3player 
| | -vcdplayer 
| | | -HD display 
| | -DVD player 

Poi Se sto aggiungendo un'altra voce alla mia serie come:

11     Test    3 

allora dovrebbe mostrare Test entrata appena sotto 21inch.

Quindi per questo genere di cose attualmente sto usando ArrayList e sono stato in grado di attraversare fino al secondo livello, ma non posso farlo per il terzo livello. Allora, qual è il modo perfetto per farlo?

Grazie

EDIT:

mi è stato chiesto di costruire questo concetto utilizzando solo applicazioni Java basato su DOS.

Answer 1

Ecco alcuni esempi di codice che li elenca in una gerarchia utilizzando la ricorsione. La classe Item ha una lista di bambini. Il trucco è aggiungere nuovi figli al genitore giusto. Ecco il metodo che ho creato per fare questo:

public Item getItemWithParent(int parentID){ 
    Item result = null; 
    if(this.categoryID == parentID){ 
     result = this; 
    } else { 
     for(Item nextChild : children){ 
      result = nextChild.getItemWithParent(parentID); 
      if(result != null){ 
       break; 
      } 
     } 
    } 
    return result; 
} 

Probabilmente esiste un modo più efficiente, ma funziona.

Poi, quando si desidera aggiungere nuovi elementi per la gerarchia, fare qualcosa di simile:

public void addItem(int categoryID, String name, int parentID) { 
    Item parentItem = findParent(parentID); 
    parentItem.addChild(new Item(categoryID, name, parentID)); 
} 
private Item findParent(int parentID) { 
    return rootNode.getItemWithParent(parentID); 
} 

Per la visualizzazione reale, ho solo passare un "livello di scheda" che dice quanto lontano alla scheda in , poi incrementarlo per ogni bambino in questo modo:

public String toStringHierarchy(int tabLevel){ 
    StringBuilder builder = new StringBuilder(); 
    for(int i = 0; i < tabLevel; i++){ 
     builder.append("\t"); 
    } 
    builder.append("-" + name); 
    builder.append("\n"); 
    for(Item nextChild : children){ 
     builder.append(nextChild.toStringHierarchy(tabLevel + 1)); 
    } 
    return builder.toString(); 
} 

il che mi dà questo:

-electronics 
    -Television 
     -21inch 
      -Test 
     -23inch 
     -LCD display 
    -player 
     -mp3player 
     -vcd player 
      -hd quality 
     -dvd player 

Answer 2

Si potrebbe avere un design ispirato a Swing .

EDIT Quando dico questo, voglio dire che potresti usare una classe che implementa un'interfaccia simile; Si può anche arrivare a utilizzare direttamente questa interfaccia, dato che Swing fa parte del JRE standard ed è disponibile ovunque sia disponibile Java standard.

Inoltre, poiché è un'interfaccia (e non una classe), è solo un modo per strutturare le chiamate. Di conseguenza, puoi facilmente utilizzarlo in un'applicazione basata su console.

Answer 3

Utilizzando ArrayList come input, sarà necessario un metodo ricorsivo per stampare tutti i nodi in una rappresentazione gerarchica/ad albero.

Se non si utilizza la ricorsione, questo potrebbe essere il motivo per cui non è possibile accedere a livelli superiori al secondo, che si menzionano.

Alcuni link ricorsione:

http://en.wikipedia.org/wiki/Recursion

http://www.java-samples.com/showtutorial.php?tutorialid=151

Answer 4

per essere eff icienti, mi piacerebbe creare qualcosa di simile:

public class Node 
{ 
    // My name 
    public String name; 
    // My first child. Null if no children. 
    public Node child; 
    // The next child after me under the same parent. 
    public Node sibling; 

    // The top node in the tree. 
    public static Node adam; 

    // Add first node to tree 
    public Node(String name) 
    { 
    this.name=name; 
    this.child=null; 
    this.sibling=null; 
    adam=this; 
    } 

    // Add a non-Adam node to the tree. 
    public Node(String name, Node parent) 
    { 
    // Copy my name. Easy part. 
    this.name=name; 
    // Make me the first child of my parent. The previous first child becomes 
    // my sibling. If the previous first child was null, fine, now my sibling is null. 
    // Note this means that children always add to the front. If this is undesirable, 
    // we could make this section a little more complicated to impose the desired 
    // order. 
    this.sibling=parent.child; 
    parent.child=this; 
    // As a new node, I have no children. 
    this.child=null; 
    } 
    // Print the current node and all nodes below it. 
    void printFamily(int level) 
    { 
    // You might want a fancier print function than this, like indenting or 
    // whatever, but I'm just trying to illustrate the principle. 
    System.out.println(level+" "+name); 
    // First process children, then process siblings. 
    if (child!=null) 
     child.printFamiliy(level+1); 
    if (sibling!=null) 
     sibling.printFamily(level); 
    } 
    // Print all nodes starting with adam 
    static void printFamily() 
    { 
    adam.printFamily(1); 
    } 
    // Find a node with a given name. Must traverse the tree. 
    public static Node findByName(String name) 
    { 
    return adam.findByName(name); 
    } 
    private Node findByNameFromHere(String name) 
    { 
    if (this.name.equals(name)) 
     return this; 
    if (child!=null) 
    { 
     Node found=child.findByNameFromHere(name); 
     if (found!=null) 
     return found; 
    } 
    if (sibling!=null) 
    { 
     Node found=sibling.findByNameFromHere(name); 
     if (found!=null) 
     return found; 
    } 
    return null; 
    } 
    // Now we can add by name 
    public Node(String name, String parentName) 
    { 
    super(name, findByName(parentName)); 
    } 
} 

diniego abituale: Questo codice è la parte superiore della mia testa, completamente testato.

Se facevo questo per un'applicazione reale, includevo il controllo degli errori e senza dubbio tutti i tipi di elementi periferici.

Answer 5

public class FileReader { 
    Map<Integer, Employee> employees; 
    Employee topEmployee; 
    class Employee { 
     int id; 
     int mgrId; 
     String empName; 
     List<Employee> subordinates; 
     public Employee(String id, String mgrid, String empName) { 
      try { 
       int empId = Integer.parseInt(id); 
       int mgrId = 0; 
       if (!"Null".equals(mgrid)) { 
        mgrId = Integer.parseInt(mgrid); 
       } 
       this.id = empId; 
       this.mgrId = mgrId; 
       this.empName = empName; 
      } catch (Exception e) { 
       System.out.println("Unable to create Employee as the data is " + id + " " + mgrid + " " + empName); 
      } 
     } 

     List<Employee> getSubordinates() { 
      return subordinates; 
     } 
     void setSubordinates(List<Employee> subordinates) { 
      this.subordinates = subordinates; 
     } 
     int getId() { 
      return id; 
     } 

     void setId(int id) { 
      this.id = id; 
     } 

     int getMgrId() { 
      return mgrId; 
     } 

    } 

    public static void main(String[] args) throws IOException { 
     FileReader thisClass = new FileReader(); 
     thisClass.process(); 
    } 

    private void process() throws IOException { 
     employees = new HashMap<Integer, Employee>(); 
     readDataAndCreateEmployees(); 
     buildHierarchy(topEmployee); 
     printSubOrdinates(topEmployee, tabLevel); 
    } 

    private void readDataAndCreateEmployees() throws IOException { 
     BufferedReader reader = new BufferedReader(new java.io.FileReader("src/main/java/com/springapp/mvc/input.txt")); 
     String line = reader.readLine(); 
     while (line != null) { 
      Employee employee = createEmployee(line); 
      employees.put(employee.getId(), employee); 
      if (employee.getMgrId() == 0) { 
       topEmployee = employee; 
      } 
      line = reader.readLine(); 
     } 
    } 

    int tabLevel = 0; 

    private void printSubOrdinates(Employee topEmployee, int tabLevel) { 
     for (int i = 0; i < tabLevel; i++) { 
      System.out.print("\t"); 
     } 
     System.out.println("-" + topEmployee.empName); 
     List<Employee> subordinates = topEmployee.getSubordinates(); 
     System.out.print(" "); 
     for (Employee e : subordinates) { 
      printSubOrdinates(e, tabLevel+1); 
     } 
    } 
    public List<Employee> findAllEmployeesByMgrId(int mgrid) { 
     List<Employee> sameMgrEmployees = new ArrayList<Employee>(); 
     for (Employee e : employees.values()) { 
      if (e.getMgrId() == mgrid) { 
       sameMgrEmployees.add(e); 
      } 
     } 
     return sameMgrEmployees; 
    } 

    private void buildHierarchy(Employee topEmployee) { 
     Employee employee = topEmployee; 
     List<Employee> employees1 = findAllEmployeesByMgrId(employee.getId()); 
     employee.setSubordinates(employees1); 
     if (employees1.size() == 0) { 
      return; 
     } 

     for (Employee e : employees1) { 
      buildHierarchy(e); 
     } 
    } 

    private Employee createEmployee(String line) { 
     String[] values = line.split(" "); 
     Employee employee = null; 
     try { 
      if (values.length > 1) { 
       employee = new Employee(values[0], values[2], values[1]); 
      } 
     } catch (Exception e) { 
      System.out.println("Unable to create Employee as the data is " + values); 
     } 
     return employee; 
    } 
}