Визуализация бинарного дерева java

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

Узнайте, как распечатать двоичную древовидную диаграмму.

1. введение

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

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

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

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

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

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

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

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

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

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)

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

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)

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

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

Тем не менее, у нас все еще есть несколько дополнительных строк, от которых нужно избавиться:

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

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. 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)

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

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

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

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

Источник

Русские Блоги

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

Интеллектуальная рекомендация

Алгоритм сортировки

Перепечатано и разобралось7-sevensКрупные парни, эта статья для того, чтобы я мог учиться и использовать ее только. Не используйте ее для других целей. Если она вам нужна, пожалуйста, свяжитесь.

P1251 Проблема плана салфетки

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

Показать серию разработки оборудования и видео программирования (3) —- 3D ERA

4, 3 -й эпоха В длинной реке научный и технологический прогресс является основной движущей силой человеческой цивилизации. Видеологии превратностей и мира меняются. Человеческие исследования и исследо.

Что такое Hadoop (объединить некоторые существующие документы)

Большие данные — это подавляющее слово, и, говоря о больших данных, неизбежно следует упомянуть Hadoop, что такое Hadoop и какую функцию он выполняет. Hadoop — это программная платформа с открытым исх.

TF Update/Tensor Tensor

TF.Assign (не прост в использовании, не используйте его. Пожалуйста, используйте метод tf.scatter_update) результат Помните после TF.Assign, этот объект больше не является переменной, поэтому следующи.

Источник

Реализация и визуализация бинарного дерева в Java

вместе с классом Diagramm и двоичным деревом для ориентации.

Поэтому, следуя тексту и рисункам, я должен реализовать конструктор, метод get-and insert для этого двоичного дерева.

public class BinaryTree < private Node root = null; private static class Node < private Integer key; private String value; private Node left = null; private Node right = null; public Node(Integer key, String value) < this.key = key; this.value = value; >> public boolean insert(Integer key, String value) < if (root == null) < root = new Node(key, value); return true; >else < return insert(root, key, value); >> private boolean insert(Node node, Integer key, String value) < if (key.equals(node.key)) < // duplicate return false; >else if (key < node.key) < if (node.left == null) < node.left = new Node(key, value); return true; >else < return insert(node.left, key, value); >> else if (key > node.key) < if (node.right == null) < node.right = new Node(key, value); return true; >else < return insert(node.right, key, value); >> return false; > // not tested, crass assumptions, public domain public String get(Integer key) < return get(root, key); // start search from the root. >public String get(Node node, Integer key) < String result = null; // Assume key is not found if (node.key.equals(key)) < // Key matches? This is the result. return node.value; >else < if (key < node.key && node.left != null) < // key is lower than // current node, // and there is a left // branch, keep // search from there. result = get(node.left, key); >else if (key > node.key && node.right != null) < // key is greater // than current // node, // and there is // a left // branch, // keep search // from there. // The key >// node.key is // arguably // redundant. result = get(node.right, key); > > return result; > 

Как я могу реализовать правильную основную функцию для тестирования? И сверху я должен визуализировать двоичное дерево с помощью graphviz и добавления метода в класс узла, который создает строку для точечного кода. Как это работает с Eclipses?

2 ответа

get Метод начнется с определенного узла в дереве и проверит, соответствует ли этот узел самому критерию. Если это так, он возвращает значение. Если нет, то он перейдет к соответствующей ветке и продолжит поиск.

// not tested, crass assumptions, public domain public String get(Integer key) < return get(root, key); // start search from the root. >public String get(Node node, Integer key) < String result = null; // Assume key is not found if (node.key.equals(key)) < // Key matches? This is the result. return node.value; >else < if (key < node.key && node.left != null) < // key is lower than current node, // and there is a left branch, keep // search from there. result = get(node.left, key); >else if (key > node.key && node.right != null) < // key is greater than current node, // and there is a left branch, // keep search from there. // The key >node.key is arguably // redundant. result = get(node.right, key); > > return result; > 

Если вы выберете процедурный подход, правильный способ сделать это будет следующим:

public class BinaryTree < private Node root = null; private static class Node < private Integer key; private String value; private Node left = null; private Node right = null; public Node(Integer key, String value) < this.key = key; this.value = value; >> public boolean insert(Integer key, String value) < if (root == null) < root = new Node(key, value); return true; >else < return insert(root, key, value); >> private boolean insert(Node node, Integer key, String value) < if (key.equals(node.key)) < // duplicate return false; >else if (key < node.key) < if (node.left == null) < node.left = new Node(key, value); return true; >else < return insert(node.left, key, value); >> else if (key > node.key) < if (node.right == null) < node.right = new Node(key, value); return true; >else < return insert(node.right, key, value); >> return false; > > 

Теперь сравните его с подходом ООП и выберите тот, который вам больше нравится:

public class BinaryTree < private Node root = null; private static class Node < private Integer key; private String value; private Node left = null; private Node right = null; public Node(Integer key, String value) < this.key = key; this.value = value; >private boolean insert(Integer key, String value) < if (key.equals(this.key)) < // duplicate return false; >else if (key < this.key) < if (left == null) < left = new Node(key, value); return true; >else < return left.insert(key, value); >> else if (key > this.key) < if (right == null) < right = new Node(key, value); return true; >else < return right.insert(key, value); >> return false; > > public boolean insert(Integer key, String value) < if (root == null) < root = new Node(key, value); return true; >else < return root.insert(key, value); >> > 

Решение простое. Для операции вставки:

1. Если в дереве еще нет корня, создайте его.
2. В противном случае добавьте новое значение в корневой узел.

Вставка значения в некоторый узел (начиная с корневого):

1. Если ключ узла равен вставленному ключу =>, у нас есть дубликат, и мы не будем продолжать.
2. Если вставленный ключ меньше ключа узла, выполните:
   1. Если левого поддерева нет, создайте новый узел и назначьте его как левого потомка.
   2. Если левое поддерево уже существует, рекурсивно добавьте в него новое (ключ, значение).

   Источник