JavaRush/Java блог/Архив info.javarush/Как использовать рекурсию для создания "Mind Map" и вывод...
artur-ant
30 уровень

Как использовать рекурсию для создания "Mind Map" и вывода содержимого. Мой успешный опыт.

Статья из группы Архив info.javarush
участников

Приветствую!

Хочу поделиться с вами своим опытом по применению рекурсии и создании структур данных на ее основе. Думаю, прежде всего, эта статья будет интересна новичкам. Таким же как я :)
Введение
Недавно я захотел создать для себя эдакий инструмент, который помогал бы мне (и вдруг еще кому-то) в моих рассуждениях, в разбиении чего-то большого на маленькие детали так, чтобы можно было потом увидеть эту структуру. Я помнил, что есть такие штуки как Mind Map и есть структура данных дерево. Тогда я задумался над тем, как ее создать, эту структуру. К тому же мне нужен проект для демонстрации своих умений и для практики. В моем распоряжении были HashMap, ArrayList. И все бы ничего, но что если мне потребуется писать такое количество элементов, которое я не знаю изначально. Тогда я решил использовать рекурсию. Рекурсия вообще интересная штука, которую я не понимал. Как это функция вызывает себя, если ей для вызова себя надо вызвать функцию, которой для вызова ..... :) В общем не сразу укладывалось в понимании. Но я знал, что в рекурсии можно глубоко и далеко погружаться. А это было то, что надо. Я буду создавать пункты и ветки до тех пор, пока не скажу "хватит", а потом структура развернется и перейдет к следующему пункту. В голове все рисовалось понятно. А вот с реализацией я помучался. Проблема еще в том, что я работаю и уделять много времени не мог. Делал урывками. И с первого раза не получилось ничего. Сходу рекурсия отказалась погружаться, да и возвращалась она не туда куда я задумывал изначально. Тогда я стал вручную создавать HashMap, чтобы понять строение. Хватило пары веток для понимания. Решил, что буду создавать структуру вида HashMap(). В Object я смогу спокойно поместить такую же карту, и также спокойно вытащить ее оттуда (прежде я протестировал это предположение на кусочке кода :) новичок же :) ) После этого я создал первый метод, который погружался в глубину и возвращался туда, откуда его запустили. Если бы я был шаманом, то непременно пустился бы в пляс вокруг костра с бубном под луной :) Так я радовался :) Все круто! Но этого же недостаточно. А что. если у меня будет несколько вариантов, каждый из которых надо расписать "вниз"? И что, если каждый из нижних вариантов может расходиться еще в стороны? Вот это загадка. Тут я помучался. Я столкнулся с тем, что не понимаю, что необходимо делать. И это сильно печалило. На день я забросил все это дело. Но потом я подумал, что я уже умею создавать одиночные ветки, тогда я буду создавать их там где мне необходимо. Тогда я создал метод, который аналогично предыдущему расширялся горизонтально до тех пор, пока я не скажу "стоп". И получилось :) Уже поднаторев в рекурсии я создал методы, который создавал "зримую" версию моей структуры. Один из методов просто выводил в консоль структуру так, что была видна вложенность. А второй метод был интересней. Я добавил HTML тегов , чтобы я мог симпатично вывести в HTML файл. В итоге я создал основу, на которую собираюсь навесить работу в WEB. Подключить базу данных для сохранения этой всей стрктуры. Хотелось бы еще придумать функцию сохранения при заполнении, чтобы можно было возвращаться к написанию. Уже что-то есть и это здорово. Этим опытом я и хочу поделиться с вами, друзья Джаварашовцы.
Продолжение
Задумка в плане структуры примерно такая (не в плане визуальности). Как использовать рекурсию для создания Теперь о практической части. Алгоритм, код. Все написано своими словами, могу и ошибиться в академических трактовках :) Алгоритм создания "дерева": 1.создаю карту 2.добавляю в нее первый элемент, предварительно считав имя для этого первого элемента 3.спрашиваю о том, какие ветки у этого элемента 4.когда ветки кончаются (стоп-слово "no") перехожу к первому из вариантов и начинаю строить аналогичную структуру для этого элемента (пункты 1 - 3) 5.когда на последнем из элементов ставлю стоп-слово, тогда создание HashMap-ы заканчивается Затем я строю из имен узлов дерева строку с HTML тегами. Полученную строку вывожу в консоль. public class Main { static String consoleEncoding = "UTF-8"; //для корректного вывода в консоль Linux и IDEA // static String consoleEncoding = "Cp866"; //для корректного вывода в консоль Windows public static void main (String[] args) throws Exception { //создал основную карту HashMap map = new HashMap<>(); //поместил в нее первый элемент HashMap map0 = new HashMap<>(); PrintStream systemOut = System.out; PrintStream printStream = new PrintStream(System.out, true, consoleEncoding); System.setOut(printStream); //начал заполнение с корня System.out.println("Что хочешь расписать по частям, разобрать? Что хочешь сделать?"); Scanner scanner = new Scanner(System.in); String answer1 = scanner.nextLine(); //поместил корень в основную карту map.put(answer1, map0); //поехали заполнять ветками (метод для работы "в ширину") addBranchWithDialog(map0); String toHTML = mapToHTML(map); // строка для HTML System.out.println(toHTML); System.setOut(systemOut); printMap(map, 0); // вывод на консоль scanner.close(); } } В HTML вывод получается примерно такой. Количество вложенностей зависит только от фантазии :)

  • ВРЕМЯ
    • дни недели
      • вторник
        • среда
          • пятница
            • понедельник
              • четверг
                • воскресенье
                  • поработал - отдохни :)
                  • суббота
                  • времена года
                    • осень
                      • весна
                        • лето
                          • зима
                          • время суток
                            • вечер
                              • день
                                • ночь
                                  • утро
                                  • длинный текст
                                    • Стандартно обычно пишут Lorem upsum. Но я так поступать не буду:) Тут будет просто длинная строка в которой не может быть энтеров, иначе перейдем к следующему элементу. Изначально не рассчитывалось на длинные строки и большие блоки

                                  Вывод в консоль более прозаичен ВРЕМЯ дни недели вторник среда пятница понедельник четверг воскресенье поработал - отдохни :) суббота времена года осень весна лето зима время суток вечер день ночь утро длинный текст Стандартно обычно пишут Lorem upsum. Но я так поступать не буду:) Тут будет просто длинная строка в которой не может быть энтеров, иначе перейдем к следующему элементу. Изначально не рассчитывалось на длинные строки и большие блоки
                                  Методы
                                  Метод addBranchWithDialog() начинает спрашивать имена подпунктов, и эти имена добавляет в ArrayList пока не будет стоп-слова "no" Затем по всем элементам списка по порядку начинает создавать ветки "вниз" messageRecurs() Метод по добавлению "вниз" сам в свою очередь сразу начинает использовать метод addBranchWithDialog(), который /** * static method to create branches in width. horizontal growth * @param map where add new branches * @throws IOException */ public static void addBranchWithDialog(HashMap map) throws IOException { System.out.println("Что-то для этого надо сделать? Если надо то что? "); BufferedReader reader = new BufferedReader(new InputStreamReader(System.in, consoleEncoding)); String data = reader.readLine(); ArrayList answers = new ArrayList<>(); while (!"no".equalsIgnoreCase(data)) { answers.add(data); System.out.println("Что-то еще? "); data = reader.readLine(); } for (String answer: answers) { map.put(answer, messageRecurs(answer)); } } /** * static method for creating HashMap, where each of all elements has into yourself another map. Uses recursion * increase in depth * @return HashMap * @throws IOException */ public static HashMap messageRecurs(String data) throws IOException { HashMap hashMap = new HashMap<>(); System.out.println(data + "."); //чтобы видеть для какой ветки сейчас идет добавление веток в ширину addBranchWithDialog(hashMap); return hashMap; } Методы по выводу информации /** * print map structure to console using custom delimiter "delim" * @param map to print * @param n start from */ public static void printMap (HashMap map, int n) { StringBuilder builder = new StringBuilder(""); String delim = " "; for (int i = 0; i < n; i++) { builder.append(delim); } String prefix = builder.toString(); String result = ""; for (Map.Entry pair : map.entrySet()) { String key = pair.getKey(); result = prefix + key; HashMap value = (HashMap) pair.getValue(); System.out.println(result); printMap(value, n + 1); } } /** * method for adding HTML tags to map's elements * in this case that is tag
                                  * * now there's some problem with encoding in this method. * need to create a html template for print out. to add "charset=utf-8" * @param hashMap our main map * @return String to view */ public static String mapToHTML(HashMap hashMap) { StringBuilder builder = new StringBuilder(); builder.append("
                                    "); for (Map.Entry pair: hashMap.entrySet()) { String key = pair.getKey(); HashMap value = (HashMap) pair.getValue(); builder.append("
                                  • "); builder.append(key); builder.append(mapToHTML(value)); builder.append("
                                  • "); } builder.append("
                                  "); return builder.toString(); }
                                  Еще один пример строения карты:

                                  • Хочу стать Java программистом
                                    • Изучать дополнительные материалы
                                      • делать свои проекты
                                        • начать воплощать свои идеи в жизнь.
                                          • широко открыть глаза и уши и смотреть в чем нуждаются люди (Так был создан Facebook)
                                        • Хорошо учиться на JavaRush
                                          • попасть на стажировку
                                            • дойти до 30-го уровня и решить большинство задач
                                              • More practice
                                              • решить тестовое задание
                                                • сделать в срок
                                                • купить подписку Intership + или Mentor+
                                                  • вложить денежку в свое обучение
                                                • Каждый день решать задачи
                                                  • выделить минимум час времени на изучение материала и решение задач
                                                    • Предупредить своих. чтобы не беспокоили
                                                      • зарядить наконец-то телефон
                                                        • Написать всем СМС-ки
                                                    • Если есть вопросы, то задавать их на портале помощи help.javarush.ru
                                                      • в вопросе писать условие задачи
                                                        • Зарегистрироваться на портале
                                                          • пользоваться поиском

                                                      Напоследок
                                                      С удовольствием передаю свой опыт вам, друзья. Буду рад, если кому поможет. Буду рад пообщаться с умными людьми в комментах. Буду рад идеям :) p.s. Буду продолжать трудиться над этим проектом. Уже освоил создание jar-архивов и корректный вывод в консоль виндовс ( вообще отдельная история с этим Windows o_O). Поработаю над шаблоном для вывода в HTML. Научусь сохранять объекты в файл (сейчас как раз тема сериализации) До новых встреч!
                                                      Комментарии (11)
                                                      • популярные
                                                      • новые
                                                      • старые
                                                      Для того, чтобы оставить комментарий Вы должны авторизоваться
                                                      Joysi
                                                      Уровень 41
                                                      1 апреля 2016, 23:12
                                                      а далее можно изменить, чтобы хранить в узлах функции и в дальнейшем вызывать их.
                                                      artur-ant
                                                      Уровень 30
                                                      2 апреля 2016, 11:24
                                                      Сегодня обязательно опробую этот код.
                                                      Joysi
                                                      Уровень 41
                                                      2 апреля 2016, 22:29
                                                      Чуть подправил дерево, чтобы оно могло содержать узлы-функции наряду с узлами-данными:
                                                      public class Tree {
                                                          private static Node root; // Вынесли отдельно, чтобы обеспечить уникальность корня
                                                      
                                                          public static Node getRoot() {
                                                              return root;
                                                          }
                                                      
                                                          // Внутренний класс - узед
                                                          public static class Node {
                                                              private     Object data;
                                                              private     Node parent;
                                                              private     List<Object> children;
                                                              interface   NodeFunction {  void execute(); }  // реализуем простейшим способом запуск функций узлов
                                                      
                                                              NodeFunction nodeFunction;
                                                      
                                                              public Node(Node parent, Object data) {
                                                                  if (Tree.root != null && parent==null) {} // выкинем какую-нить ошибку при попытке создать снова корень
                                                                  if (data instanceof NodeFunction) {       // Если узел - функция ,пропишем ее
                                                                      this.nodeFunction = (NodeFunction) data;
                                                                      this.data         = "Function";
                                                                  }
                                                                  else {
                                                                      this.nodeFunction = null;             // пропишем простой узел данных
                                                                      this.data = data;
                                                                  }
                                                                  this.children   = new LinkedList<>();
                                                                  if (Tree.root != null) parent.children.add(this); // "пропишемся" у родителя
                                                              }
                                                      
                                                              @Override
                                                              public String toString() { // Вывод содержимого узла
                                                                  return "Node{" + "data=" + data + "}";
                                                              }
                                                          }
                                                      
                                                          // Конструктор (создаем один узел)
                                                          public Tree(Object rootData) {
                                                              root = new Node(null, rootData);
                                                          }
                                                      
                                                          // Добавим узел в дерево
                                                          public Node addNode(Node parentNode, Object nodeData) {
                                                              if (parentNode == null) return null;
                                                              return new Node(parentNode, nodeData);
                                                          }
                                                      
                                                          // Получим содержимое узла
                                                          public Object getNodeValue(Node node) {
                                                              if (node == null) return null;
                                                              return node.data;
                                                        
                                                      Joysi
                                                      Уровень 41
                                                      2 апреля 2016, 22:35
                                                      Прошу заранее простить за простоту примеров (мучает легкий депресняк). Но можно сделать узел «минимумы» — к ней приделать вагон функций, ищущих разными алгоритмами минимумы функций, а к каждому узлу-функции — узлы, содержащими статистику работы функций (кол-во вызовов, время выполнения, точность вычисления и т.п.). Как бы просто дайте волю фантазии.

                                                      P.S. Я только заканчиваю 23 левел, возможно, более опытные товарищи усмехнутся и заменят использование интерфейса для работы с функциями на лямбды, но я пока не очень в них. Но если кто опубликует замечания — буду только рад.
                                                      Byshevsky
                                                      Уровень 16
                                                      1 апреля 2016, 11:44
                                                      Какой то поток сознания. Практическая применяемость у то что ты «начал изучать» какая?
                                                      artur-ant
                                                      Уровень 30
                                                      1 апреля 2016, 11:50
                                                      Спасибо за комментарий.
                                                      Joysi
                                                      Уровень 41
                                                      1 апреля 2016, 14:30
                                                      Ценность, возможна, в конечном создании класса Tree. В Java (да и во многих других ЯП) нет стандартных реализаций для часто используемых структур: дерева, графа, конечных автоматов.
                                                      Возможно, наверное, что требования предъявляемые к таким структурам очень широки (в отличии от стандартных коллекций). Так что реализация своего дерева очень даже true.

                                                      Было бы забавно посмотреть на реализацию дерева/автомата, чтобы оно решало следующую задачу:
                                                      Для входного данного (пусть даже integer), в дереве нашло последовательность шагов по обработке именного для него( причем шаги могут быть и функциями и операторами) и 1) выдало результат 2)обновило само себя (в зависимости от результата выполнения шагов).

                                                      Например: ищем минимумы нескольких функций (или какие-то данные в файлах на своих критериях поиска) задав вагон «роботов», которых «сажаем» на дерево — и оно управляет ими до выдачи результата + обновляет само себя. Тогда создание задач сводится к минимуму — создаем «тупого» робота, занимающего минимальные объем в памяти и «кидаем в дерево» — пусть дальше «в обнимку» с ним шляется пока не выдаст результат (а возможно и дерево его убьет — потому что «тупой» (не нашел результат в приемлемое время или заблудился в дереве) или «обжора»(потребляет слишком много ресурсов самого дерева).
                                                      А если отслеживать частоту использования веток дерева и менять структуру для наиболее редких (чтобы ими пользовались чаще) — ммм прелестно выйдет…
                                                      А можно дереву на основе статистики и новые ветки отращивать…
                                                      Балансировка функционала дерева и робота + возможность роботов обмениваться инфой без участия дерева — тоже отдельная вкусная песня…

                                                      Мне было бы как минимум любопытно взглянуть на реализацию такого дерева =)
                                                      artur-ant
                                                      Уровень 30
                                                      1 апреля 2016, 17:18
                                                      Вот это да!
                                                      Ну почти что книга о приключениях маленького робота и кровожадного дерева :)

                                                      Мне было бы весьма интересно узнать как такое дерево соорудить :)
                                                      Joysi
                                                      Уровень 41
                                                      1 апреля 2016, 23:07
                                                      Пока для начала.
                                                      Фактически дерево — это набор вершин + набор соединяющих их направленных ребер подчиняющихся правилу:
                                                      — для каждой вершины существует ровно одно входящее ребро (но только для корневой вершины это входящее ребро=null)
                                                      — ребра не могут соединять одну и ту же вершину
                                                      — дерево всегда содержит корень (удобно для будущего конструктора не так ли :)
                                                      Естественно можно переделать правила, но тогда все выльется в ориентированный граф :) Можете с ним поработать — как Вам угодно

                                                      Делайте сразу универсальное решение, вершины могут содержать не только строки. Кол-во исходящих ребер может быть любым.
                                                      Костяк (как его нарастить «мясом» и обимплементить общепринятыми интерфейсами станет намного понятнее после последнего бонуса 20 левела, если еще не решали):

                                                      public class Tree {
                                                          private static Node root; // Вынесли отдельно, чтобы обеспечить уникальность корня
                                                      
                                                          public static Node getRoot() {
                                                              return root;
                                                          }
                                                      
                                                          public static class Node { // Внутренний класс - узел
                                                              private Object data;
                                                              private Node parent;
                                                              private List<Object> children;
                                                      
                                                              public Node(Node parent, Object data) {
                                                                  if (Tree.root != null && parent==null) {} // выкинем какую-нить ошибку при попытке создать снова корень
                                                                  this.parent     = parent;
                                                                  this.data       = data;                   // пропишем узел
                                                                  this.children   = new LinkedList<>();
                                                                  if (Tree.root != null) parent.children.add(this); // "пропишемся" у родителя
                                                              }
                                                      
                                                              @Override
                                                              public String toString() { // Вывод содержимого узла
                                                                  return "Node{" + "data=" + data + "}";
                                                              }
                                                          }
                                                      
                                                          public Tree(Object rootData) {// Конструктор (создаем один узел)
                                                              root = new Node(null, rootData);
                                                          }
                                                      
                                                          public Node addNode(Node parentNode, O
                                                      Joysi
                                                      Уровень 41
                                                      1 апреля 2016, 11:22
                                                      Все таки лучше оформить и создать отдельный класс MindMap (чтобы потом мог его использовать в любых местах) и по аналогии с big4 20 левелом «стандартизовать» его: уметь перебирать ветки или целиком mindmap итератором, клонировать его целиком, и отдельные ветки, добавлять-удалять узлы, искать значение по узлам, сохранять в HTML и было бы круто в дальнейшем сохранять в mm-формат (Freemind) фактически XML, freemind.sourceforge.net/wiki/index.php/File_format#XML_declaration

                                                      А можно и мясом нарастить со временем:
                                                      — сделать узлы дерева любым объектом (текст, бинарные данные( например изображение или иконка), ссылка на внешний файл или URL....)
                                                      — сделать ссылки второго типа (не основные) между узлами, для указания возможных связей.
                                                      — при удалении узла, сделать возможность «мягкого» удаления, чтобы можно было восстановить при необходимости (а в обычном режиме данные ветки не учитываются).
                                                      и т.п.
                                                      artur-ant
                                                      Уровень 30
                                                      1 апреля 2016, 11:48
                                                      Благодарю за дельные советы :)
                                                      Буду учиться дальше и смогу сделать несто подобное :)