标准ML二叉树遍历

Question

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

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

我需要编写一个函数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是更好的解决方案。