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]