SML - 如何創建樹的後序掃描列表

Question

如何在SML中實現一個獲取樹並返回列表的函數。根據樹的後序掃描，列表由樹節點中的值組成。

樹datatype是：

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

Answer 1

，可以簡單地這樣做：

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

如果你有一個分支首先訪問它的左子樹（createList(left)），那麼它的右子樹（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函數來預先將子樹的後序遍歷到傳入的列表中，您可以只構建一次整個列表。