Threaded Binary Tree(3 sem)

/*
                                            #########################################
                                            |           Node class start            |
                                            #########################################
*/
public class Node {
    int key;
    int height;
    Node left;
    Node right;
    boolean rightThread; // Истина, если правый указатель указывает на преемника
                        // Ложь, если правый указатель указывает на обычного потомка
    boolean isOutputed;

    @Override
    public String toString() {
        return "" + key;
    }
}
/*
                                            #########################################
                                            |           Node class end              |
                                            #########################################

                                            #########################################
                                            |           Tree class start            |
                                            #########################################
*/
class Tree {
    public Node rootNode;

    /*      insert func start     */
    public Node insertNode(Node parentNode, final int key) {
        if (parentNode == null) {
            Node temp = new Node();
            temp.key = key;
            return temp;
        } else if (parentNode.key > key) {
            parentNode.left = insertNode(parentNode.left, key);
        } else if (parentNode.key < key) {
            if (parentNode.rightThread) {
                parentNode.right = null;
                parentNode.rightThread = false;
            }

            parentNode.right = insertNode(parentNode.right, key);
        } else {
            System.err.println("Некорректный ввод! Элемент с таким значением уже существует.");
        }
        return parentNode;
    }
    /*      insert func end     */

    /*      delete func start     */
    public static Node mostLeftChild(final Node parentNode) {
        Node temp = parentNode;
        while (temp.left != null)
            temp = temp.left;
        return temp;
    }

    public Node deleteNode(Node parentNode, final int key) {
        if (parentNode == null) {
            System.err.println("Элемента с таким значением нет в дереве!");
            return null;
        } else if (parentNode.key > key) {
            parentNode.left = deleteNode(parentNode.left, key);
        } else if (parentNode.key < key) {
            parentNode.right = deleteNode(parentNode.right, key);
        } else {
            if (parentNode.left == null || parentNode.right == null || (parentNode.rightThread)) {
                parentNode = (parentNode.left == null && !parentNode.rightThread) ? parentNode.right : parentNode.left;
            } else {
                Node mostLeftChild = mostLeftChild(parentNode.right);
                parentNode.key = mostLeftChild.key;
                parentNode.right = deleteNode(parentNode.right, parentNode.key);
            }
        }
        return parentNode;
    }
    /*      delete func end     */

    /*      find func start     */
    public Node findNodeByValue(final int value) {
        Node currentNode = rootNode;
        while (currentNode.key != value) {
            if (value < currentNode.key) {
                currentNode = currentNode.left;
            } else {
                currentNode = currentNode.right;
            }
            if (currentNode == null) {
                System.out.println("Элемента с таким значением нет в дереве.");
                return null;
            }
        }
        return currentNode;
    }
    /*      find func end     */

    /*      thread func start     */
    public static Node clearThreadsAndOutputs(Node parentNode) {
        if (parentNode == null)
            return null;
        clearThreadsAndOutputs(parentNode.left);
        parentNode.isOutputed = false;
        if (parentNode.rightThread) {
            parentNode.right = null;
            parentNode.rightThread = false;
        }
        clearThreadsAndOutputs(parentNode.right);
        return null;
    }

    public static Node sewTree(Node parentNode) {
        if (parentNode == null) {
            return null;
        }

        if (parentNode.right == null && parentNode.left == null) {
            return parentNode;
        }

        if (parentNode.left != null) {
            Node left = sewTree(parentNode.left);
            left.right = parentNode;
            left.rightThread = true;
        }

        if (parentNode.right == null) {
            return parentNode;
        }

        return sewTree(parentNode.right);
    }
    /*      thread func end     */

    /*      print methods start     */
    public static final String ANSI_RESET = "\u001B[0m";
    public static final String ANSI_BLUE = "\u001B[34m";
    public static final String ANSI_RED = "\u001B[31m";

    void printInorder(Node parentNode) {
        if (parentNode == null)
            return;

        printInorder(parentNode.left);
        String color = (parentNode.rightThread) ? ANSI_RED : ANSI_BLUE;
        System.out.print(color + parentNode.key + " " + ANSI_RESET);
        if (!parentNode.rightThread)
            printInorder(parentNode.right);
    }

    void printPreorder(Node parentNode) {
        if (parentNode == null)
            return;

        String color = (parentNode.rightThread) ? ANSI_RED : ANSI_BLUE; //useless at the moment
        System.out.print(color + parentNode.key + " " + ANSI_RESET);
        printPreorder(parentNode.left);
        if (!parentNode.rightThread)
            printPreorder(parentNode.right);
    }

    void printPostorder(Node parentNode) {
        if (parentNode == null)
            return;

        printPostorder(parentNode.left);
        if (!parentNode.rightThread)
            printPostorder(parentNode.right);
        String color = (parentNode.rightThread) ? ANSI_RED : ANSI_BLUE; //useless at the moment
        System.out.print(color + parentNode.key + " " + ANSI_RESET);
    }


    static public void printSewTree(Node currNode) {
        if (currNode != null) {
            String color = (currNode.right != null && currNode.right.isOutputed) ? ANSI_RED : ANSI_BLUE; //useless at the moment
            System.out.print(color + currNode.key + " " + ANSI_RESET);
            if (!currNode.isOutputed) {
                currNode.isOutputed = true;
                printSewTree(currNode.left);
                printSewTree(currNode.right);
            }
        }
    }

    public void printNode(final Node currentNode) {
        System.out.println("Выбранный узел имеет значение: " + currentNode.key);
        if (currentNode.left == null && currentNode.right == null)
            System.out.println("У данного элемента нет потомков.");
        else {
            String ansRightChild = (currentNode.right != null) ? "Значение правого потомка: " + currentNode.right.key : "У данного элемента нет правого потомка.";
            System.out.println(ansRightChild);
            String ansLeftChild = (currentNode.left != null) ? "Значение левого потомка: " + currentNode.left.key : "У данного элемента нет левого потомка.";
            System.out.println(ansLeftChild);
        }
    }
    /*      print methods end     */
}

/*
                                            #########################################
                                            |           Tree class end              |
                                            #########################################

                                            #########################################
                                            |         TreePrinter class start       |
                                            #########################################
*/

import java.util.ArrayList;
import java.util.List;

public class TreePrinter
{
    public static void printTree(Node root)
    {
        List<List<String>> lines = new ArrayList<List<String>>();

        List<Node> level = new ArrayList<Node>();
        List<Node> next = new ArrayList<Node>();

        level.add(root);
        int newNode = 1;

        int widest = 0;

        while (newNode != 0) {
            List<String> line = new ArrayList<String>();

            newNode = 0;

            for (Node currNode : level) {
                if (currNode == null) {
                    line.add(null);

                    next.add(null);
                    next.add(null);
                } else {
                    String stringOfNode = currNode.toString();
                    line.add(stringOfNode);
                    if (stringOfNode.length() > widest) widest = stringOfNode.length();

                    next.add(currNode.left);
                    if (!currNode.rightThread)
                        next.add(currNode.right);
                    else {
                        next.add(null);
                    }

                    if (currNode.left != null) newNode++;
                    if (!currNode.rightThread && currNode.right != null) newNode++;
                }
            }

            if (widest % 2 == 1) widest++;

            lines.add(line);

            List<Node> tmp = level;
            level = next;
            next = tmp;
            next.clear();
        }

        int perPiece = lines.get(lines.size() - 1).size() * (widest + 4);
        for (int i = 0; i < lines.size(); i++) {
            List<String> line = lines.get(i);
            int hpw = (int) Math.floor(perPiece / 2f) - 1;

            if (i > 0) {
                for (int j = 0; j < line.size(); j++) {

                    char tempChar = ' ';
                    if (j % 2 == 1) {
                        if (line.get(j - 1) != null) {
                            tempChar = (line.get(j) != null) ? '┴' : '┘';
                        } else {
                            if (line.get(j) != null) tempChar = '└';
                        }
                    }
                    System.out.print(tempChar);

                    if (line.get(j) == null) {
                        for (int k = 0; k < perPiece - 1; k++) {
                            System.out.print(" ");
                        }
                    } else {
                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? " " : "─");
                        }
                        System.out.print(j % 2 == 0 ? "┌" : "┐");
                        for (int k = 0; k < hpw; k++) {
                            System.out.print(j % 2 == 0 ? "─" : " ");
                        }
                    }
                }
                System.out.println();
            }

            for (String lineStr : line) {

                if (lineStr == null) lineStr = "";
                float tmp = perPiece / 2f - lineStr.length() / 2f;
                int gap1 = (int) Math.ceil(tmp);
                int gap2 = (int) Math.floor(tmp);

                for (int k = 0; k < gap1; k++) {
                    System.out.print(" ");
                }
                System.out.print(lineStr);
                for (int k = 0; k < gap2; k++) {
                    System.out.print(" ");
                }
            }
            System.out.println();

            perPiece /= 2;
        }
    }
}

/*

                                            #########################################
                                            |         TreePrinter class end         |
                                            #########################################

                                            #########################################
                                            |           Main class start            |
                                            #########################################
*/

import java.util.Scanner;

public class Main {

    public static void printTaskInfo() {
        System.out.println("\tДанная программа позволяет сформировать, изменить, вывести и прошить бинарное дерево поиска.");
        System.out.println("\t\tДля работы в программе используйте команды меню.");
    }

    public static void printMenuOptions() {
        System.out.println("\t\t\t\t\t Меню");
        System.out.println("\t\t\t\t1.Добавить узел");
        System.out.println("\t\t\t\t2.Удалить узел");
        System.out.println("\t\t\t\t3.Поиск узла");
        System.out.println("\t\t\t\t4.Вывести дерево");
        System.out.println("\t\t\t\t5.Прошить дерево и вывести прошивку");
        System.out.println("\t\t\t\t6.Вывести обходы дерева всеми способами.");
        System.out.println("\t\t\t\t7.Выйти из программы");
    }

    public static void main(String[] args) {
        Tree tree = new Tree();
        Scanner scan = new Scanner(System.in);
        int choice = 0;

        printTaskInfo();
        printMenuOptions();

        do {
            System.out.print("\n\nВведите команду для выполнения: ");
            try {
                choice = Integer.parseInt(scan.nextLine());
            } catch (Exception e) {
                choice = -1;
            }
            switch (choice) {
                case 1: {
                    System.out.println("Вы выбрали: добавить узел");
                    int elemToAdd;
                    System.out.print("Введите значение элемента для добавления: ");
                    elemToAdd = Integer.parseInt(scan.nextLine());
                    tree.rootNode = tree.insertNode(tree.rootNode, elemToAdd);
                    break;
                }

                case 2: {
                    System.out.println("Вы выбрали: удалить узел");
                    int elemToDelete;
                    System.out.print("Введите значение элемента для удаления: ");
                    elemToDelete = Integer.parseInt(scan.nextLine());
                    tree.rootNode = tree.deleteNode(tree.rootNode, elemToDelete); //? "Элемент успешно удален!" : "Элемента с таким значением нет в дереве!";
                    break;
                }
                case 3: {
                    System.out.println("Вы выбрали: поиск узла");
                    int elemToFind;
                    System.out.print("Введите значение элемента для поиска: ");
                    elemToFind = Integer.parseInt(scan.nextLine());
                    Node foundNode = tree.findNodeByValue(elemToFind);
                    if (foundNode != null)
                        tree.printNode(foundNode);
                    break;
                }
                case 4: {
                    System.out.println("Вы выбрали: вывести дерево");
                    System.out.println("Вывод дерева: ");
                    TreePrinter.printTree(tree.rootNode);
                    break;
                }
                case 5: {
                    System.out.println("Вы выбрали: прошить дерево и вывести прошивку.\nКрасным цветом обозначены узлы, имеющие прошивку");
                    Tree.clearThreadsAndOutputs(tree.rootNode);
                    Tree.sewTree(tree.rootNode);
                    Tree.printSewTree(tree.rootNode);
                    break;
                }
                case 6: {
                    System.out.println("Вы выбрали: показать обход дерева всеми способами.");
                    System.out.println("Прямой обход: ");
                    tree.printPreorder(tree.rootNode);
                    System.out.println("\nСимметричный обход: ");
                    tree.printInorder(tree.rootNode);
                    System.out.println("\nОбратный обход: ");
                    tree.printPostorder(tree.rootNode);
                    break;
                }
                case 7: {
                    System.out.println("Вы выбрали: выйти из программы");
                    break;
                }
                default:
                    System.err.println("Некорректный ввод! Выберите один из пунктов меню!");
                    break;
            }
        } while (choice != 7);
    }
}

/*
                                            #########################################
                                            |           Main class end              |
                                            #########################################
*/