基于Robert Harper的SML二叉树定义，如何构造指定树的根节点？

根据给定的SML互递归类型定义：

datatype 'a tree =
  Leaf
| Node of 'a branch * 'a branch
and 'a branch =
  Branch of 'a * 'a tree;

你构造的ten其实就是目标树的根节点，只是它的类型是int branch而非你预期的int tree。这里的核心是理清两个类型的角色：

• 'a tree代表无值的树结构：要么是空结构（Leaf），要么是由两个带值分支组合成的分叉结构（Node）；
• 'a branch代表带根值的完整树：包含一个具体值，以及该值对应的下一级树结构。

你想要的目标树是一个以10为根、左右子树分别为5和11分支的完整树，正好对应你定义的val ten = Branch (10, Node (five, eleven));——这就是符合要求的根节点。

如果强行要求根节点是'a tree类型，那根据定义它只能是Leaf或Node(branch, branch)，这种结构本身不包含根值，和你想要的目标树结构不匹配。

内容的提问来源于stack exchange，提问作者Ahmed Riza