«1. Введение

Печать — очень распространенный метод визуализации структур данных. Однако это может быть сложно, когда дело доходит до деревьев, из-за их иерархической природы.

В этом уроке мы изучим некоторые методы печати для двоичных деревьев в Java.

2. Древовидные диаграммы

Несмотря на ограничения рисования только символами на консоли, существует множество различных форм диаграмм для представления древовидных структур. Выбор одного из них в основном зависит от размера и сбалансированности дерева.

Давайте рассмотрим некоторые из возможных типов диаграмм, которые мы можем распечатать:

Но мы объясним практический вариант, который также легче реализовать. Принимая во внимание направление, в котором растет дерево, мы можем назвать его горизонтальным деревом:

Поскольку горизонтальное дерево всегда течет в том же направлении, что и текст, у нас есть некоторые преимущества выбора горизонтальной диаграммы по сравнению с другими:

  1. We can visualize large and unbalanced trees as well
  2. The length of node values doesn’t affect the display structure
  3. It is much easier to implement

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

3. Модель бинарного дерева

Прежде всего, мы должны смоделировать базовое бинарное дерево, которое мы можем сделать всего несколькими строками кода.

Давайте определим простой класс BinaryTreeModel: 

public class BinaryTreeModel {

    private Object value;
    private BinaryTreeModel left;
    private BinaryTreeModel right;

    public BinaryTreeModel(Object value) {
        this.value = value;
    }

    // standard getters and setters

}

4. Пример тестовых данных

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

BinaryTreeModel root = new BinaryTreeModel("root");

BinaryTreeModel node1 = new BinaryTreeModel("node1");
BinaryTreeModel node2 = new BinaryTreeModel("node2");
root.setLeft(node1);
root.setRight(node2);
 
BinaryTreeModel node3 = new BinaryTreeModel("node3");
BinaryTreeModel node4 = new BinaryTreeModel("node4");
node1.setLeft(node3);
node1.setRight(node4);
 
node2.setLeft(new BinaryTreeModel("node5"));
node2.setRight(new BinaryTreeModel("node6"));
 
BinaryTreeModel node7 = new BinaryTreeModel("node7");
node3.setLeft(node7);
node7.setLeft(new BinaryTreeModel("node8"));
node7.setRight(new BinaryTreeModel("node9"));

~ ~~ 5. Принтер двоичного дерева

Конечно, нам нужен отдельный класс, чтобы поддерживать чистоту BinaryTreeModel в соответствии с принципом единой ответственности.

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

Итак, мы определяем класс BinaryTreePrinter и начинаем его реализовывать.

5.1. Обход в предварительном порядке

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

Следовательно, чтобы выполнить предварительный обход, нам нужно реализовать рекурсивный метод, который сначала посещает корневой узел, затем левое поддерево и, наконец, правое поддерево.

Давайте определим метод обхода нашего дерева: 

public void traversePreOrder(StringBuilder sb, BinaryTreeModel node) {
    if (node != null) {
        sb.append(node.getValue());
        sb.append("\n");
        traversePreOrder(sb, node.getLeft());
        traversePreOrder(sb, node.getRight());
    }
}

Далее, давайте определим наш метод печати: 

public void print(PrintStream os) {
    StringBuilder sb = new StringBuilder();
    traversePreOrder(sb, this.tree);
    os.print(sb.toString());
}

Таким образом, мы можем просто распечатать наше тестовое дерево: 

new BinaryTreePrinter(root).print(System.out);

Вывод будет список узлов дерева в порядке обхода: 

root
node1
node3
node7
node8
node9
node4
node2
node5
node6

5.2. Добавление ребер дерева

Чтобы правильно настроить нашу диаграмму, мы используем три типа символов: «————————————————————————————————————————————————————————————————————————————————————————————————— «» для визуализации узлов. Первые два из них предназначены для указателей, а последний — для заполнения ребер и соединения указателей.

Давайте обновим наш метод traversePreOrder, добавим два параметра в качестве заполнения и указателя и будем использовать символы соответственно: 

public void traversePreOrder(StringBuilder sb, String padding, String pointer, BinaryTreeModel node) {
    if (node != null) {
        sb.append(padding);
        sb.append(pointer);
        sb.append(node.getValue());
        sb.append("\n");

        StringBuilder paddingBuilder = new StringBuilder(padding);
        paddingBuilder.append("│  ");

        String paddingForBoth = paddingBuilder.toString();
        String pointerForRight = "└──";
        String pointerForLeft = (node.getRight() != null) ? "├──" : "└──";

        traversePreOrder(sb, paddingForBoth, pointerForLeft, node.getLeft());
        traversePreOrder(sb, paddingForBoth, pointerForRight, node.getRight());
    }
}

Также мы обновим метод печати: 

public void print(PrintStream os) {
    StringBuilder sb = new StringBuilder();
    traversePreOrder(sb, "", "", this.tree);
    os.print(sb.toString());
}

Итак, давайте протестируем наш BinaryTreePrinter снова:

Таким образом, со всеми отступами и указателями наша диаграмма приобрела прекрасную форму.

Тем не менее, нам все еще нужно избавиться от нескольких лишних линий:

Когда мы смотрим на диаграмму, мы все еще видим символы в трех неправильных местах:

  1. The column of extra lines under the root node
  2. The extra lines under the right subtree
  3. The extra lines under the left subtree which has no right sibling

5.3. Различные реализации для корневых и дочерних узлов

Чтобы исправить лишние строки, мы можем разделить наш метод обхода. Мы применим одно поведение к корневому узлу, а другое — к дочерним узлам.

Давайте настроим traversePreOrder только для корневого узла: 

public String traversePreOrder(BinaryTreeModel root) {

    if (root == null) {
        return "";
    }

    StringBuilder sb = new StringBuilder();
    sb.append(root.getValue());

    String pointerRight = "└──";
    String pointerLeft = (root.getRight() != null) ? "├──" : "└──";

    traverseNodes(sb, "", pointerLeft, root.getLeft(), root.getRight() != null);
    traverseNodes(sb, "", pointerRight, root.getRight(), false);

    return sb.toString();
}

Далее мы создадим еще один метод для дочерних узлов как traverseNodes. Кроме того, мы добавим новый параметр hasRightSibling для правильной реализации предыдущих строк: 

public void traverseNodes(StringBuilder sb, String padding, String pointer, BinaryTreeModel node, 
  boolean hasRightSibling) {
    if (node != null) {
        sb.append("\n");
        sb.append(padding);
        sb.append(pointer);
        sb.append(node.getValue());

        StringBuilder paddingBuilder = new StringBuilder(padding);
        if (hasRightSibling) {
            paddingBuilder.append("│  ");
        } else {
            paddingBuilder.append("   ");
        }

        String paddingForBoth = paddingBuilder.toString();
        String pointerRight = "└──";
        String pointerLeft = (node.getRight() != null) ? "├──" : "└──";

        traverseNodes(sb, paddingForBoth, pointerLeft, node.getLeft(), node.getRight() != null);
        traverseNodes(sb, paddingForBoth, pointerRight, node.getRight(), false);
    }
}

Кроме того, нам нужно небольшое изменение в нашем методе печати: 

public void print(PrintStream os) {
    os.print(traversePreOrder(tree));
}

Наконец, наша диаграмма приобрела красивую форму. с чистым выводом:

6. Заключение

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

Все примеры из этой статьи и дополнительные тестовые примеры доступны на GitHub.