Преобразование древовидной структуры в двумерный массив 'grid' в Java - PullRequest
Новая
       24

Преобразование древовидной структуры в двумерный массив 'grid' в Java

0 голосов
/ 08 января 2019

Я пытаюсь отобразить древовидную структуру в таблице и никак не могу разобраться с последним битом.

У меня довольно стандартный класс узлов (для ясности удалены методы и конструкторы), 

public class TreeNode<T> {

    private TreeNode<?>         parent;
    private T                   data;
    private List<TreeNode<?>>   children    = new ArrayList<>();

}

который может быть заполнен примерно так: 

TreeNode<String> grandchild1 = new TreeNode<>("Grandchild 1");
TreeNode<String> grandchild2 = new TreeNode<>("Grandchild 2");
TreeNode<String> grandchild3 = new TreeNode<>("Grandchild 3");
TreeNode<String> child1 = new TreeNode<>("Child 1");
child1.addChild(grandchild1);
child1.addChild(grandchild2);
TreeNode<String> child2 = new TreeNode<>("Child 2");
child2.addChild(grandchild3);
TreeNode<String> root = new TreeNode<>("Root");
root.add(child1);
root.add(child2);

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

[["Root", "Child 1", "Grandchild 1"],
 ["", "", "Grandchild 2"],
 ["", "Child 2", "Grandchild 3"]]

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

| Root   | Child 1    | Grandchild 1 |
|        |            | Grandchild 2 |
|        | Child 2    | Grandchild 3 |

Вот что я пробовал до сих пор: 

public List<List<String>> getData(TreeNode<?> root) {
    List<List<String>> data = new ArrayList<>();
    getData(data, root);
    return data;
}

private void getData(List<List<String>> data, TreeNode<?> node) {
    if (!node.isLeaf()) {
        for (TreeNode<?> child : node.getChildren()) {
            getData(data, child);
        }
    } else {
        data.add(getRow(currentNode));
    }
}

private List<String> getRow(TreeNode<?> node) {
    Deque<String> row = new LinkedList<>();
    TreeNode<?> currentNode = node;
    while (!currentNode.isRoot()) {
        row.addFirst(String.valueOf(currentNode.getData()));
        currentNode = currentNode.getParent();
    }
    return new ArrayList<>(row);
}

Хотя это рекурсивно собирает данные для отображения, очевидно, что данные будут повторяться, так как для каждой строки печатается их родительское значение, и я получу следующее: 

[["Root", "Child 1", "Grandchild 1"],
 ["Root", "Child 1", "Grandchild 2"],
 ["Root", "Child 2", "Grandchild 3"]]

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

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

Ответы [ 3 ]

0 голосов
/ 08 января 2019

Обход аналогичен ответу @Matteo Ugolotti, только другая глубина трейлинга и печать ведущего узла.

Для каждого узла вывести все дочерние элементы в одной строке рекурсивно. Когда строка печатается, каждый дочерний элемент (если он есть) только что напечатанных узлов также печатается рекурсивно.

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

Я удалил дженерики и сделал каждый узел String, чтобы можно было узнать длину каждого узла (используется для правильной печати столбцов). Вы можете создать метод в своем классе Node, который возвращает длину (общих) данных. 

public void printTree(Node<String> node, int depth, int columnSize) {
    // Print leaf
    if(node.children.size() == 0) {
        printNode(node, columnSize);
        System.out.print("|\n");
    } else {
        // Print current node
        printNode(node, columnSize);

        // Print all nodes of this level recursively
        printTree(node.children.get(0), depth + 1, columnSize);

        // Print all children current node recursively
        for (int i = 1; i < node.children.size(); i++) {
            printLeading(depth + 1, columnSize);
            printTree(node.children.get(i), depth + 1, columnSize);
        }
    }
}

public void printLeading(int depth, int columnSize) {
    // Print the leading white spaces of column at a certain depth
    // Each node (depth) takes the column size + 2 characters (= "| ")
    for (int i = 0; i < depth * columnSize + depth * 2; i++) {
        System.out.print(" ");
    }
}

public void printNode(Node<String> node, int columnSize) {
    int trailing = columnSize - node.getData().length();
    System.out.print("| " + node.data);

    // Print the leading white spaces in the column
    for (int i = 0; i < trailing; i++) {
        System.out.print(" ");
    }
}
0 голосов
/ 09 января 2019

Благодаря P. ван дер Лаан Мне удалось придумать довольно не элегантное решение. Если есть лучший или более «стандартный» способ добиться этого, я бы с удовольствием это услышал!

Итак, я создал класс для хранения вложенного списка и текущей позиции строки: 

public class NodeGrid {

    private List<List<String>>  data        = new ArrayList<>();
    private int                 currentRow  = 0;

    public void addData(String dataString) {
        while (data.size() <= currentRow) {
            data.add(new ArrayList<>());
        }
        data.get(currentRow).add(dataString);
    }

    public void newRow() {
        data.add(new ArrayList<>());
        currentRow++;
    }

    public List<List<String>> getData() {
        data.remove(currentRow); // the last row is deleted before retrieving since it will always be empty
        return data;
    }
}

Который затем может реализовать DFS таким же образом: 

private void getRowData(NodeGrid data, TreeNode<?> currentNode, int depth) {
    if (currentNode.isLeaf()) {
        data.addData(String.valueOf(currentNode.getData()));
        data.newRow();
    } else {
        data.addData(String.valueOf(currentNode.getData()));
        getRowData(data, currentNode.getChild(0), depth + 1);
        for (int i = 1; i < currentNode.getChildren().size(); i++) {
            for (int d = 0; d < depth + 1; d++) {
                data.addData("");
            }
            getRowData(data, currentNode.getChild(i), depth + 1);
        }
    }
}

Я не уверен, что это лучшее решение, и оно тоже не кажется очень эффективным (необходимо удалить последнюю добавленную пустую строку), но пока работает.

0 голосов
/ 08 января 2019

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

public void printTree(TreeNode<T> node, int depth) {
    // Print leaf
    if(node.children.size() == 0) {
      System.out.print(node.data);
      System.out.print("\n");
      return;
    } else {

      // Print current node
      System.out.print(node.data);

      // Print next nodes at this level
      printTree(node.children.get(0), depth + 1);

      // Print remaining nodes with leading white columns
      for (int i = 1; i < node.children.size(); i++) {
        for (int j = 0; j < depth; j++) {
          System.out.print("   |");
        }
        System.out.print(node.children.get(i);
        System.out.print("\n");
      }
    }
}
...