package com.company.struct;

public class Node {
    private int data;
    private Node leftChild;
    private Node rightChild;

    public Node(int data) {
        this.data = data;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    public Node getLeftChild() {
        return this.leftChild;
    }

    public Node getRightChild() {
        return this.rightChild;
    }

    public int getData() {
        return this.data;
    }

    public void outputNode() {
        System.out.print(this.data + " ");
    }
}



package com.company.struct;

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

public class Tree {
    private Node root = null;

    public Tree() {
    }

    public Node getRoot() {
        return this.root;
    }

    public Node find(int key) {
        Node current = this.root;

        do {
            if (current.getData() == key) {
                return current;
            }

            if (key < current.getData()) {
                current = current.getLeftChild();
            } else {
                current = current.getRightChild();
            }
        } while(current != null);

        return null;
    }

    public void insert(int data) {
        Node newNode = new Node(data);
        if (this.root == null) {
            this.root = newNode;
        } else {
            Node current = this.root;

            Node parent;
            label21:
            do {
                do {
                    parent = current;
                    if (data < current.getData()) {
                        current = current.getLeftChild();
                        continue label21;
                    }

                    current = current.getRightChild();
                } while(current != null);

                parent.setRightChild(newNode);
                return;
            } while(current != null);

            parent.setLeftChild(newNode);
        }
    }

    private Node getSuccessor(Node delNode) {
        Node successorParent = delNode;
        Node successor = delNode;

        for(Node current = delNode.getRightChild(); current != null; current = current.getLeftChild()) {
            successorParent = successor;
            successor = current;
        }

        if (successor != delNode.getRightChild()) {
            successorParent.setLeftChild(successor.getRightChild());
            successor.setRightChild(delNode.getRightChild());
        }

        return successor;
    }

    public void delete(int data) {
        Node current = this.root;
        Node parent = this.root;
        boolean isLeftChild = true;

        while(current.getData() != data) {
            parent = current;
            if (data < current.getData()) {
                isLeftChild = true;
                current = current.getLeftChild();
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }

            if (current == null) {
                return;
            }
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == this.root) {
                this.root = null;
            } else if (isLeftChild) {
                parent.setLeftChild((Node)null);
            } else {
                parent.setRightChild((Node)null);
            }
        } else if (current.getRightChild() == null) {
            if (current == this.root) {
                this.root = current.getLeftChild();
            } else if (isLeftChild) {
                parent.setLeftChild(current.getLeftChild());
            } else {
                parent.setRightChild(current.getLeftChild());
            }
        } else if (current.getLeftChild() == null) {
            if (current == this.root) {
                this.root = current.getRightChild();
            } else if (isLeftChild) {
                parent.setLeftChild(current.getRightChild());
            } else {
                parent.setRightChild(current.getRightChild());
            }
        } else {
            Node successor = this.getSuccessor(current);
            if (current == this.root) {
                this.root = successor;
            } else if (isLeftChild) {
                parent.setLeftChild(successor);
            } else {
                parent.setRightChild(successor);
            }

            successor.setLeftChild(current.getLeftChild());
        }

    }

    public void postOrder(Node localRoot) {
        if (localRoot != null) {
            this.postOrder(localRoot.getLeftChild());
            this.postOrder(localRoot.getRightChild());
            localRoot.outputNode();
        }

    }

    public void outputInFile(String patch) throws IOException {
        FileWriter writer = new FileWriter(patch);
        Stack globalStack = new Stack();
        globalStack.push(this.root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        writer.write("****************************************************************\n");
        writer.write("                         Бинарное дерево\n");

        while(!isRowEmpty) {
            Stack localStack = new Stack();
            isRowEmpty = true;

            for(int j = 0; j < nBlanks; ++j) {
                writer.write(32);
            }

            while(!globalStack.isEmpty()) {
                Node temp = (Node)globalStack.pop();
                if (temp != null) {
                    writer.write(Integer.toString(temp.getData()));
                    localStack.push(temp.getLeftChild());
                    localStack.push(temp.getRightChild());
                    if (temp.getLeftChild() != null || temp.getRightChild() != null) {
                        isRowEmpty = false;
                    }
                } else {
                    writer.write("--");
                    localStack.push((Object)null);
                    localStack.push((Object)null);
                }

                for(int j = 0; j < nBlanks * 2 - 2; ++j) {
                    writer.write(32);
                }
            }

            writer.write("\n");
            nBlanks /= 2;

            while(!localStack.isEmpty()) {
                globalStack.push(localStack.pop());
            }
        }

        writer.write("\n****************************************************************");
        writer.flush();
    }

    public void displayTree() {
        Stack globalStack = new Stack();
        globalStack.push(this.root);
        int nBlanks = 32;
        boolean isRowEmpty = false;
        System.out.println("****************************************************************");
        System.out.println("                         Бинарное дерево");

        while(!isRowEmpty) {
            Stack localStack = new Stack();
            isRowEmpty = true;

            for(int j = 0; j < nBlanks; ++j) {
                System.out.print(' ');
            }

            while(!globalStack.isEmpty()) {
                Node temp = (Node)globalStack.pop();
                if (temp != null) {
                    System.out.print(temp.getData());
                    localStack.push(temp.getLeftChild());
                    localStack.push(temp.getRightChild());
                    if (temp.getLeftChild() != null || temp.getRightChild() != null) {
                        isRowEmpty = false;
                    }
                } else {
                    System.out.print("--");
                    localStack.push((Object)null);
                    localStack.push((Object)null);
                }

                for(int j = 0; j < nBlanks * 2 - 2; ++j) {
                    System.out.print(' ');
                }
            }

            System.out.println();
            nBlanks /= 2;

            while(!localStack.isEmpty()) {
                globalStack.push(localStack.pop());
            }
        }

        System.out.println("****************************************************************");
    }

    public void clear() {
        this.root = null;
    }

    public int getDiameter(Node root) {
        if (root == null) {
            return 0;
        } else {
            int rootDiameter = this.getHeight(root.getLeftChild()) + this.getHeight(root.getRightChild()) + 1;
            int leftDiameter = this.getDiameter(root.getLeftChild());
            int rightDiameter = this.getDiameter(root.getRightChild());
            return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
        }
    }

    public int getHeight(Node root) {
        return root == null ? 0 : Math.max(this.getHeight(root.getLeftChild()), this.getHeight(root.getRightChild())) + 1;
    }
}


package com.company.starter;

import com.company.struct.Tree;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Scanner;

public class Main {

    static Scanner scannerConsole;
    static Tree treeInt;

    static final int CREATE_TREE = 1;
    static final int OPEN_TREE = 2;
    static final int ADD_NODE = 1;
    static final int DELETE_NODE = 2;
    static final int VIEW_TREE = 3;
    static final int MAX_WAY = 4;
    static final int POST_ORDER = 5;
    static final int SAVE_TREE_OF_MENU = 6;
    static final int OPEN_TREE_OF_MENU = 7;
    static final int EXIT_PROGRAM = 0;

    static int enterValue(){
        int num;
        boolean isCorrect = true;
        num = 0;
        do {
            try {
                num = Integer.parseInt(scannerConsole.nextLine());
                isCorrect = false;
            } catch (Exception E) {
                System.out.print("Ошибка, повторите ввод: ");
            }
        } while(isCorrect);
        return num;
    }

    static int enterNodeForAdd(){
        int num;
        boolean isCorrect;
        do{
            isCorrect = false;
            num = enterValue();
            if(treeInt.getRoot() != null)
                if(treeInt.find(num) != null){
                    System.out.print("Данное число уже есть в дереве. Повторите ввод: ");
                    isCorrect = true;
                }
        }while(isCorrect);
        return num;
    }

    static int enterNodeForDel(){
        int num;
        boolean isCorrect;
        do{
            isCorrect = false;
            num = enterValue();
            if(treeInt.find(num) == null){
                System.out.print("Данного числа нет в дереве. Повторите ввод: ");
                isCorrect = true;
            }
        }while(isCorrect);
        return num;
    }

    static boolean isCorrectChoice(int choice){
        boolean isInCorrect;
        if(choice == CREATE_TREE || choice == OPEN_TREE){
            isInCorrect = false;
        }
        else{
            isInCorrect = true;
        }
        return isInCorrect;
    }

    static void printSelection(boolean isInCorrect, int choice){
        if(!isInCorrect){
            System.out.println("Вы выбрали вариант " + choice);
            System.out.println("---------------------------------------------");
        }
        else {
            System.out.print("Пожалуйста, выберите указанные варианты: ");
        }
    }

    static int getTheChoice(){
        int choice;
        boolean isInCorrect;
        do {
            choice = enterValue();
            isInCorrect = isCorrectChoice(choice);
            printSelection(isInCorrect, choice);
        }while(isInCorrect);
        return choice;
    }

    static boolean isCorrectSizeFile(String patch) {
        boolean isCorrect = true;
        File inputFile = new File(patch);
        if (inputFile.length() == 0) {
            System.out.print("Файл пустой, повторите ввод: ");
            isCorrect = false;
        }
        return isCorrect;
    }

    static boolean isFileCorrect(String patch) throws IOException {
        Scanner scannerFile = new Scanner(new File(patch));
        boolean isCorrect = true;
        while(scannerFile.hasNextLine() && isCorrect){
            try {
                scannerFile.nextInt();
            } catch(Exception E) {
                System.out.print("Данные в указанном файле не соответсвуют условию. Повторите ввод: ");
                isCorrect = false;
            }
        }
        scannerFile.close();
        return isCorrect;
    }

    static boolean IsFileExist(String patch){
        boolean isCorrect;
        File inputFile = new File(patch);
        if (inputFile.exists()){
            isCorrect = true;
        }
        else{
            isCorrect = false;
            System.out.print("Указанного файла не существует. Повторите ввод: ");
        }
        return isCorrect;
    }

    static String enterPatch() throws IOException {
        String patch;
        boolean isCorrect;
        System.out.print("Введите адрес файла: ");
        do {
            patch = scannerConsole.nextLine();
            isCorrect = (IsFileExist(patch) && isCorrectSizeFile(patch) && isFileCorrect(patch));
        } while (!isCorrect);
        return patch;
    }

    static void fillTreeFromFile(String patch) throws FileNotFoundException {
        Scanner scannerFile = new Scanner(new File(patch));
        int temp;
        while(scannerFile.hasNextLine()){
            temp = scannerFile.nextInt();
            treeInt.insert(temp);
        }
        scannerFile.close();
    }

    static void openTreeFromFile() throws IOException {
        treeInt.clear();
        System.out.println("Открытие дерева");
        System.out.println("---------------------------------------------");
        String patch = enterPatch();
        fillTreeFromFile(patch);
    }

    static void openTree(int choice) throws IOException, ClassNotFoundException {
        if(choice == OPEN_TREE){
            openTreeFromFile();
        }
    }

    static boolean isCorrectChoiceForMenu(int choice){
        boolean isCorrect;
        if(choice == ADD_NODE || choice == DELETE_NODE || choice == VIEW_TREE
                || choice == MAX_WAY || choice == POST_ORDER || choice == SAVE_TREE_OF_MENU
                || choice == OPEN_TREE_OF_MENU || choice == EXIT_PROGRAM){
            isCorrect = false;
        }
        else{
            isCorrect = true;
        }
        return isCorrect;
    }

    static int inputTheChoiceForMenu(){
        int choice;
        boolean isCorrect;
        do {
            choice = enterValue();
            isCorrect = isCorrectChoiceForMenu(choice);
            printSelection(isCorrect, choice);
        }while(isCorrect);
        return choice;
    }

    static void printMainMenu(){
        System.out.println("\nПрограмма работы с бинарным деревом");
        System.out.println("---------------------------------------");
        System.out.print("Построить дерево(1) \nОткрыть дерево из файла(2)\n\nВвод: ");
    }

    static void printInfoMenu(){
        System.out.println("---------------------------------------------");
        System.out.println("\t\t\tБинарное дерево");
        System.out.println("---------------------------------------------");
        System.out.println("Выберите действие, которое вы хотите выполнить:");
        System.out.println("(1)Добавление элемента");
        System.out.println("(2)Удаление указанного элемента");
        System.out.println("(3)Просмотр элементов дерева");
        System.out.println("(4)Максимальный путь");
        System.out.println("(5)Обратный обход дерева");
        System.out.println("(6)Сохранение дерева");
        System.out.println("(7)Открыть дерево");
        System.out.println("(0)Выход");
        System.out.print("Ввод: ");
    }

    static void addNode() throws IOException, ClassNotFoundException {
        System.out.println("Добавление элемента в дерево");
        System.out.println("------------------------------");
        System.out.print("Введите число, которое хотите добавить: ");
        int num = enterNodeForAdd();
        treeInt.insert(num);
        System.out.println("Число " + num + " успешно добавлено");
        selectionMenu();
    }



    static void deleteNode() throws IOException, ClassNotFoundException {
        if(treeInt.getRoot() == null){
            System.out.println("Дерево пусто");
        } else {
            System.out.println("Удаление элемента из дерева");
            System.out.println("------------------------------");
            System.out.print("Введите число, которое хотите удалить: ");
            int num = enterNodeForDel();
            treeInt.delete(num);
            System.out.println("Число " + num + " успешно удалено");
        }
    }

    static void viewTree(){
        if(treeInt.getRoot() != null){
            treeInt.displayTree();
            System.out.print("\n");
        } else {
            System.out.println("Дерево пусто");
        }
    }

    static void saveTree() throws IOException {
        System.out.println("\t\t\tСохранение дерева");
        System.out.println("---------------------------------------------");
        System.out.print("Введите адрес: ");
        String patch = scannerConsole.nextLine();
        treeInt.outputInFile(patch);
        System.out.println("Данные записаны в файл с адресом: " + patch);
    }

    static void checkSizeTreeForSave() throws IOException {
        if(treeInt.getRoot() == null){
            System.out.println("Дерево пусто");
        } else {
            saveTree();
        }
    }

    static void postOrder(){
        if(treeInt.getRoot() == null){
            System.out.println("Дерево пусто");
        } else {
            System.out.print("Обратный обход дерева: ");
            treeInt.postOrder(treeInt.getRoot());
            System.out.println("\n");
        }
    }

    static void maxWay(){
        if(treeInt.getRoot() == null){
            System.out.println("Дерево пусто");
        } else {
            System.out.print("Путь максимальной длины между вершинами с разным числом потомков равен:  ");
            System.out.println(treeInt.getDiameter(treeInt.getRoot()) - 1);
        }
    }

    static void selectionMenu()  throws IOException, ClassNotFoundException {
        printInfoMenu();
        switch (inputTheChoiceForMenu()){
            case ADD_NODE:
                addNode();
                selectionMenu();
            case DELETE_NODE:
                deleteNode();
                selectionMenu();
            case VIEW_TREE:
                viewTree();
                selectionMenu();
            case MAX_WAY:
                maxWay();
                selectionMenu();
            case POST_ORDER:
                postOrder();
                selectionMenu();
            case SAVE_TREE_OF_MENU:
                checkSizeTreeForSave();
                selectionMenu();
            case OPEN_TREE_OF_MENU:
                openTreeFromFile();
                selectionMenu();
            case EXIT_PROGRAM:
                System.out.println("Конец программы");
                System.exit(0);
        }
    }

    public static void main(String[] args) throws IOException, ClassNotFoundException {
        scannerConsole = new Scanner(System.in);
        treeInt = new Tree();
        printMainMenu();
        openTree(getTheChoice());
        selectionMenu();
        scannerConsole.close();
    }
}