标准ML二叉树遍历

Question

我是SML的新手并且正在进行关于树遍历的练习.这是问题的设定.

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

我需要编写一个函数inorder,它接受一个二叉树并在inorder遍历中返回树的所有成员的列表.

我写了这一行:

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是更好的解决方案.