在 F# 中将整数列表转换为树 [英] Convert integer list into tree in F#

问题描述

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

I'm new to F# and would like to know how to convert a simple integer list into a tree.

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

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

list should convert to tree like this ---> Leaf 1,Node(Leaf 2),Node(Node(Leaf 3,Leaf 4))

推荐答案

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

The output that you want to get in your answer is a bit poorly formatted, but my interpretation is that you are trying to build a balanced binary tree. To do this recursively, you need to split the input list in two halves and then recursively build tree from the left and the right halves.

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

This is a bit tricky, because splitting a functional list in halves is not that simple. In practice, you could probably turn your data into an array and use that, but if you want a functional solution you can use:

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)开始，它在每一步都需要两个元素，所以当这个列表为空时，你已经到达了原始列表的中间，在那里我们每一步只需要一个元素.

The trick in the half function is that it iterates over the list and keeps two copies of the list. From one (called marker), it takes two elements at each step and so by the time this list is empty, you have reached the middle of the original list where we take just one element at each step.

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

Now you can write a simple recursive function to build a tree

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)

这篇关于在 F# 中将整数列表转换为树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！