SML에서 이진 트리의 가장 깊은 요소 찾기

Question

이것은 숙제 문제입니다.

내 질문에 간단합니다 : 형식의 btree_deepest 'a btree ->'트리의 가장 깊은 요소의 목록을 반환하는 목록을 작성하십시오. 트리가 비어 있으면 가장 깊은 곳에서 []를 반환해야합니다. 동일한 최대 깊이에 입력 트리의 요소가 여러 개있는 경우, 가장 깊은 요소는 선주문 순회에 따라 정렬 된 가장 깊은 요소가 포함 된 목록을 반환해야합니다. 함수는 제공된 btree_reduce 함수를 사용해야하며 재귀 적이어야합니다.

여기 내 코드입니다 :

(* Binary tree datatype. *) 
datatype 'a btree = Leaf | Node of 'a btree * 'a * 'a btree 

(* A reduction function. *) 
(* btree_reduce : ('b * 'a * 'b -> 'b) -> 'b -> 'a tree -> 'b) *) 
fun btree_reduce f b bt = 
    case bt of 
    Leaf => b 
    | Node (l, x, r) => f (btree_reduce f b l, x, btree_reduce f b r) 

(* btree_size : 'a btree -> int *) 
fun btree_size bt = 
    btree_reduce (fn(x,a,y) => x+a+y) 1 bt 

(* btree_height : 'a btree -> int *) 
fun btree_height bt = 
    btree_reduce (fn(l,n,r) => Int.max(l, r)+1) 0 bt 

나는 깊은 요소의 목록을 구축 할 수 btree_reduce에 전달하는 함수를 만들 필요가 있음을 알고 나는 비틀 거리는 오전 곳입니다.

재귀를 허용했다면 왼쪽 노드와 오른쪽 노드의 높이를 비교 한 다음 어느 것이 더 높은 지점에 재연 (또는 둘 다 동일한 높이에 있으면 재귀) 한 다음 현재 요소를 반환합니다. 높이가 0이고 이러한 요소를 목록에 던집니다. 난 그냥 시작하는 올바른 방향으로 밀어 필요가 있다고 생각

...

감사합니다!

업데이트 : 여기

컴파일하지 않는 솔루션에서 시도이다 :

fun btree_deepest bt = 
let 
val (returnMe, height) = btree_reduce (fn((left_ele, left_dep),n,(right_ele, right_dep)) => 
    if left_dep = right_dep 
     then 
      if left_dep = 0 
       then ([n], 1) 
       else ([left_ele::right_ele], left_dep + 1) 
     else 
      if left_dep > right_dep 
       then (left_ele, left_dep+1) 
       else (right_ele, right_dep+1) 
    ) 
    ([], 0) bt 
in 
    returnMe 
end 

Answer 1

을 최대 깊이의 요소를 취득하기 위하여는, 당신은 동시에 두 가지를 추적해야합니다 방문한 모든 하위 트리에 대해 btree_reduce : 해당 하위 트리의 최대 깊이 및 해당 깊이에서 발견 된 요소. 이 정보를 일부 데이터 구조로 감싸면 'b (btree_reduce의 서명에 따라) 유형이 있습니다.

btree_reduce에 제공하는 함수에서 두 개의 하위 트리 결과를 결합해야하는 경우 "왼쪽"하위 결과가 "더 깊음", "덜 깊음"또는 "같은 깊이입니다" "오른쪽"하위 결과로. 하위 결과는 각 하위 트리의 가장 깊은 노드의 깊이와 노드 값을 나타내며이를 결합하여 현재 트리의 가장 깊은 노드의 깊이와 값을 얻는 방법을 생각해보십시오.

포인터가 더 필요하다면 btree_deepest 구현을 가지고 있으며 공유 할 수 있습니다. 당신이 특별히 (그리고 명예롭게) 힌트를 요구했기 때문에 아직 그것을 게시하지 않았습니다. 해결책이 아닙니다.

Answer 2

코드를 살펴 보았습니다. X_ele이 단일 요소인지 또는 목록인지 여부에 따라 혼란이있는 것처럼 보이므로 형식 오류가 발생합니다. 위의 첫 번째 'else'브랜치에서 '@'연산자를 사용하십시오.

 if left_dep = 0 
      then ([n], 1) 
      else (left_ele @ right_ele, left_dep + 1)