Как напечатать двоичную древовидную диаграмму

1. Введение

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

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

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

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

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

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

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

1. Мы также можем визуализировать большие и несбалансированные деревья.
2. Длина значений узла не влияет на структуру отображения
3. Его намного проще реализовать

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

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. Столбец дополнительных строк под корневым узлом
2. Дополнительные строки под правым поддеревом
3. Дополнительные строки под левым поддеревом, у которого нет правого родственного элемента

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 .