标准 ML：修改二叉树的深度函数

Question

我得到了一个二叉树的深度函数，如下所示：

fun depth Empty = 0
    | depth(Node(t_1, _ t_2)) = max(depth t_1, depth t_2) + 1;

假设我想修改这个深度函数，使单个节点的深度为 0（实际上，单个节点的深度为 1）。我该怎么做？

我在想：

fun depth Empty = 0
    | depth(Node(Empty, _, Empty)) = 0
    | depth(Node(t_1, _, t_2)) = max(depth t_1, depth t_2) + 1;

这样看起来对吗？

谢谢，

克莱曼

Answer 1

这很接近，但不太正确。 depth(Node(Node(Empty,1,Empty),2,Empty) 将在左子树上递归，它是一个节点，因此它将 return 0。然后它会在右边递归，它是空的，returning 0。然后你将取 0 和 0 的最大值，returning 1，这可能不是你想要的。相反，您必须像您所做的那样匹配空案例和单例案例，对于默认案例，您将需要调用原始版本，即 returns 1 用于单个节点。

标准 ML：修改二叉树的深度函数

Standard ML: Modify depth function for binary tree

functional-programming

sml