#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <fstream>
#include <stdio.h>
#include <string.h>

#define MIN_SIZE 0
#define MAX_SIZE 20
#define MAX_DEPTH 4
#define OFFSET 20
#define LEFT 0
#define RIGHT 1

using namespace std;

struct Node {
    int field;
    Node* left;
    Node* right;
};

int childs[21];
int maxPath = 0;
int ansArr[21] = { 0 };
short matrix[21][21];

int inputValue(int min, int max);
int userInputFromConsole();
Node* userInputFromFile();
bool checkPath(string path);
string userInputPath();
short inputMethod();
void printInConsole(string ans);
string userOutputPath();
void printInFile(string ans, string path);
short outputMethod();
void start();
void printTask();
Node* add(Node* tree, int n);

int inputValue(int min, int max) {
    int currentValue;
    bool isNotValid = true;
    do {
        cin >> currentValue;
        if (currentValue >= min && currentValue <= max)
            isNotValid = false;
        else
            cout << "Введите число в заданном диапазоне\n";
    } while (isNotValid);
    return currentValue;
}

int userInputFromConsole() {
    int n;
    cout << "Введите вершину в диапазоне " << MIN_SIZE + 1 << ".." << MAX_SIZE << ", 0 - для окончания построения дерева" << ": ";
    n = inputValue(MIN_SIZE, MAX_SIZE);
    return n;
}

Node* userInputFromFile() {
    int n;
    Node* tree = NULL;
    string path = userInputPath();
    ifstream file(path);
    file.open(path);
    file.clear();
    while (!file.eof()) {
        file >> n;
        tree = add(tree, n);
    }
    file.close();
    return tree;
}

bool checkPath(string path) {
    ifstream file(path);
    if (file.is_open()) {
        cout << path << " найден" << endl;
        return true;
    }
    else {
        cout << path << " не найден" << endl;
        return false;
    }
}

string userInputPath() {
    string path;
    bool isNotValid = false;
    do {
        cout << "Введите абсолютный путь к файлу с входными данными" << endl;
        cin >> path;
    } while (!checkPath(path));
    return path;
}

short inputMethod() {
    short method;
    cout << "Каким способом хотите ввести данные?" << endl;
    cout << "1 - с помощью консоли" << endl;
    cout << "2 - с помощью файла" << endl;
    do {
        cin >> method;
        if (method != 1 && method != 2)
            cout << "Введите 1 или 2" << endl;
    } while (method != 2 && method != 1);
    return method;
}

void printInConsole(string ans) {
    cout << ans;
}

string userOutputPath() {
    string path;
    cout << "Введите абсолютный путь к файлу для вывода результата" << endl;
    cin >> path;
    return path;
}

void printInFile(string ans, string path) {
    ofstream file(path);
    file << ans;
    cout << "Результат работы помещён в файл";
}

short outputMethod() {
    short method;
    cout << "Куда хотите вывести результат?" << endl;
    cout << "1 - в консоль" << endl;
    cout << "2 - в файл" << endl;
    do {
        cin >> method;
        if (method != 1 && method != 2)
            cout << "Введите 1 или 2" << endl;
    } while (method != 2 && method != 1);
    return method;
}

void printResult(string ans) {
    short method = outputMethod();
    if (method == 1)
        printInConsole(ans);
    else {
        string path = userOutputPath();
        printInFile(ans, path);
    }
}

short getTreeDepth(Node* tree) {
    if (tree == NULL)
        return 0;
    else
        return 1 + max(getTreeDepth(tree->left), getTreeDepth(tree->right));
}

Node* add(Node* tree, int n) {
    if (tree == NULL) {
        Node* tree = new Node;
        tree->field = n;
        tree->left = NULL;
        tree->right = NULL;
        return tree;
    }
    else if (n < tree->field)
        tree->left = add(tree->left, n);
    else if (n > tree->field)
        tree->right = add(tree->right, n);
    else
        cout << "Элемент " << n << " уже был добавлен в дерево" << endl;
    return tree;
}

int foo(short n) {
    switch (n) {
    case 1:
        return 8;
        break;
    case 2:
        return 4;
        break;
    case 3:
        return 2;
        break;
    case 4:
        return 0;
        break;
    default: return -1;
    }
}

void printTree(Node* tree, int currentSet, short depth, int index, char** str) {
    if (!tree || depth < 1 || depth > MAX_DEPTH)
        return;
    int x = currentSet;
    int z = foo(depth);
    char* s = str[index];
    s += currentSet - 1;
    int a = sprintf(s, "%2d", tree->field);
    s[2] = ' ';
    currentSet--;
    index++;
    for (int j = 0; j < z; j++) {
        s = str[index];
        s += currentSet;
        if (tree->left)
            s[0] = '/';
        s += (x - currentSet) * 2;
        if (tree->right)
            s[0] = '\\';
        index++;
        currentSet--;
    }
    printTree(tree->left, currentSet, depth + 1, index, str);
    printTree(tree->right, (x + z + 1), depth + 1, index, str);
}

void getTreeAsMatrix(Node* tree, short matrix[21][21]) {
    if (tree->left) {
        matrix[tree->field][tree->left->field] = 1;
        matrix[tree->left->field][tree->field] = 1;
        getTreeAsMatrix(tree->left, matrix);
    }
    if (tree->right) {
        matrix[tree->field][tree->right->field] = 1;
        matrix[tree->right->field][tree->field] = 1;
        getTreeAsMatrix(tree->right, matrix);
    }
}

void getChilds(Node* tree, int childs[21]) {
    if (tree->left)
        childs[tree->field]++;
    if (tree->right)
        childs[tree->field]++;
    if (tree->left)
        getChilds(tree->left, childs);
    if (tree->right)
        getChilds(tree->right, childs);
}

void DFS(int now, int path[21], int step, short child, int lengthPath, int visited[21]) {
    if (visited[now] > 0)
        return;
    visited[now] = now;
    path[step] = now;
    if (childs[now] != child)
        if (maxPath < lengthPath) {
            maxPath = lengthPath;
            for (int i = 1; i < lengthPath + 1; i++)
                ansArr[i] = path[i];
        }
    for (int i = 1; i < 21; i++)
        if (i != now)
            if (matrix[now][i] == 1)
                DFS(i, path, step + 1, child, lengthPath + 1, visited);
}

void printTask() {
    cout << "Деревья. Найти путь максимальной длины между вершинами с разным числом потомков." << endl;
}

void start() {
    printTask();
    int n = 1;
    Node* tree = NULL;
    short method = inputMethod();
    if (method == 1)
        while ((n = userInputFromConsole()) != 0) {
            tree = add(tree, n);
        }
    if (method == 2) {
        tree = userInputFromFile();
    }
    char** str = new char*[64];
    for (int i = 0; i < 64; i++) {
        str[i] = new char[64];
        memset(str[i], ' ', 64);
        str[i][63] = 0;
    }
    printTree(tree, OFFSET, 1, 0, str);
    int size = getTreeDepth(tree);
    int j = size;
    for (int i = 0; i < j; i++)
        size += foo(i);
    for (int i = 0; i < size + 1; i++)
        cout << str[i] << endl;
    for (int i = 0; i < 64; i++) {
        delete(str[i]);
    }
    delete(str);

    getTreeAsMatrix(tree, matrix);
    string ans = "";
    int arr[21];
    getChilds(tree, childs);
    for (int i = 1; i < 21; i++) {
        for (int j = 1; j < 21; j++) {
            arr[j] = 0;
        }
        DFS(i, arr, 1, childs[i], 1, arr);
    }
    for (int i = 1; i < maxPath + 1; i++)
        if (ansArr[i] != 0)
            ans += to_string(ansArr[i]) + "->";
    ans.erase(ans.size() - 2, 2);
    printResult(ans);
}

int main()
{
    setlocale(LC_ALL, "Russian");
    start();
}