list - 在 F# 中将整数列表转换为树

Question

我是 F# 新手，想知道如何将简单的整数列表转换为树。

let lst =[1;2;3;4]
type Tree=
 |Leaf of int
 |Node Tree * Tree

列表应该像这样转换成树---> Leaf 1,Node(Leaf 2),Node(Node(Leaf 3,Leaf 4))

Answer 1

您希望在答案中获得的输出格式有点差，但我的解释是您正在尝试构建平衡的二叉树。要递归地执行此操作，您需要将输入列表分成两半，然后从左半部分和右半部分递归地构建树。

这有点棘手，因为将功能列表分成两半并不是那么简单。在实践中，您可能可以将数据转换为数组并使用它，但如果您想要一个功能解决方案，您可以使用：

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

let rec half marker acc xs = 
  match xs, marker with
  | x::xs, _::_::marker -> half marker (x::acc) xs
  | x::xs, _::[] -> List.rev (x::acc), xs
  | xs, _ -> List.rev acc, xs

该half函数的诀窍是它遍历列表并保留列表的两个副本。从一个（称为marker）开始，它在每一步都需要两个元素，所以当这个列表为空时，你已经到达了原始列表的中间，我们在每一步只取一个元素。

现在您可以编写一个简单的递归函数来构建一棵树

let rec makeTree = function
  | [] -> failwith "Does not work on empty lists"
  | [x] -> Leaf x
  | xs ->  let l, r = half xs [] xs
           Node(makeTree l, makeTree r)