Ocaml，二叉树的级别函数

Question

我想为二叉树实现级别函数，它将二叉树转换为列表 list int 并且每个 list int 需要包含当前级别的所有值：例如：

              9
         6          10
     5     7              11
 42   
 42
 42

[[9];[6;10];[5;7;11];[42];[42];[42]]

我需要使用这种类型 fold_bin_tree

type 'a bin_tree =
   Node of 'a bin_tree * 'a * 'a bin_tree | Null;;


let rec fold_bin_tree f a t =
  match t with
  Null ->a |
  Node (l,x,r) ->f x (fold_bin_tree f a l) (fold_bin_tree f a r);;

我已经实现了合并函数作为助手，这就是我的代码：

let merge l1 l2 = (*[[a b c] [d e]] merge [[1] [2 3] [4]] = 
[[a b c 1] [d e 2 3] [4]]*)
let rec scan l1 l2 acc =
  match l1,l2 with
  | [],[] -> acc
  | h1::t1,[] -> scan t1 l2 (h1::acc)
  | [], h2::t2 -> scan l1 t2 (h2::acc)
  | h1::t1,h2::t2 -> scan t1 t2 ((h1@h2)::acc)
  in scan l1 l2 [];;

let levels t =
  fold_bin_tree
  (fun x levels_l levels_r -> let lev = merge levels_l levels_r in
    [x]::lev
  ) [] t;;

我测试了合并，它似乎运行良好，但我的关卡无法正常运行，因为

levels example

returns [[9];[5;7];[42];[42];[42;11];[6;10]]

其中示例是我在 post

开头显示的那棵树

  let example = Node(  Node(Node(Node(Node(Node(Null,42,Null),42,Null),42,Null),5,Null), 6 ,Node( Null, 7 ,Null )) ,9, (Node(Null, 10 ,Node(Null,11,Null))));;

Answer 1

提示：为什么你的函数 merge returns

 merge [[1];[2]] [];;

[[2]; [1]]

?

Ocaml，二叉树的级别函数

Ocaml, levels function for binary tree

binary-tree

ocaml