标准 ML：二叉树的大小计算不正确？

Question

我的书有以下函数计算二叉树中非叶节点的数量：

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

假设我想计算二叉树中的所有个节点。我将如何修改此功能来做到这一点？

这是我的想法：

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

这样看起来对吗？

谢谢，

克莱曼

Answer 1

Matt 是正确的，您的两个函数在功能上是相同的——两者都是 return 树中 all 个节点的计数。一开始我没有注意到这一点，因为我从表面上看你的第一个函数计算了 nonleaf 节点，然后注意到你的 Node(Empty,_,Empty) 模式是叶子的正确模式（如果叶子被定义为没有非空子节点的节点）。但是——这意味着书中的函数不仅仅计算非叶（父）节点。如果你确实想要一个只计算父节点的函数，毕竟你的模式有一个用途：

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

如果您的树应用程序大量使用父节点与叶节点的区别，您可以（以让您的一些函数定义更加复杂为代价）放弃 Node 构造函数支持单独的 Parent 和 Leaf 构造函数。类似于：

datatype 'a tree = Empty | Leaf of 'a | Parent of 'a tree * 'a * 'a tree;

然后你可以这样写函数

fun countLeaves Empty = 0
    | countLeaves (Leaf _) = 1
    | countLeaves (Parent(t1,_,t2)) = countLeaves t1 + countLeaves t2;

例如

- val t = Parent(Parent(Leaf "2", "*", Leaf "3"), "+", Leaf "4");
- countLeaves t;
val it = 3 : int

Answer 2

您提供的两种实现实际上是相同的。你的第二个实现的第二种情况是你的第三个模式的特例。对于您的第一个实现，size(Node(Empty,1,Empty)) 将递归左子树，返回 0，递归右子树，即 returns 0，然后加 1，得到结果 1。实际上，如果您切换第二种和第三种情况的顺序，编译器会告诉你是多余的：

test.sml:3.5-5.38 Error: match redundant
      Empty => ...
      Node (t_1,_,t_2) => ...
-->   Node (Empty,_,Empty) => ...

标准 ML：二叉树的大小计算不正确？

Standard ML: Size of binary tree computed incorrectly?

functional-programming

sml