Напишите функцию для построения дерева из списка

Question

Как написать функцию для построения дерева из списка в F #?

type Tree = 
     | Node of (Tree * Tree) 
     | leaf of int 

Если один читает надписи на дереве слева написать, то они должны быть в том же порядке, что и исходный список.

Answer 1

Вот несколько советов, которые помогут вам начать работу. Учитывая ваше определение Tree:

type Tree = 
    | Leaf of int 
    | Node of (Tree * Tree) 

Вы хотите определить функцию, которая строит Tree значение из списка целых чисел. Хорошая практика - разбивать проблемы на более мелкие части, поэтому вместо определения функции fromList вы можете начать с более простой функции для добавления одного элемента. Для этого вам просто нужно рассмотреть два случая, т.е. двух возможных форм деревьев, так огрызок такой функции уже дано:

let addInt n tree = 
    match tree with 
    | Leaf x  -> ?? 
    | Node (t1,t2) -> ?? 

После того, как вы выяснили, разумное определение можно продолжить, думая о том, как определить функцию, которая работает с списками и повторным использованием. addInt. На этот раз вы должны совпадать базовые случаи для списка:

let rec addMany xs tree = 
    match xs with 
    | []  -> ?? 
    | x :: xs -> ?? 

После того, как вы удобные проблемы разрешающих, как это с использованием явной рекурсии, вы можете взглянуть на List.fold упростить ваше решение.