Лабораторная работа 5.2 Java

package com.example.lab5_2;

import java.io.*;
import java.util.Scanner;

public class Main {
    public static Scanner scan = new Scanner(System.in);
    final static int A_MAKE_EMPTY_TREE = 1,
                     A_ADD_NODE = 2,
                     A_DELETE_NODE = 3,
                     A_SHOW_TREE = 4,
                     A_SHOW_IN_ORDER = 5,
                     A_INSERT_SUBTREE = 6,
                     A_OPEN = 7,
                     A_SAVE = 8,
                     A_EXIT = 9,
                     A_INSERT = 5,
                     A_SUBTREE_EXIT = 5,
                     INPUT = 1,
                     OUTPUT = 2,
                     MIN_VAL = 1,
                     MAX_VAL = 1000000;
    public static void main(String[] args) {
        Tree tree = new Tree();
        processTree(tree);
        scan.close();
    }

    private static void processTree(Tree tree) {
        int action;
        do {
            action = inputAction();
            performAction(action, tree);
        } while (action != A_EXIT);
    }

    private static void performAction(int action, Tree tree) {
        switch (action) {
            case A_MAKE_EMPTY_TREE:
                makeEmptyTree(tree);
                break;
            case A_ADD_NODE:
                addNode(tree);
                break;
            case A_DELETE_NODE:
                deleteNode(tree);
                break;
            case A_SHOW_TREE:
                showTree(tree);
                break;
            case A_SHOW_IN_ORDER:
                showTreeInOrder(tree);
                break;
            case A_INSERT_SUBTREE:
                insertSubtree(tree);
                break;
            case A_OPEN:
                openFile(tree);
                break;
            case A_SAVE:
                saveInFile(tree);
                break;
            case A_EXIT:
                break;
        }
    }

    private static void saveInFile(Tree tree) {
        boolean isFileCorrect;
        String filePath;
        filePath = inputFilePath(OUTPUT);
        saveTree(tree, filePath);
        System.out.println("\nДерево успешно сохранено.");
    }

    private static void saveTree(Tree tree, String filePath) {
        try (FileWriter fileWriter = new FileWriter(filePath)) {
            tree.printTreeInFile(fileWriter);
        } catch (IOException e) {
            System.out.println("\nОшибка! Невозможно открыть файл.");
        }
    }

    private static void openFile(Tree tree) {
        boolean isFileCorrect;
        String filePath;
        do {
            filePath = inputFilePath(INPUT);
            isFileCorrect = isFileCorrect(filePath);
        } while (!isFileCorrect);
        tree.makeEmptyTree();
        inputFromFile(filePath, tree);
    }

    private static void inputFromFile(String filePath, Tree inputTree) {
        int newVal;
        try (Scanner fileScanner = new Scanner(new FileReader(filePath))) {
            while (fileScanner.hasNext()) {
                newVal = Integer.parseInt(fileScanner.next());
                inputTree.insertNode(newVal);
            }
            fileScanner.close();
        } catch (FileNotFoundException e) {
            System.out.println("\nОшибка! Невозможно открыть файл.");
        }
    }

    private static void insertSubtree(Tree tree) {
        int insertVal;
        boolean isLeafNode;
        Tree subtree = new Tree();
        System.out.println("\nВведите листовую вершину, в которую хотите вставить поддерево:");
        do {
            insertVal = inputNum(MIN_VAL, MAX_VAL);
            isLeafNode = tree.isLeafNode(insertVal, tree.rootNode);
            if (!isLeafNode)
                System.out.println("\nДанное значение не является листовой вершиной. Повторите ввод:");
        } while (!isLeafNode);
        processSubtree(subtree, insertVal, tree);

    }

    private static void processSubtree(Tree subtree, int insertVal, Tree tree) {
        int subtreeAction;
        do {
            subtreeAction = inputSubtreeAction();
            performSubtreeAction(subtreeAction, subtree, insertVal, tree);
        } while (subtreeAction != A_SUBTREE_EXIT);
    }

    public static int inputSubtreeAction() {
        System.out.print("\n______________________________________________ \n1.Создать пустое дерево. \n2.Добавить элемент в дерево. \n3.Удалить элемент из дерева.\n4.Вывести дерево.\n5.Выйти. \n______________________________________________ \nВыберите действие: ");
        return inputNum(A_MAKE_EMPTY_TREE, A_SUBTREE_EXIT);
    }

    private static void performSubtreeAction(int subtreeAction, Tree subtree, int insertVal, Tree tree) {
        switch (subtreeAction) {
            case A_MAKE_EMPTY_TREE:
                makeEmptyTree(subtree);
                break;
            case A_ADD_NODE:
                addNodeInSubtree(subtree, tree);
                break;
            case A_DELETE_NODE:
                deleteNode(subtree);
                break;
            case A_SHOW_TREE:
                showTree(subtree);
                break;
            case A_SUBTREE_EXIT:
                insertSubtreeInTree(insertVal, subtree, tree);
                break;
        }
    }

    private static void insertSubtreeInTree(int insertVal, Tree subtree, Tree tree) {
        tree.insertSubtree(insertVal, subtree);
        System.out.println("\nДерево успешно вставлено.");
    }

    private static void addNodeInSubtree(Tree subtree, Tree tree) {
        int newValue;
        boolean isCorrect;
        System.out.println("\nВведите значение, которое хотите добавить [1; 1000000]:");
        do {
            isCorrect = true;
            newValue = inputNum(MIN_VAL, MAX_VAL);
            if (tree.findNode(newValue, tree.rootNode) != null) {
                System.out.println("\nОшибка! Данное значение присутствует в исходном дереве, добавление невозможно. Повторите ввод:");
                isCorrect = false;
            }
        } while (!isCorrect);
        subtree.insertNode(newValue);
        System.out.println("\nУспешно добавлено.");
    }

    private static void showTreeInOrder(Tree tree) {
        tree.printTreeInOrder();
    }

    private static void showTree(Tree tree) {
        tree.printTree();
    }

    private static void makeEmptyTree(Tree tree) {
        tree.makeEmptyTree();
        System.out.println("\nПустое дерево успешно создано.");
    }

    private static void deleteNode(Tree tree) {
        int delValue;
        System.out.println("\nВведите значение, которое хотите удалить [1; 1000000]:");
        delValue = inputNum(MIN_VAL, MAX_VAL);
        tree.delete(delValue);
        System.out.println("\nУспешно удалено.");
    }

    private static void addNode(Tree tree) {
        int newValue;
        System.out.println("\nВведите значение, которое хотите добавить [1; 1000000]:");
        newValue = inputNum(MIN_VAL, MAX_VAL);
        tree.insertNode(newValue);
        System.out.println("\nУспешно добавлено.");
    }

    public static int chooseElem(Tree tree) {
        boolean isCorrect;
        int num;
        String strValues = tree.treeToString(tree.rootNode);
        String[] values = strValues.split(" ");
        do {
            System.out.println("Выберите элемент дерева:");
            isCorrect = false;
            num = inputNum(1, 10);
            for (int i = 0; i < values.length; i++)
                if (num == Integer.parseInt(values[i]))
                    isCorrect = true;
            if (!isCorrect)
                System.out.println("Введенный элемент отсутствует в дереве.");
        } while (!isCorrect);
        return num;
    }

    public static int inputAction() {
        System.out.print("\n______________________________________________ \n1.Создать пустое дерево. \n2.Добавить элемент в дерево. \n3.Удалить элемент из дерева.\n4.Вывести дерево.\n5.Просмотреть дерево в порядке: узел, левая ветвь, правая ветвь.\n6.Вставить поддерево. \n7.Импортировать дерево из файла. \n8.Сохранить в файл текущее дерево. \n9.Выйти. \n______________________________________________ \nВыберите действие: ");
        return inputNum(A_MAKE_EMPTY_TREE, A_EXIT);
    }

    public static void writeTask(){
        System.out.println("Данная программа указывает место вставки указанного элемента из массива в двоичном дереве поиска.");
    }

    public static int inputNum(final int MIN_LIM, final int MAX_LIM) {
        int num = 0;
        boolean isIncorrect;
        do {
            isIncorrect = false;
            try {
                num = Integer.parseInt(scan.nextLine());
            } catch (NumberFormatException ex) {
                System.out.print("Ошибка! Введенное значение должно быть числом!\nПовторите ввод: ");
                isIncorrect = true;
            }
            if (!isIncorrect && (num < MIN_LIM || num > MAX_LIM)) {
                System.out.print("Ошибка! Введенное значение должно быть натуральным числом от " + MIN_LIM + " до " + MAX_LIM + "!\nПовторите ввод: ");
                isIncorrect = true;
            }
        } while (isIncorrect);
        return num;
    }

    public static String inputFilePath(final int TYPE_OF_PATH) {
        boolean isIncorrect;
        String path;
        if (TYPE_OF_PATH == INPUT)
            System.out.print("\nВведите путь к файлу для ввода данных: ");
        else if (TYPE_OF_PATH == OUTPUT)
            System.out.print("\nВведите путь к файлу для вывода данных: ");
        do {
            isIncorrect = false;
            path = scan.nextLine();
            File file = new File(path);
            if (TYPE_OF_PATH == INPUT) {
                if (!file.exists()) {
                    System.out.print("Ошибка! Данный файл не найден! Введите корректный путь к файлу и повторите попытку: ");
                    isIncorrect = true;
                }
                if (!isIncorrect && !path.endsWith(".txt")) {
                    System.out.print("Ошибка! Файл должен иметь расширение .txt! Корректный путь к файлу:");
                    isIncorrect = true;
                }
            }
        } while (isIncorrect);
        return path;
    }

    public static boolean isFileCorrect(String path) {
        boolean isIncorrect;
        int newVal;
        isIncorrect = false;
        String strValues = "";
        int nodeCount;
        try (Scanner fileScanner = new Scanner(new FileReader(path))) {
            while (fileScanner.hasNext())
                newVal = Integer.parseInt(fileScanner.next());
            fileScanner.close();
        } catch (NumberFormatException ex) {
            System.out.println("\nОшибка! В файле данные введены не по формату!");
            isIncorrect = true;
        } catch (FileNotFoundException e) {
            System.out.println("\nОшибка! Невозможно открыть файл.");
        }
        return !isIncorrect;
    }
}

package com.example.lab5_2;

import java.io.FileWriter;
import java.io.IOException;
import java.util.Stack;

public class Tree {
    public Node rootNode;

    public Tree() {
        rootNode = null;
    }

    public void insertNode(int value) {
        Node newNode = new Node();
        newNode.value = value;
        if (rootNode == null) {
            rootNode = newNode;
        } else {
            Node currentNode = rootNode;
            Node parentNode;
            while (true) {
                parentNode = currentNode;
                if (value == currentNode.value) {
                    return;
                } else if (value < currentNode.value) {
                    currentNode = currentNode.leftChild;
                    if (currentNode == null) {
                        parentNode.leftChild = newNode;
                        return;
                    }
                } else {
                    currentNode = currentNode.rightChild;
                    if (currentNode == null) {
                        parentNode.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

    public void printTree() {
        Stack globalStack = new Stack();
        globalStack.push(rootNode);
        int gaps = (int) Math.pow(2, findMaxDepth(rootNode));
        boolean isRowEmpty = false;
        String separator = "-----------------------------------------------------------------";
        System.out.println(separator);
        while (!isRowEmpty) {
            Stack localStack = new Stack();
            isRowEmpty = true;
            for (int j = 0; j < gaps; j++)
                System.out.print(' ');
            while (!globalStack.isEmpty()) {
                Node temp = (Node) globalStack.pop();
                if (temp != null) {
                    System.out.print(temp.value);
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);
                    if (temp.leftChild != null || temp.rightChild != null)
                        isRowEmpty = false;
                } else {
                    System.out.print("__");
                    localStack.push(null);
                    localStack.push(null);
                }
                for (int j = 0; j < gaps * 2 - 2; j++)
                    System.out.print(' ');
            }
            System.out.println();
            gaps /= 2;
            while (!localStack.isEmpty())
                globalStack.push(localStack.pop());
        }
        System.out.println(separator);
    }

    public void printTreeInOrder() {
        Stack globalStack = new Stack();
        globalStack.push(rootNode);
        int gaps = (int) Math.pow(2, findMaxDepth(rootNode));
        boolean isRowEmpty = false;
        String separator = "-----------------------------------------------------------------";
        System.out.println(separator);
        while (!isRowEmpty) {
            Stack localStack = new Stack();
            isRowEmpty = true;
            for (int j = 0; j < gaps; j++)
                System.out.print(' ');
            while (!globalStack.isEmpty()) {
                Node temp = (Node) globalStack.pop();
                if (temp != null) {
                    System.out.print(temp.value);
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        System.out.println("\nОшибка вывода дерева.");
                    }
                    localStack.push(temp.leftChild);
                    localStack.push(temp.rightChild);
                    if (temp.leftChild != null || temp.rightChild != null)
                        isRowEmpty = false;
                } else {
                    System.out.print("__");
                    localStack.push(null);
                    localStack.push(null);
                }
                for (int j = 0; j < gaps * 2 - 2; j++)
                    System.out.print(' ');
            }
            System.out.println();
            gaps /= 2;
            while (!localStack.isEmpty())
                globalStack.push(localStack.pop());
        }
        System.out.println(separator);
    }

    private int findMaxDepth(Node node) {
        int depthL, depthR;
        int maxDepth;
        if (node == null)
            maxDepth = 0;
        else {
            depthR = findMaxDepth(node.rightChild);
            depthL = findMaxDepth(node.leftChild);
            if (depthR > depthL)
                maxDepth = depthR + 1;
            else
                maxDepth = depthL + 1;
        }
        return maxDepth;
    }

    public int getHeight(Node root) {
        if (root == null) {
            return 0;
        }

        return 1 + Math.max(getHeight(root.leftChild), getHeight(root.rightChild));
    }

    public String treeToString(Node node) {
        String ans = "";
        if (node != null) {
            ans += treeToString(node.leftChild);
            ans += node.value + " ";
            ans += treeToString(node.rightChild);
        }
        return ans;
    }

    public void makeEmptyTree() {

        rootNode = null;
    }

    public void delete(int n) {
        Node deleteNode, minRightNode;
        int minValue;
        deleteNode = findNode(n, rootNode);
        if (deleteNode == null)
            System.out.println("\nЭлемент отсутствует в дереве, удаление невозможно.");
        else if ((deleteNode.rightChild == null) || (deleteNode.leftChild == null))
            if (deleteNode == rootNode) {
                if (rootNode.rightChild != null)
                    rootNode = rootNode.rightChild;
                else if (rootNode.leftChild != null)
                    rootNode = rootNode.leftChild;
                else
                    rootNode = null;
            }
            else
                delWithoutTwoDes(deleteNode, rootNode);
        else {
            minRightNode = findNodeMin(deleteNode.rightChild);
            minValue = minRightNode.value;
            delWithoutTwoDes(minRightNode, rootNode);
            deleteNode.value = minValue;
        }
    }

    private Node findNodeMin(Node node) {
        Node resultNode;
        resultNode = node;
        if ((node.rightChild != null) || (node.leftChild != null))//мен
            resultNode = findMin(node, resultNode);
        return resultNode;
    }

    private Node findMin(Node node, Node nodeMin) {
        if (node.leftChild != null) {
            if (node.leftChild.value < nodeMin.value)
                nodeMin = node.leftChild;
            nodeMin = findMin(node.leftChild, nodeMin);
        }
        return nodeMin;
    }

    private void delWithoutTwoDes(Node deleteNode, Node rootNode) {
        if ((rootNode.rightChild != null) && (rootNode.rightChild.value == deleteNode.value)) {
            if (rootNode.rightChild.rightChild != null)
                rootNode.rightChild = rootNode.rightChild.rightChild;
            else if (rootNode.rightChild.leftChild != null)
                rootNode.rightChild = rootNode.rightChild.leftChild;
            else
                rootNode.rightChild = null;
        }
        else if ((rootNode.leftChild != null) && (rootNode.leftChild.value == deleteNode.value)) {
            if (rootNode.leftChild.rightChild != null)
                rootNode.leftChild = rootNode.leftChild.rightChild;
            else if (rootNode.leftChild.leftChild != null)
                rootNode.leftChild = rootNode.leftChild.leftChild;
            else
                rootNode.leftChild = null;
        }
        else {
            if (rootNode.rightChild != null)
                delWithoutTwoDes(deleteNode, rootNode.rightChild);
            if ((rootNode.leftChild != null) && (deleteNode != null))
                delWithoutTwoDes(deleteNode, rootNode.leftChild);
            }
        }

    public Node findNode(int n, Node node) {
        Node resultNode;
        resultNode = null;
        if (node == null) {
            node = null;
        } else if (node.value == n)
            resultNode = node;
        else if (node.rightChild != null) {
            resultNode = findNode(n, node.rightChild);
            if (resultNode == null)
                resultNode = findNode(n, node.leftChild);
        } else if (node.leftChild != null)
            resultNode = findNode(n, node.leftChild);
        return resultNode;
    }

    public boolean isLeafNode(int checkedNode, Node root) {
        boolean isLeaf;
        if ((root.rightChild == null) && (root.leftChild == null)) {
            if (root.value == checkedNode)
                isLeaf = true;
            else
                isLeaf = false;
        } else if ((root.rightChild != null) && (root.value < checkedNode))
            isLeaf = isLeafNode(checkedNode, root.rightChild);
        else if ((root.leftChild != null) && (root.value > checkedNode))
            isLeaf = isLeafNode(checkedNode, root.leftChild);
        else
            isLeaf = false;
        return isLeaf;
    }

    public void insertSubtree(int insertVal, Tree subtree) {
        Node insertNode;
        insertNode = findNode(insertVal, rootNode);
        if (insertVal > subtree.rootNode.value)
            insertNode.leftChild = subtree.rootNode;
        else
            insertNode.rightChild = subtree.rootNode;
    }

    public void printTreeInFile(FileWriter fileWriter) {
        Stack globalStack = new Stack();
        globalStack.push(rootNode);
        int gaps = (int) Math.pow(2, findMaxDepth(rootNode));
        boolean isRowEmpty = false;
        String separator = "-----------------------------------------------------------------";
        try {
            fileWriter.write(separator + "\n");
            while (!isRowEmpty) {
                Stack localStack = new Stack();
                isRowEmpty = true;
                for (int j = 0; j < gaps; j++)
                    fileWriter.write(' ');
                while (!globalStack.isEmpty()) {
                    Node temp = (Node) globalStack.pop();
                    if (temp != null) {
                        fileWriter.write(Integer.toString(temp.value));
                        localStack.push(temp.leftChild);
                        localStack.push(temp.rightChild);
                        if (temp.leftChild != null || temp.rightChild != null)
                            isRowEmpty = false;
                    } else {
                        fileWriter.write("__");
                        localStack.push(null);
                        localStack.push(null);
                    }
                    for (int j = 0; j < gaps * 2 - 2; j++)
                        fileWriter.write(' ');
                }
                fileWriter.write("\n");
                gaps /= 2;
                while (!localStack.isEmpty())
                    globalStack.push(localStack.pop());
            }
            fileWriter.write(separator + "\n");
        }  catch (IOException e) {
            System.out.println("\nОшибка! Некорректный файл вывода.");
        }
    }
}

package com.example.lab5_2;

public class Node {
    public int value;
    public Node leftChild;
    public Node rightChild;

}