Wie flache Datenstruktur in hierarchische Datenstruktur (Java) anzeigen?

Question

Ich habe diese Frage kürzlich in einem Praxistest für einen Job gestellt.

Angenommen, Sie eine flache Datenstruktur wie folgt angegeben:

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

nun aus der obigen Struktur flach Daten, die wir so etwas wie die unten hierarchische Baumstruktur angezeigt werden sollen.

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

Dann Wenn ich wie einen weiteren Eintrag in meine Array bin hinzugefügt:

11     Test    3 

dann sollte es nur unter 21inchTest Eintrag zeigen.

Also für diese Art von Sache verwende ich derzeit ArrayList und konnte bis zum zweiten Level durchqueren, kann aber nicht für das dritte Level tun. Was ist der perfekte Weg dafür?

Dank

EDIT:

ich gebeten wurde, nur dieses Konzept mit DOS-basierten Java-Anwendung zu erstellen.

Answer 1

Hier ist ein Beispielcode, der sie in einer Hierarchie Rekursion auflistet. Die Item-Klasse hat eine Liste von Children. Der Trick besteht darin, dem richtigen Elternteil neue Kinder hinzuzufügen. Hier ist die Methode, die ich erstellt, dies zu tun:

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

Es ist wahrscheinlich eine effizientere Art und Weise, aber das funktioniert.

Dann, wenn Sie neue Elemente der Hierarchie hinzufügen möchten, tun Sie etwas wie folgt aus:

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

Für die eigentliche Anzeige, die ich in einem „-Reiter Ebene“ nur passieren, das sagt, wie weit Registerkarte es dann wie folgt für jedes Kind erhöht:

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

Was gibt mir:

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

Answer 2

Sie könnten ein Design haben, das von Swing inspiriert ist.

BEARBEITEN Wenn ich das sage, meine ich, Sie könnten eine Klasse verwenden, die eine ebenfalls Schnittstelle implementiert; Sie können sogar direkt mit dieser Schnittstelle arbeiten, da Swing Teil der Standard-JRE ist und überall dort verfügbar ist, wo Standard-Java zur Verfügung steht.

Da es eine Schnittstelle (und keine Klasse) ist, ist es nur eine Möglichkeit für Sie, Ihre Anrufe zu strukturieren. Daher können Sie es problemlos in einer konsolenbasierten Anwendung verwenden.

Answer 3

Wenn Sie Ihre ArrayList als Eingabe verwenden, wird eine rekursive Methode benötigt, um alle Knoten in einer hierarchischen/Baumdarstellung zu drucken.

Wenn Sie keine Rekursion verwenden, kann dies der Grund dafür sein, dass Sie nicht auf höhere Ebenen als die zweite, die Sie erwähnen, gehen können.

Einige Links auf Rekursion:

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

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

Answer 4

Um eff iziente, würde ich so etwas wie dies erstellen:

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

Übliche Haftungsausschluss: Dieser Code aus der Spitze von meinem Kopf ist, völlig ungetestet.

Wenn ich dies für eine echte Anwendung tun würde, würde ich Fehlerprüfung und ohne Zweifel alle Arten von Peripherie-Zeug enthalten.

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