SML 遍历 N 叉树

Question

我是 SML 的新手。

经过几次搜索，我仍然找不到任何与遍历 n 叉树相关的资源。很多例子只是遍历一个简单的二叉树。

说，我有

datatype 'a tree = leaf of 'a list | node of 'a tree list

我想遍历这棵 n 叉树并返回完全相同的树 (val traverse = fn : 'a tree -> 'a tree)

我该怎么办？

这是我的代码：

fun traverse (leaf x) = (leaf x)
  | traverse (node []) = node []
  | traverse (node [x]) = node [x]

我正在努力添加最后一个模式，即（这是错误的）

  | traverse (node (x::xs)) = traverse (node x) :: traverse (xs)

感谢您的帮助。

Answer 1

由于traverse是从树到树的函数，所以可以用map遍历列表中的所有子树（不需要特例）：

fun traverse (leaf x) = leaf x
  | traverse (node xs) = node (map traverse xs)

SML Traverse an N-ary tree