Вывод дерева в виде иерархии

38. Вывести дерево в виде иерархии

Условие задачи:
Дан список объектов Node. Каждый узел содержит:

собственный идентификатор id;
идентификатор родителя parentId;
список дочерних узлов.

Сначала необходимо связать узлы между собой по parentId, а затем реализовать метод printNode(), который рекурсивно выводит дерево в виде текстовой иерархии.

Код:

class Node {
    private final Integer id;
    private final Integer parentId;
    private final List<Node> childNode = new ArrayList<>();

    public Node(Integer id, Integer parentId) {
        this.id = id;
        this.parentId = parentId;
    }

    public Integer getId() {
        return id;
    }

    public Integer getParentId() {
        return parentId;
    }

    public List<Node> getChildNode() {
        return childNode;
    }
}

public class Test4 {

    public void linkNodes(List<Node> nodes) {
        Map<Integer, List<Node>> nodesByParent = nodes.stream()
                .filter(node -> node.getParentId() != null)
                .collect(Collectors.groupingBy(Node::getParentId));

        nodes.forEach(node ->
                node.getChildNode().addAll(
                        nodesByParent.getOrDefault(
                                node.getId(),
                                Collections.emptyList()
                        )
                )
        );
    }

    public String printNode(
            Node node,
            String prefix,
            String childrenPrefix
    ) {
        // TODO
    }
}

Для данных:

List<Node> nodes = List.of(
        new Node(1, null),
        new Node(2, 1),
        new Node(3, 1),
        new Node(4, 3),
        new Node(5, 3),
        new Node(6, 5)
);

ожидаемый результат:

1
├── 2
└── 3
    ├── 4
    └── 5
        └── 6

Спойлеры к решению

Подсказки

💡 Текущий узел нужно добавить как prefix + node.getId().
💡 Для каждого ребёнка необходимо определить, является ли он последним.
💡 Для обычного ребёнка используется ├──, для последнего — └──.
💡 Если после узла остаются соседи, для следующего уровня нужно продолжить вертикальную линию │.
💡 Обход удобно реализовать рекурсивно.

Решение

public String printNode(
        Node node,
        String prefix,
        String childrenPrefix
) {
    StringBuilder result = new StringBuilder();

    result.append(prefix)
            .append(node.getId())
            .append('\n');

    List<Node> children = node.getChildNode();

    for (int i = 0; i < children.size(); i++) {
        Node child = children.get(i);
        boolean isLast = i == children.size() - 1;

        String childPrefix =
                childrenPrefix
                        + (isLast ? "└── " : "├── ");

        String nextChildrenPrefix =
                childrenPrefix
                        + (isLast ? "    " : "│   ");

        result.append(
                printNode(
                        child,
                        childPrefix,
                        nextChildrenPrefix
                )
        );
    }

    return result.toString();
}

Вызов для корневого узла:

linkNodes(nodes);

System.out.print(
        printNode(nodes.get(0), "", "")
);

Для каждого дочернего узла определяется, последний ли он среди соседей:

boolean isLast = i == children.size() - 1;

Если после него есть другие узлы, используется:

├──

Если это последний ребёнок:

└──

Префикс для следующих уровней тоже зависит от этого.

Для непоследнего узла:

childrenPrefix + "│   "

вертикальная линия должна продолжаться, поскольку ниже ещё будут выводиться его соседи.

Для последнего:

childrenPrefix + "    "

продолжать вертикальную линию уже не нужно.

Например, для узла 3:

└── 3
    ├── 4
    └── 5
        └── 6

рекурсивный вызов автоматически накапливает необходимые отступы.

Каждый узел посещается один раз, поэтому сам вывод дерева работает за O(n), где n — количество узлов. Дополнительная память рекурсии — O(h), где h — высота дерева, не считая памяти под результирующую строку.