Untitled
unknown
plain_text
5 months ago
9.8 kB
1
Indexable
Never
import java.util.*; // класс TreeNode представляет узел дерева class TreeNode { public int value; // значение узла public TreeNodeFrame left; // левый потомок public TreeNodeFrame right; // правый потомок public TreeNode(int value) { this.value = value; } public TreeNode(int value, TreeNodeFrame left, TreeNodeFrame right) { this.value = value; this.left = left; this.right = right; } //// метод проверки, является ли узел листом (не имеет потомков) //public boolean isLeaf() { // return left == null && right == null; // } // //// метод удаления левого потомка узла //public void removeLeft() { // left = null; // } // //// метод удаления правого потомка узла //public void removeRight() { // right = null; // } // //// метод получения левого потомка узла //public TreeNodeFrame getLeft() { // return left; // } // //// метод получения правого потомка узла //public TreeNodeFrame getRight() { // return right; // } // } public class Main { public static void main(String[] args) { TreeNodeFrame root1 = readTree("(3(4(0)(301))(5))"); printTreeGraphically(root1); addLeaves(root1); printTreeGraphically(root1); } public static TreeNodeFrame addLeaves(TreeNodeFrame root) { if (root == null) { return null; } if (root.left == null && root.right == null) { if (root.value % 2 == 0) { root.left = new TreeNodeFrame(1); } else { root.right = new TreeNodeFrame(-1); } } else { root.left = addLeaves(root.left); root.right = addLeaves(root.right); } return root; } // метод построения дерева из строки вида "(3(4(0()())(300()()))(5()()))" public static TreeNodeFrame readTree(String input) { // создаем стек для извлечения узлов дерева return TreeVisualizationApp.getTreeNodeFrame(input); } // метод вывода дерева на экран в виде строки public static void printTree(TreeNodeFrame node) { System.out.print(node.value); if (node.left != null || node.right != null) { System.out.print("("); if (node.left != null) { printTree(node.left); } System.out.print(","); if (node.right != null) { printTree(node.right); } System.out.print(")"); } } /** * Выводит дерево на экран в графическом виде. * * @param root Корневой узел дерева. */ public static void printTreeGraphically(TreeNodeFrame root) { int maxLevel = getMaxLevel(root); // Получаем максимальный уровень дерева printNodeInternal(Collections.singletonList(root), 1, maxLevel); // Рекурсивно выводим узлы на экран } /** * Рекурсивно выводит узлы на экран. * * @param nodes Список узлов для вывода. * @param level Текущий уровень дерева. * @param maxLevel Максимальный уровень дерева. */ private static void printNodeInternal(List<TreeNodeFrame> nodes, int level, int maxLevel) { // Если список пуст или все элементы равны null, то выходим из метода if (nodes.isEmpty() || isAllElementsNull(nodes)) return; int floor = maxLevel - level; // Вычисляем текущий уровень относительно максимального уровня int edgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0))); // Вычисляем количество линий-ребер на данном уровне int firstSpaces = (int) Math.pow(2, (floor)) - 1; // Вычисляем количество пробелов перед первым узлом на данном уровне int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1; // Вычисляем количество пробелов между узлами на данном уровне printWhitespaces(firstSpaces); // Выводим пробелы перед первым узлом на данном уровне List<TreeNodeFrame> newNodes = new ArrayList<>(); // Создаем новый список узлов для следующего уровня for (TreeNodeFrame node : nodes) { if (node != null) { System.out.print(node.value); // Выводим значение узла newNodes.add(node.left); // Добавляем левого потомка в новый список узлов newNodes.add(node.right); // Добавляем правого потомка в новый список узлов } else { newNodes.add(null); // Добавляем null в новый список узлов вместо отсутствующего узла newNodes.add(null); // Добавляем null в новый список узлов вместо отсутствующего узла System.out.print(" "); // Выводим пробел вместо отсутствующего узла } printWhitespaces(betweenSpaces); // Выводим пробелы между узлами на данном уровне } System.out.println(); // Переходим на следующую строку // Выводим линии-ребра на данном уровне for (int i = 1; i <= edgeLines; i++) { for (TreeNodeFrame node : nodes) { printWhitespaces(firstSpaces - i); // Выводим пробелы перед левой линией-ребром if (node == null) { printWhitespaces(edgeLines + edgeLines + i + 1); // Выводим пробелы вместо линий-ребер, если узел отсутствует continue; } if (node.left != null) System.out.print("/"); // Выводим левую линию-ребро, если она есть else printWhitespaces(1); // Выводим один пробел, если левого потомка нет printWhitespaces(i + i - 1); // Выводим пробелы между линиями-ребрами if (node.right != null) System.out.print("\\"); // Выводим правую линию-ребро, если она есть else printWhitespaces(1); // Выводим один пробел, если правого потомка нет printWhitespaces(edgeLines + edgeLines - i); // Выводим пробелы после правой линии-ребра } System.out.println(); // Переходим на следующую строку } printNodeInternal(newNodes, level + 1, maxLevel); // Рекурсивно выводим узлы следующего уровня } /** * Выводит заданное количество пробелов. * * @param count Количество пробелов для вывода. */ private static void printWhitespaces(int count) { for (int i = 0; i < count; i++) System.out.print(" "); } /** * Возвращает максимальный уровень дерева. * * @param node Корневой узел дерева. * @return Максимальный уровень дерева. */ private static int getMaxLevel(TreeNodeFrame node) { if (node == null) return 0; return Math.max(getMaxLevel(node.left), getMaxLevel(node.right)) + 1; } /** * Проверяет, являются ли все элементы списка null. * * @param list Список для проверки. * @return true, если все элементы списка равны null, иначе false. */ private static boolean isAllElementsNull(List list) { for (Object object : list) { if (object != null) return false; } return true; } } }