1. введение
Печать – очень распространенный метод визуализации структур данных. Однако это может быть сложно, когда речь заходит о деревьях, из-за их иерархической природы.
В этом уроке мы изучим некоторые методы печати двоичных деревьев в Java.
2. Древовидные диаграммы
Несмотря на ограничения рисования только символами на консоли, существует множество различных форм диаграмм для представления древовидных структур. Выбор одного из них в основном зависит от размера и баланса дерева.
Давайте рассмотрим некоторые из возможных типов диаграмм, которые мы можем распечатать:
Но мы объясним практический вариант, который также легче реализовать. Принимая во внимание направление, в котором растет дерево, мы можем назвать его горизонтальным деревом :
Поскольку горизонтальное дерево всегда течет в том же направлении , что и текст , у нас есть некоторые преимущества в выборе горизонтальной диаграммы по сравнению с другими:
- Мы также можем визуализировать большие и несбалансированные деревья
- Длина значений узлов не влияет на структуру отображения
- Это гораздо проще реализовать
Поэтому мы перейдем к горизонтальной диаграмме и реализуем простой класс принтера двоичного дерева в следующих разделах.
3. Модель бинарного дерева
Прежде всего, мы должны смоделировать базовое двоичное дерево, которое мы можем сделать всего с помощью нескольких строк кода.
Давайте определим простую Модель бинарного дерева класс:
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. Принтер двоичного дерева
Конечно, нам нужен отдельный класс, чтобы сохранить нашу Модель бинарного дерева чистой ради Принципа единой ответственности .
Теперь мы могли бы использовать шаблон посетителя, чтобы дерево обрабатывало иерархию, а наш принтер просто обрабатывал печать. Но для этого урока мы будем держать их вместе, чтобы все было просто.
Таким образом, мы определяем класс с именем Binary Tree Printer и начинаем его реализацию.
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());
}
}
Кроме того, мы также обновляем print метод:
public void print(PrintStream os) {
StringBuilder sb = new StringBuilder();
traversePreOrder(sb, "", "", this.tree);
os.print(sb.toString());
}
Итак, давайте снова протестируем наш Принтер двоичного дерева :
Таким образом, со всеми дополнениями и указателями наша диаграмма сложилась красиво.
Тем не менее, у нас все еще есть несколько дополнительных строк, от которых нужно избавиться:
Когда мы смотрим на диаграмму, все еще есть символы в трех неправильных местах:
- Столбец дополнительных строк под корневым узлом
- Дополнительные строки под правым поддеревом
- Дополнительные строки под левым поддеревом, у которого нет правого родного брата
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. A кроме того, мы добавим новый параметр имеет правильный брат для правильной реализации предыдущих строк:
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);
}
}
Кроме того, нам нужно небольшое изменение в нашем методе print :
public void print(PrintStream os) {
os.print(traversePreOrder(tree));
}
Наконец, наша диаграмма сформировалась в красивую форму с чистым выводом:
6. Заключение
В этой статье мы узнали простой и практичный способ распечатать двоичное дерево в Java .
Все примеры этой статьи и дополнительные тестовые примеры доступны на GitHub .