open System;

type Tree =
    | Leaf of string
    | InternalTree of string * Tree list

let createTree =
    let rec createInnerTrees node =
        let innerTreesNodes =
            Seq.initInfinite (fun id ->
                printf "Введите %A-й узел родительского узла %A (-1 для прекращения):\n" id node;
                Console.ReadLine())
            |> Seq.takeWhile (fun x -> x <> "-1")
            |> Seq.toList;

        let innerTrees =
            innerTreesNodes
                |> Seq.map (fun node ->
                    let nodeInnerTrees = createInnerTrees node;
                    match List.length nodeInnerTrees with
                        | 0 -> Leaf node
                        | _ -> InternalTree (node, nodeInnerTrees))
                |> Seq.toList;

        innerTrees

    printf "Введите корень дерева:\n"
    let root = Console.ReadLine();

    InternalTree (root, createInnerTrees root)

let rec isBinary (tree:Tree) =
    match tree with
        | Leaf _ -> true
        | InternalTree (_, innerTrees) ->
            (innerTrees.Length <= 2) && (innerTrees |> Seq.forall (fun innerTree -> isBinary innerTree))

let drawBinaryTree (tree:Tree) =
    let rec getOutputElements node x y=
        match node with
            | Leaf n -> [(n, x, y)]
            | InternalTree (n,innerTrees) ->
                let childElements = match innerTrees.Length with
                    | 1 ->
                        [("/",x-1,y+1)] @
                        [("/",x-2,y+2)] @
                        (getOutputElements (innerTrees.Item(0)) (x-3) (y+3))
                    | 2 ->
                        [("/",x-1,y+1)] @
                        [("/",x-2,y+2)] @
                        (getOutputElements (innerTrees.Item(0)) (x-3) (y+3)) @
                        [("\\",x+1,y+1)] @
                        [("\\",x+2,y+2)] @
                        (getOutputElements (innerTrees.Item(1)) (x+3) (y+3))

                [(n, x, y)] @ childElements

    let drawLine elements =
        let maxX =
            elements
            |> Seq.map (fun (_,x,_) -> x)
            |> Seq.max;

        let drawElement curX elements =
            let el = elements |> Seq.tryFind (fun (_,x,_) -> x = curX);
            if (el.IsSome) then
                printf "%s" (match el.Value with (s,_,_) -> s);
            else
                printf " "
            ()

        [0..maxX] |> Seq.iter (fun curX -> drawElement curX elements)
        printf "\n"
        ()

    let outputElements = getOutputElements tree 40 0

    let groups =
        outputElements
        |> Seq.groupBy (fun (_, _, y) -> y)
        |> Seq.sortBy (fun (key, value) -> key)
        |> Seq.iter (fun (key, value) -> drawLine value)

    ()

let printRegularTree (tree:Tree) =
    let rec printElement node  spaces =
        printf "%s" spaces;
        match node with
        | Leaf n ->
            printf "Лист: %s\n" n
        | InternalTree (n, innerTrees) ->
            printf "Узел: %s\n" n
            for node in innerTrees do printElement node (spaces + "   ")

    printElement tree "";

let printTree (tree:Tree) =
    if (isBinary tree) then
        drawBinaryTree tree
    else
        printRegularTree tree

let rec findElement (tree:Tree) el =
    match tree with
    | Leaf n -> n = el
    | InternalTree (n,innerTrees) ->
        (n = el) || (innerTrees |> Seq.exists (fun tree -> findElement tree el))

[<EntryPoint>]
let main argv =

    let tree = createTree;

    printTree tree;

    printf "Введите элемент, который надо найти\n";
    let node = Console.ReadLine();

    if (findElement tree node) then
        printf "Элемент %A найден\n" node
    else
        printf "Элемента %A нет в дереве\n" node

    Console.ReadLine() |> ignore;
    0