module BinaryTree

// 节点类型
type Node<'a> =
    {
        Value : 'a
        Left : Node<'a> option
        Right : Node<'a> option
    }

// 创建二叉树
let myTree =
    {
        Value = 150
        Left =
            Some({
                    Value = 30
                    Left = None
                    Right = Some({Value = 5;Left = None;Right = None})
                })
        Right =
            Some({
                    Value = 45
                    Left = Some({Value = 15;Left = None;Right = None})
                    Right = None
                })
    }

// 先序遍历
let rec IterPreorder (f : 'a -> unit) (root : Node<'a>) =
    f root.Value
    if root.Left.IsSome then
        IterPreorder f root.Left.Value
    if root.Right.IsSome then
        IterPreorder f root.Right.Value

// 对myTree执行先序遍历
printfn "Preorder Iter:"
myTree |> IterPreorder (fun x -> printfn "%A" x)

// 广度优先遍历
let BFSIter (f : 'a -> unit) (root : Node<'a>) =
    let nextLayer (x : Node<'a> list) =
        x
        |> List.map (fun x -> [x.Left;x.Right])
        |> List.reduce (fun x y -> List.append x y)
        |> List.filter (fun x -> x.IsSome)
        |> List.map (fun x -> x.Value)
    let mutable iterQueue : Node<'a> list = [root]
    while not iterQueue.IsEmpty do
        List.iter (fun x -> f x.Value) iterQueue
        iterQueue <- nextLayer iterQueue

// 对myTree执行BFS遍历
printfn "BFS Iter:"
myTree |> BFSIter (fun x -> x |> printfn "%A")

// 求二叉树深度
let rec Depth (root : Node<'a>) =
    1 + max
        (match root.Left with
        |Some(x) -> Depth x
        |None -> 0)
        (match root.Right with
        |Some(x) -> Depth x
        |None -> 0)

// 求myTree深度
myTree |> Depth |> printfn "Depth:%A"