¿Cómo mostrar la estructura de datos planos en una estructura de datos jerárquica (Java)?

Question

Recientemente me he enfrentado a esta pregunta en una prueba práctica para un trabajo.

Supongamos que se le da una estructura plana de datos de esta manera:

**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 

Y desde la estructura de datos plana por encima queremos mostrar algo así como la estructura de árbol jerárquico a continuación.

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

Entonces Si añado otra entrada a mi matriz como:

11     Test    3 

entonces debería mostrar Test entrada justo debajo 21inch.

Así que para este tipo de cosas actualmente estoy usando ArrayList y he podido atravesar hasta el segundo nivel pero no puedo hacerlo para el tercer nivel. Entonces, ¿cuál es la manera perfecta de hacer esto?

Gracias

EDIT:

me pidieron para construir este concepto utilizando únicamente aplicaciones Java basado en DOS.

Answer 1

He aquí algunos ejemplos de código que los enumera en una jerarquía utilizando la recursividad. La clase Item tiene una lista de hijos. El truco es agregar nuevos hijos al padre correcto. Aquí está el método que creé para hacer esto:

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; 
} 

Probablemente haya una manera más eficiente, pero esto funciona.

Entonces, cuando se desea añadir nuevos elementos a su jerarquía, hacer algo como esto:

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); 
} 

Para la pantalla real, que sólo tiene que pasar en un "nivel ficha" que dice qué tan lejos a la pestaña de , entonces se incrementará para cada niño como éste:

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(); 
} 

lo que me da esto:

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

Answer 2

Puede tener un diseño inspirado en Swing .

EDITAR Cuando digo eso, quiero decir que usted podría utilizar una clase que implementa una interfaz de lo mismo; Tenga en cuenta que puede llegar incluso a utilizar directamente esta interfaz, ya que Swing es parte de JRE estándar y está disponible en todos los lugares donde Java está disponible.

Además, como es una interfaz (y no una clase), es solo una forma de estructurar sus llamadas. Como consecuencia, puede usarlo fácilmente en una aplicación basada en consola.

Answer 3

Usando su ArrayList como entrada se necesitará un método recursivo para imprimir todos los nodos en una representación jerárquica/de árbol.

Si no está utilizando recursividad, esta podría ser la razón por la que no puede ir a niveles superiores al segundo que menciona.

Algunos enlaces en la recursividad:

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

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

Answer 4

para ser ef ciente, me gustaría crear algo como esto:

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)); 
    } 
} 

descargo usual: Este código es la parte superior de mi cabeza, no está comprobado.

Si estuviera haciendo esto para una aplicación real, incluiría la comprobación de errores y sin dudas todo tipo de cosas periféricas.

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; 
    } 
}