在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

列表应像这样转换为树---> 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屋！