Ocaml list to tree

Question

我想写一个函数load: 'a option list -> 'a tree，它从给定的列表中恢复二叉树，它包含后缀顺序中的元素。 如果列表不代表任何树，你的函数应该引发异常 加载（你必须先声明它）。

树被定义为：

type ‘a btree = L of ‘a | N of ‘a btree * ‘a btree 

到目前为止，我所做的就是：

exception Load ;; 

let rec load l = 
    match l with 
     | [] -> raise Load 
     | Some x::_ -> L x 
     | None::t -> N(?,load t) 
;; 

下面是一个输入列表的一个例子：

[Some 2; Some 0; None; Some 5; Some 9; Some 20; None; None; None] 

这有点棘手怎么做。由于该列表是在后缀顺序，我想知道是否会更好地使用List.foldright函数？

Answer 1

我想你应该更努力做功课（当然有一些有趣的学习），但你显然不关心：

let load input = 
    let rec load stack = function 
    | [] -> stack 
    | Some elem :: rest -> load (L elem :: stack) rest 
    | None :: rest -> 
     match stack with 
     | right :: left :: stack -> load (N(left, right) :: stack) rest 
     | [] | [_] -> failwith "incorrect node arity" 
    in 
    match load [] input with 
    | res :: [] -> res 
    | [] -> failwith "no input" 
    | _ :: _ :: _ -> failwith "remaining nodes"