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, которая предшествует обходу пост-заказа поддерева в переданный список, вы можете создать весь список только один раз.