1

与えられたリストからバイナリツリーを復元する関数を書きたいと思いますload: 'a option list -> 'a tree。このリストには、接尾辞の順序で要素が含まれています。リストがツリーを表していない場合、関数は例外Loadを発生させる必要があります（事前に宣言する必要があります）。

ツリーは次のように定義されます：

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関数を使ったほうがいいのかな？

4

1 に答える 1

6

宿題をもっと頑張るべきだと思いますが（確かに何か面白いことを学ぶことがあります）、どうやら気にしないので：

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"
于 2012-05-29T15:21:35.530 に答える