Как отобразить плоскую структуру данных в иерархическую структуру данных (Java)?

Question

Я недавно сталкивался с этим вопросом в практическом тесте на работу.

Предположим, вам дана плоская структура данных, подобная этой:

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

Теперь из приведенной выше плоской структуры данныхмы хотим показать что-то вроде иерархической структуры ниже.

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

Тогда Если я добавляю еще одну запись в мой массив, например:

11                 Test               3

, тогда она должна показывать Test запись чуть ниже 21inch.

Так что для такого рода вещей я в настоящее время использую ArrayList и могу пройти до второго уровня, но не могу сделать это для третьего уровня.Итак, каков идеальный способ сделать это?

Спасибо

РЕДАКТИРОВАТЬ:

Меня попросили построить эту концепцию, используя только Java-приложение на основе DOS,

Answer 1

Вот пример кода, который перечисляет их в иерархии с использованием рекурсии.Класс Item имеет Список детей.Хитрость заключается в добавлении новых детей к нужному родителю.Вот метод, который я создал для этого:

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

Возможно, есть более эффективный способ, но он работает.

Затем, когда вы хотите добавить новые элементы в вашу иерархию,сделать что-то вроде этого:

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

Для фактического отображения я просто передаю «уровень табуляции», который говорит, как далеко вкладывать, а затем увеличивает его для каждого дочернего элемента следующим образом:

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

Что дает мне это:

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

Answer 2

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

Answer 3

У вас может быть дизайн, вдохновленный Swing TreeModel .

EDIT Когда я говорю это, я имею в виду, что вы можете использовать класс, реализующий аналогичный интерфейс;Обратите внимание, что вы можете даже пойти дальше, используя непосредственно этот интерфейс, поскольку Swing является частью стандартного JRE и доступен везде, где доступна стандартная Java.

Более того, поскольку это интерфейс (а не класс), онтолько способ структурировать ваши звонки.Как следствие, вы можете легко использовать его в консольном приложении.

Answer 4

Чтобы быть эффективным, я бы создал что-то вроде этого:

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

Обычный отказ от ответственности: этот код находится у меня на голове, полностью не проверен.

Если бы я делалэто для реального приложения, я бы включил проверку ошибок и, несомненно, всевозможные периферийные устройства.

Answer 5

Используя ваш ArrayList в качестве входных данных, потребуется рекурсивный метод для печати всех узлов в иерархическом / древовидном представлении.

Если вы не используете рекурсию, то это может быть причиной того, что вы не можете перейти на уровни вышечем второй, который вы упомянули.

Некоторые ссылки на рекурсию:

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

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