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 0时，您打电话aux t lvl，否则您将始终拥有k = lvl（即在树的根部）。

另外，当你已经找到正确的级别时，为什么要叫aux l (k+1)？之后的平等不可能是真实的。

总之，这里的有几个格式更改代码：

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]