Как решить проблему с функцией вставки деревьев f # - PullRequest
Новая
       110

Как решить проблему с функцией вставки деревьев f #

0 голосов
/ 30 ноября 2018

Пожалуйста, мне нужна помощь в создании функции вставки для дерева.Значение в заданном списке строк должно быть вставлено в каждую ветвь и лист дерева.Я попытался решить эту проблему и получил очень близкий ответ, но я не могу написать функцию правильно, чтобы вставить все строковые значения.

Код: 

type Tree = Leaf of string | Branch of (string * Tree) list

let rec insertTree (lst : string list) (tree : Tree) : Tree =

        match lst, tree with
        | a::b::c::[], y  -> 
            match y with
            | Leaf(n) -> Branch[(a, Branch[(n, Leaf(c))])]
            | Branch[(x, p)] -> Branch[(x, Branch[(a, Branch[(b, insertTree (c::[]) p)])])]
            | _     -> insertTree (b::c::[]) y
        | _ , y    -> tree

Тест: insertTree ["4"; "5";"6"] (Branch [("1", (Branch[("2", Leaf("3"))]))])

Дает: Branch [("1", Branch [("4", Branch [("5", Branch [("2", Leaf "3")])])])]

Я хочу вместо этого: 

(Branch [("1", (Branch[("2", (Branch[("3",(Branch[("4",(Branch[("5", Leaf("6"))]))]))]))]))])

1 Ответ

0 голосов
/ 30 ноября 2018

Я предполагаю, что вы просто хотите добавить список к последнему листу, и что все ветви будут иметь не более одного элемента в своем списке. 

let insertTree (lst : string list) (tree : Tree) : Tree =
    let rec insertSingleIntotree x t = 
        match t with
        | Leaf(n) -> Branch[(n,Leaf x)]
        | Branch[(n,p)] -> Branch[(n, insertSingleIntotree x p)]
        | _ -> failwith "no idea what should happen here!"

    lst
    |> List.fold (fun acc x -> insertSingleIntotree x acc) tree
...