骆驼列表到树 [英] Ocaml list to tree

问题描述

我想编写一个函数load: 'a option list -> 'a tree，该函数从给定列表中恢复二叉树，该列表包含后缀顺序的元素. 如果列表不代表任何树，则您的函数应引发异常 加载(必须提前声明).

I want to write a function load: 'a option list -> 'a tree, that restores binary tree from the given list, which contains the elements in postfix order. If the list does not represent any tree, your function should raise the exception Load (you have to declare it earlier).

树定义为:

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

到目前为止，我所做的是:

So far what I did was :

exception Load ;;

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

以下是输入"列表的示例:

Here's an example of an Input list:

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

如何做到这一点有些棘手.由于列表按后缀顺序排列，所以我想知道使用List.foldright函数??会更好吗?

It's kind of tricky how to do it. Since the list is in postfix order, I'm wondering if it will be better to use List.foldright function ??

推荐答案

我认为您应该更加努力地做功课(肯定有一些有趣的东西要学习)，但是您显然不在乎:

I think you should try harder to do your homework (surely there is something interesting to learn), but as you apparently don't care:

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"

这篇关于骆驼列表到树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！