在SML中查找2-3树中的节点数

Question

我期中考试快到了，所以我正在做练习题。我不知道如何开始这个问题。

2-3树是这样的树，其中每个非叶节点可以具有两个或三个子节点，并且节点的所有子树具有相同的高度。如果我们忽略子树高度的条件，我们可以进行以下SML类型定义：

数据类型‘a twoThreeTree =|空

|‘a*’a twoThreeTree *‘a twoThreeTree的二进制

|三元of‘a*’a twoThreeTree *‘a twoThreeTree *’a twoThreeTree；

a.编写一个递归函数N来计算2-3树中的节点数。

b.编写一个递归函数ht来计算2-3树的高度。(与二叉树类似，将空树的高度设为-1。

如果有什么不同的话，那就是a部分的帮助就足够了。我想我可以用我从a)学到的东西来做b)。

Answer 1

这应该对(a)有帮助。

fun N(Empty)            = 0
  | N(Binary(_,x,y))    = 1 + (N(x)) + (N(y))
  | N(Ternary(_,x,y,z)) = 1 + (N(x)) + (N(y)) + (N(z))

我们假设Empty的节点数量为0，对于其他类型的节点，我们计算节点本身和其他节点的数量。

对于b，而不是将它们相加在一起。考虑一下如何定义以下树的高度

         NODE
         / \
LEFT_TREE   RIGHT_TREE

如果LEFT_TREE的高度为H_left，而RIGHT_TREE的高度为H_right。您能否将整个树的高度表示为H_left和H_right的函数？如果这棵树有三个孩子呢？

fun ht(Empty)            = -1
  | ht(Binary(_,x,y))    = ...
  | ht(Ternary(_,x,y,z)) = ...