tree - OCaml - 在树中解析节点

Question

我想将级别上的所有节点写入列表。

type 'a tree = T of 'a * 'a tree * 'a tree;;

 let at_level t lvl=
      let rec aux t k =
         match t with
        |Leaf -> []
        |T(x, l, r) -> if k = lvl then 
           (x::aux l (k+1)) @ (aux r (k+1))
        else 
        (aux l (k+1)) @( aux r (k+1))
      in aux t lvl;;

但我总是收到结果：[x] 其中 x 是根的值。我的程序中的问题在哪里？

Answer 1

问题是你aux t lvl在你应该打电话的时候打电话aux t 0，否则你总是k = lvl从一开始就有（即在树的根部）。

aux l (k+1)另外，当您已经找到正确的级别时，为什么还要打电话？之后的k = lvl平等不可能是真的。

无论如何，这是带有一些格式更改的代码：

type 'a tree = T of 'a * 'a tree * 'a tree | Leaf;;

let at_level tree lvl =                                       
  let rec aux t k = match t with                                
    |Leaf -> []                                                   
    |T(value, left, right) when k = lvl -> [value]                
    |T(value, left, right) -> (aux left (k+1)) @ (aux right (k+1))
  in aux tree 0;;


# let tree = T(5,T(6,Leaf,Leaf),T(7,Leaf,Leaf));;
# at_level tree 1;;
- : int list = [6; 7]