將整數列表轉換爲F中的樹＃

Question

我是F＃的新手，想知道如何將簡單整數列表轉換爲樹。

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

列表應該轉換成樹這樣的--->葉1，節點（葉2），節點（節點（葉3，葉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功能巧妙之處在於它遍歷列表，並有兩隻清單的副本。從一個（稱爲）開始，每個步驟都需要兩個元素，所以當這個列表爲空時，您已經到達原始列表的中間位置，每個步驟只有一個元素。

現在你可以寫一個簡單的遞歸函數來構建樹

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)