1. Введение
Печать — очень распространенный метод визуализации структур данных. Однако это может быть сложно, когда дело доходит до деревьев, из-за их иерархической природы.
В этом руководстве мы изучим некоторые методы печати для двоичных деревьев в Java.
2. Древовидные диаграммы
Несмотря на ограничения рисования с использованием только символов на консоли, существует множество различных форм диаграмм для представления древовидных структур. Выбор одного из них в основном зависит от размера и сбалансированности дерева.
Давайте рассмотрим некоторые из возможных типов диаграмм, которые мы можем распечатать:
Но мы объясним практический, который также легче реализовать. Принимая во внимание направление, в котором растет дерево, мы можем назвать его горизонтальным деревом :
Поскольку горизонтальное дерево всегда течет в том же направлении, что и текст , у нас есть некоторые преимущества выбора горизонтальной диаграммы по сравнению с другими:
- Мы также можем визуализировать большие и несбалансированные деревья.
- Длина значений узла не влияет на структуру отображения
- Его намного проще реализовать
Поэтому мы воспользуемся горизонтальной диаграммой и реализуем простой класс принтера двоичного дерева в следующих разделах.
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 :
Таким образом, со всеми отступами и указателями наша диаграмма приобрела прекрасную форму.
Однако у нас все еще есть несколько лишних строк, от которых нужно избавиться:
Когда мы смотрим на диаграмму, все еще есть символы в трех неправильных местах:
- Столбец дополнительных строк под корневым узлом
- Дополнительные строки под правым поддеревом
- Дополнительные строки под левым поддеревом, у которого нет правого родственного элемента
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 .