LAB2_TREE

import java.io.*;
import java.util.ArrayList;

/*
Задано дерево в виде таблицы.
В первой колонке номер узла – целое число, вторая колоночка таблицы – родитель.
Задачи:
(1)Для произвольного узла вывести часть дерева, которая связывает его с корнем дерева.
(2)Вывести дочернее поддерево.
(3)Выбираем два произвольных узла и строим часть дерева, которая их соединяет.
*/

public class Tree {

    public static void main(String[] args) throws IOException {

        BufferedReader consoleReader = new BufferedReader(new InputStreamReader(System.in));

        //Создадим произвольное дерево в виде таблицы.
        Integer[][] tree = {
                {8, null},
                {4, 8},
                {9, 8},
                {10, 9},
                {11, 10},
                {7, 10},
                {2, 4},
                {6, 4},
                {1, 2},
                {3, 2}
        };

        //Выведем его на экран.
        System.out.println("Ваше дерево в виде таблицы:");
        for (int i = 0; i < tree.length; i++) {
            for (int j = 0; j < tree[i].length; j++) {
                System.out.print(tree[i][j] + "\t");
            }
            System.out.println();
        }

        //(1)Вывод пути от произвольного узла до корня дерева.
        ArrayList<Integer> path = new ArrayList<>();

        System.out.print("\nВведите число(узел, путь до которого вы хотите найти): ");
        int treeNode = Integer.parseInt(consoleReader.readLine());
        System.out.println("Путь от узла со значением " + treeNode + " до корня дерева:");

        pathToTheRoot(treeNode, tree, path);
        printArrayList(path);
        System.out.println();

        //(2)Вывод дочернего поддерева.
        System.out.print("\nВведите число(узел, поддерево которого вы хотите получить): ");
        treeNode = Integer.parseInt(consoleReader.readLine());
        System.out.println("Поддерево узла со значением " + treeNode + ":");

        childTree(treeNode, tree);
        System.out.println();


        //(3)Выбираем два произвольных узла и строим часть дерева, которая их соединяет.
        System.out.print("\nВведите два произвольных числа(узлы): ");
        String[] nodes = consoleReader.readLine().split("\\s+");

        int firstTreeNode = Integer.parseInt(nodes[0]);
        ArrayList<Integer> firstPath = new ArrayList<>();
        pathToTheRoot(firstTreeNode, tree, firstPath);

        int secondTreeNode = Integer.parseInt(nodes[1]);
        ArrayList<Integer> secondPath = new ArrayList<>();
        pathToTheRoot(secondTreeNode, tree, secondPath);

        connectionOfTwoNodes(firstPath, secondPath);

        consoleReader.close();
    }

    //Функция для 1-го задания.
    public static void pathToTheRoot(Integer treeNode, Integer[][] tree, ArrayList<Integer> path) {
        for (int i = 0; i < tree.length; i++) {
            if (tree[i][0] == treeNode) {
                if (tree[i][1] == null) {
                    path.add(treeNode);
                    break;
                }
                else {
                    path.add(treeNode);
                    Integer parent = tree[i][1];
                    pathToTheRoot(parent, tree, path);
                }
            }
        }
    }

    //Функция для 2-го задания
    public static void childTree(Integer treeNode, Integer[][] tree) {
        for (int i = 0; i < tree.length; i++) {
            if(tree[i][1] == treeNode) {
                int child = tree[i][0];
                System.out.print(treeNode + " -> " + child + "\n");
                childTree(child, tree);
            }
        }
    }

    //Функция для 3-го задания
    public static void connectionOfTwoNodes(ArrayList<Integer> firstPath, ArrayList<Integer> secondPath) {
        int firstPathIndex = 0;
        int secondPathIndex = 0;
        for (int i = 0; i < firstPath.size(); i++) {
            for (int j = 0; j < secondPath.size(); j++) {
                if (firstPath.get(i) == secondPath.get(j)) {
                    firstPathIndex = i;
                    secondPathIndex = j;
                    break;
                }
            }
            if (firstPathIndex != 0 || secondPathIndex != 0) break;
        }
        for (int i = 0; i <= firstPathIndex; i++) {
            if(i == firstPathIndex) System.out.print(firstPath.get(i));
            else System.out.print(firstPath.get(i) + " <- ");
        }
        for (int i = secondPathIndex - 1; i >= 0; i--) {
            System.out.print(" -> " + secondPath.get(i));
        }
    }

    //Вывод ArrayList'а на экран в красивом виде
    public static void printArrayList(ArrayList<Integer> list) {
        for(int i = 0; i < list.size(); i++) {
            if (i == list.size() - 1) System.out.print(list.get(i));
            else System.out.print(list.get(i) + " <- ");
        }
        System.out.println();
    }

}