SML - 트리의 포스트 오더 스캔에서 목록을 만드는 방법

Question

SML에서 트리를 가져 와서 목록을 반환하는 함수를 구현하는 방법. 목록은 트리의 포스트 오더 스캔에 따라 트리 노드의 값으로 구성됩니다.

나무 datatype은 다음과 같습니다

에 의해 간단하게 수행 할 수 있습니다

datatype 'a Tree = Leaf | Branch of 'a * 'a Tree * 'a Tree; 

Answer 1

: 당신이 지점이 먼저이 하위 트리 (createList(left))에 남아있는 방문이있는 경우

fun createList(Leaf) = [] 
= | createList(Branch(el, left, right)) = createList(left) @ createList(right) @ [el]; 

, 다음 그것의 바로 하위 트리 (createList(right)) 그리고 나서 el 요소를 추가하십시오. 기본적으로 포스트 오더 트리 탐색이하는 일을 수행하십시오. Leaf (빈 트리)에서 목록을 만들려면 결과가 빈 목록이됩니다.

Answer 2

보다 효율적인 솔루션 :

local 
    fun helper Leaf result = result 
    | helper (Branch (el, left, right)) result = helper left (helper right (el::result)) 
in 
    fun createList tree = helper tree nil 
end 

이 완전히 긴장을 풀고있다 @의 왼쪽 인수가 반복적으로 적용하는 경우 매우 비싼되고 오른쪽 인수에 붙일 수 있기 때문에 더 효율적입니다 그것은 길고 긴 목록으로. 반대로 서브 트리의 포스트 오더 트래버 설을 전달 된리스트 앞에 추가하는 helper 함수를 사용하면 전체리스트를 한 번만 빌드 할 수 있습니다.