Lab_5_2

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

class Node {
    int data; // ключ узла
    Node leftChild; // Левый узел потомок
    Node rightChild; // Правый узел потомок

    public Node(int data, Node leftChild, Node rightChild) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}
class Tree {
    public Node rootNode;

    public Tree(Node rootNode) {
        this.rootNode = rootNode;
    }

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

    public Node findMaxNodeInBranch(Node curr) {
        if (curr.rightChild != null) {
            return findMaxNodeInBranch(curr.rightChild);
        } else {
            return curr;
        }
    }

    /*public void deleteNode(Node curr, int value) {
        if (curr != null) {
            if (value < curr.data) {
                deleteNode(curr.leftChild, value);
            }
            if (value > curr.data) {
                deleteNode(curr.rightChild, value);
            }
            if (value == curr.data) {
                if ((curr.rightChild == null) && (curr.leftChild == null)){
                    curr = null;
                } else {
                    if ((curr.rightChild == null) && (curr.leftChild != null)) {
                        curr = curr.leftChild;
                    }
                    if ((curr.rightChild != null) && (curr.leftChild == null)) {
                        curr = curr.rightChild;
                    }
                    if ((curr.rightChild != null) && (curr.leftChild != null)) {
                        Node max = findMaxNodeInBranch(curr.leftChild);
                        curr.data = max.data;
                        deleteNode(curr.leftChild, max.data);
                    }
                }
            }
        }
    }*/

    public boolean deleteNode(int value)
    {
        Node currentNode = rootNode;
        Node parentNode = rootNode;
        boolean isLeftChild = true;
        while (currentNode.data != value) {
            parentNode = currentNode;
            if (value < currentNode.data) {
                isLeftChild = true;
                currentNode = currentNode.leftChild;
            }
            else {
                isLeftChild = false;
                currentNode = currentNode.rightChild;
            }
            if (currentNode == null)
                return false;
        }

        if (currentNode.leftChild == null && currentNode.rightChild == null) {
            if (currentNode == rootNode)
                rootNode = null;
            else if (isLeftChild)
                parentNode.leftChild = null;
            else
                parentNode.rightChild = null;
        }
        else if (currentNode.rightChild == null) {
            if (currentNode == rootNode)
                rootNode = currentNode.leftChild;
            else if (isLeftChild)
                parentNode.leftChild = currentNode.leftChild;
            else
                parentNode.rightChild= currentNode.leftChild;
        }
        else if (currentNode.leftChild == null) {
            if (currentNode == rootNode)
                rootNode = currentNode.rightChild;
            else if (isLeftChild)
                parentNode.leftChild = currentNode.rightChild ;
            else
                parentNode.rightChild = currentNode.rightChild;
        }
        else {
            Node heir = receiveHeir(currentNode);
            if (currentNode == rootNode)
                rootNode = heir;
            else if (isLeftChild)
                parentNode.leftChild = heir;
            else
                parentNode.rightChild = heir;
        }
        return true;
    }
    private Node receiveHeir(Node node) {
        Node parentNode = node;
        Node heirNode = node;
        Node currentNode = node.rightChild;
        while (currentNode != null)
        {
            parentNode = heirNode;
            heirNode = currentNode;
            currentNode = currentNode.leftChild;
        }

        if (heirNode != node.rightChild)
        {
            parentNode.leftChild = heirNode.rightChild;
            heirNode.rightChild = node.rightChild;
        }
        return heirNode;
    }

    public int CountNodesInTree(Node curr) {
        int count = 0;
        if (curr != null) {
            if ((curr.leftChild != null) || (curr.rightChild != null)) {
                count++;
            }
            count += CountNodesInTree(curr.leftChild);
            count += CountNodesInTree(curr.rightChild);
        }
        return count;
    }

    public int CountLeavesInTree(Node curr) {
        int count = 0;
        if (curr != null) {
            if ((curr.leftChild == null) && (curr.rightChild == null)) {
                count++;
            }
            count += CountLeavesInTree(curr.leftChild);
            count += CountLeavesInTree(curr.rightChild);
        }
        return count;
    }
}

public class Main {

    static final int MAX_OPERATION_COUNT = 3;
    static final int MIN_OPERATION_COUNT = 0;
    static final int MIN_DATA = -99;
    static final int MAX_DATA = 99;
    static Scanner scan = new Scanner(System.in);


    public static void main(String[] args) {
        writeTask();
        Node head = new Node(0, null, null);
        Tree tree = new Tree(head);
        tree.rootNode = null;
        System.out.println("Получить дерево из файла? 1 - да, 2 - нет");
        int choice = chooseInputOutputMethod();
        if (choice == 1) {
            tree = addTreeFromFile(tree);
        }
        boolean isContinue = true;
        do {
            choice = chooseOperation();
            switch (choice) {
                case 1:
                    tree = addNewElement(tree);
                    break;
                case 2:
                    tree = deleteElement(tree);
                    break;
                case 3:
                    countNodesAndLeaves(tree);
                    break;
                case 0:
                    isContinue = false;
                    break;
            }
        } while (isContinue);
        scan.close();
    }

    public static void writeTask() {
        System.out.println("Данная программа реализует работу с бинарным деревом поиска.");
        System.out.println("Список возможных функций: 1. Добавление нового элемента.");
        System.out.println("                          2. Удаление элемента.");
        System.out.println("                          3. Подсчёт количества узлов и листьев дерева.");
        System.out.println("                          0. Завершение работы.");
    }

    public static int chooseOperation() {
        int choice = 0;
        boolean isNotCorrect;
        do {
            System.out.println("Введите номер операции, которую необходимо выполнить.");
            isNotCorrect = false;
            try {
                choice = Integer.parseInt(scan.nextLine());
            } catch (NumberFormatException e) {
                isNotCorrect = true;
                System.out.println("Некорректно введён номер операции. Повторите попытку.");
            }
            if ((!isNotCorrect) && (choice > MAX_OPERATION_COUNT || choice < MIN_OPERATION_COUNT)) {
                isNotCorrect = true;
                System.out.println("Введён неправильный номер операции. Он должен быть от " + MIN_OPERATION_COUNT + " до " + MAX_OPERATION_COUNT + ". Повторите попытку.");
            }
        } while (isNotCorrect);
        return choice;
    }

    public static Tree addNewElement(Tree tree) {
        boolean isNotCorrect;
        int data = 0;
        do {
            isNotCorrect = false;
            System.out.println("Введите элемент, добавляемый в дерево (от -99 до 99)");
            try {
                data = Integer.parseInt(scan.nextLine());
            } catch (NumberFormatException e) {
                isNotCorrect = true;
                System.out.println("Некорректно введено число");
            }
            if ((!isNotCorrect) && (data < MIN_DATA || data > MAX_DATA)) {
                isNotCorrect = true;
                System.out.println("Значение элемента должно быть от " + MIN_DATA + " до " + MAX_DATA);
            }
        } while (isNotCorrect);
        tree.insertNode(data);
        return tree;
    }

    public static Tree deleteElement(Tree tree) {
        if (tree.rootNode == null) {
            boolean isNotCorrect;
            int data = 0;
            do {
                isNotCorrect = false;
                System.out.println("Введите элемент, удаляемый из дерева (от -99 до 99)");
                try {
                    data = Integer.parseInt(scan.nextLine());
                } catch (NumberFormatException e) {
                    isNotCorrect = true;
                    System.out.println("Некорректно введено число");
                }
                if ((!isNotCorrect) && (data < MIN_DATA || data > MAX_DATA)) {
                    isNotCorrect = true;
                    System.out.println("Номер формата должен быть от " + MIN_DATA + " до " + MAX_DATA);
                }
            } while (isNotCorrect);
            if (!(tree.deleteNode(data))) {
                System.out.println("Удаляемый элемент не найден в дереве!");
            }
        } else {
            System.out.println("Дерево пустое, удаление элемента невозможно.");
        }
        return tree;
    }

    public static void countNodesAndLeaves(Tree tree) {
        if (tree.rootNode != null) {
            int nodes = tree.CountNodesInTree(tree.rootNode);
            int leaves = tree.CountLeavesInTree(tree.rootNode);
            System.out.println("Количество узлов: " + nodes);
            System.out.println("Количество листьев: " + leaves);
        } else {
            System.out.println("Бинарное дерево пустое!");
        }
    }

    public static int chooseInputOutputMethod() {
        boolean isNotCorrect;
        int choice = 0;
        do {
            isNotCorrect = false;
            try {
                choice = Integer.parseInt(scan.nextLine());
            } catch (NumberFormatException e) {
                System.out.println("Число введено некорректно. Повторите попытку...");
                isNotCorrect = true;
            }
            if ((!isNotCorrect) && (choice != 1) && (choice != 2)) {
                System.out.print("Введите либо 1, либо 2. Ваш выбор: ");
                isNotCorrect = true;
            }
        } while (isNotCorrect);
        return choice;
    }

    public static String takePathToFile() {
        String path;
        boolean isNotCorrect;
        do {
            isNotCorrect = false;
            System.out.println("Введите путь к файлу: ");
            path = scan.nextLine();
            File file = new File(path);
            if (!file.exists()) {
                System.out.println("Не удалось найти файл по заданному пути. Повторите попытку...");
                isNotCorrect = true;
            }
        } while (isNotCorrect);
        return path;
    }

    public static Tree addTreeFromFile(Tree oldTree) {
        String path;
        boolean isNotCorrect;
        boolean isEmpty = true;
        int element;
        Node start = null;
        Tree tree = new Tree(start);
        do {
            tree = oldTree;
            path = takePathToFile();
            isNotCorrect = false;
            try (Scanner fileReader = new Scanner(new File(path))) {
                try {
                    while (fileReader.hasNextLine()) {
                        element = Integer.parseInt(fileReader.nextLine());
                        if ((!isNotCorrect) && (element < MIN_DATA || element > MAX_DATA)) {
                            isNotCorrect = true;
                            System.out.println("Значение элемента должно быть от " + MIN_DATA + " до " + MAX_DATA);
                        }
                        if (!isNotCorrect) {
                            tree.insertNode(element);
                            isEmpty = false;
                        }
                    }
                } catch (NumberFormatException e) {
                    isNotCorrect = true;
                    System.out.println("Некорректно введено одно из значений в файле. Попробуйте заново.");
                }
            } catch (IOException e) {
                isNotCorrect = true;
                System.out.println("Не выходит получить данные из файла. Попробуйте ещё раз.");
            }
            if ((!isNotCorrect) && (isEmpty)) {
                isNotCorrect = true;
                System.out.println("Введён пустой файл. Попробуйте ещё раз.");
            }
        } while (isNotCorrect);
        System.out.println("Дерево получено");
        return tree;
    }
}