时间戳

首页 > 解决方案 > SML 遍历 N 叉树

tree - SML 遍历 N 叉树

问题描述

我是 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)

谢谢你的帮助。

标签： treesml

解决方案

由于traverse是从树到树的函数，因此您可以遍历列表中的所有子树map（并且您不需要特殊情况）：

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

推荐阅读