标准机器学习二叉树遍历

Question

我是 SML 的新手，正在练习树遍历。这是问题的设置。

datatype 'a bTree = nil | bt of 'a bTree * 'a * 'a bTree;

我需要编写一个函数 inorder，它接受一个二叉树和 return 中序遍历树的所有成员的列表。

我写了这一行：

fun inorder(nil) = nil
  | inorder(bt(left,key,right)) = inorder(left) @ [key] @ inorder(right);

但是遇到一些错误，不知道如何解决：

Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z list * 'Z list
operand:         'Z list * 'Y bTree
in expression:
  (key :: nil) @ inorder right

Error: operator and operand don't agree [tycon mismatch]
operator domain: 'Z list * 'Z list
operand:         'Y bTree * _
in expression:
  inorder left @ (key :: nil) @ inorder right

Answer 1

您无意中隐藏了 nil 列表构造函数并将其替换为同名的树构造函数。

这意味着你的第一个案例，

inorder(nil) = nil

表示inorder的结果是一棵树；它的类型是

'a bTree -> 'a bTree

并且您不能将列表附加 (@) 到 'a bTree。

如果您重命名空树构造函数，您的代码将起作用：

datatype 'a bTree = nilTree | bt of 'a bTree * 'a * 'a bTree;

fun inorder nilTree = nil
  | inorder (bt(left,key,right)) = inorder left @ [key] @ inorder right;

或使用 [] 代替 nil。
不过，不隐藏 nil 是更好的解决方案。

标准机器学习二叉树遍历

Standard ML Binary Tree Traversal

binary-tree

sml

ml

tree-traversal