«1. Введение
Печать — очень распространенный метод визуализации структур данных. Однако это может быть сложно, когда дело доходит до деревьев, из-за их иерархической природы.
В этом уроке мы изучим некоторые методы печати для двоичных деревьев в Java.
2. Древовидные диаграммы
Несмотря на ограничения рисования только символами на консоли, существует множество различных форм диаграмм для представления древовидных структур. Выбор одного из них в основном зависит от размера и сбалансированности дерева.
Давайте рассмотрим некоторые из возможных типов диаграмм, которые мы можем распечатать:
Но мы объясним практический вариант, который также легче реализовать. Принимая во внимание направление, в котором растет дерево, мы можем назвать его горизонтальным деревом:
Поскольку горизонтальное дерево всегда течет в том же направлении, что и текст, у нас есть некоторые преимущества выбора горизонтальной диаграммы по сравнению с другими:
- We can visualize large and unbalanced trees as well
- The length of node values doesn’t affect the display structure
- 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 снова:
Таким образом, со всеми отступами и указателями наша диаграмма приобрела прекрасную форму.
Тем не менее, нам все еще нужно избавиться от нескольких лишних линий:
Когда мы смотрим на диаграмму, мы все еще видим символы в трех неправильных местах:
- The column of extra lines under the root node
- The extra lines under the right subtree
- 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.