验证二叉树的大小？

Question

我有这样的数据类型

datatype 'a bin_tree = 
    Leaf of 'a
  | Node of 'a bin_tree    (* left tree *)
           * int           (* size of left tree *)
           * int           (* size of right tree *)
           * 'a bin_tree   (* right tree *)

所以正确树的示例是：

val tree1 =
  Node(Node(Node(Leaf 47, 1, 1, Leaf 38),
            2,1,
            Leaf 55),
       3,2,
       Node(Leaf 27, 1, 1, Leaf 96))

违反树的例子是

val tree1false =
  Node(Node(Node(Leaf 47, 1, 1, Leaf 38),
            2,1,
            Leaf 55),
       4,2,
       Node(Leaf 27, 1, 1, Leaf 96))

如何编写谓词测试使得

- test tree1;
val it = true : bool
- test tree1false;
val it = false : bool

Answer 1

这是一道递归题。在解决树上的递归问题之前，最好牢牢掌握列表上的递归。您可以说树是列表的概括，或者列表是树的 special-cases：列表有一个尾巴，树可以有任意数量的尾巴，具体取决于树的类型。所以这里是你如何使用列表重建和解决问题：

如果您有一个列表，而不是典型的列表定义，它也记忆了自己的长度：

(* datatype 'a list = [] | :: of 'a * 'a list *)

datatype 'a lenlist = Nil | Cons of int * 'a * 'a lenlist

那你可以测试下存储的长度和实际值的个数是否一致

我将从创建一个计数函数开始，以说明函数中执行递归的部分：

(* For regular built-in lists *)
fun count0 [] = 0
  | count0 (x::xs) = 1 + count0 xs

(* Counting the memoized list type disregarding the n *)
fun count1 Nil = 0
  | count1 (Cons (n, x, xs)) = 1 + count1 xs

下一部分是我想在每个递归步骤中测试存储的数字 n 是否也符合实际计数。这个函数的 return 类型是什么？嗯，你要的test函数应该是'a lenlist -> bool，我做的count函数是'a lenlist -> int.

我建议你做一个 testcount 两者兼顾。但是您可以通过多种方式做到这一点，例如通过给它“额外的参数”，或者给它“额外的 return 值”。我将同时演示两者，只是为了表明有时一个比另一个更好，经验会告诉你哪个更好。

这是一个 val testcount1 : 'a lenlist -> bool * int 函数：

fun testcount1 Nil = (true, 0)
  | testcount1 (Cons (n, x, xs)) =
    let val (good_so_far, m) = testcount1 xs
        val still_good = good_so_far andalso n = m + 1
    in (still_good, m + 1)
    end

val goodList = Cons (4, #"c", Cons (3, #"o", Cons (2, #"o", Cons (1, #"l", Nil))))
val badList = Cons (3, #"d", Cons (2, #"e", Cons (1, #"r", Cons (0, #"p", Nil))))

测试这个，

- testcount1 goodList;
> val it = (true, 4) : bool * int
- testcount1 badList;
> val it = (false, 4) : bool * int

这表明 testcount1 returns 数字是否相加和列表的实际长度,这在递归期间是必要的，以测试每个步骤中的数字相加，但最后不再需要。您可以将此 testcount 函数包装在一个更简单的 test 函数中，该函数只关心 bool:

fun test xs = #1 (testcount1 xs)

这是另一种方法：testcount1 递归的方式不太令人满意。它会继续计算 m + 1，即使它能够确定列表（例如 Cons (0, #"p", Nil)）已损坏。

这里有一个替代方法 val testcount2 : 'a lenlist * int -> bool，它将一个数字存储在一个额外的参数中：

fun testcount2 (Nil, 0) = true
  | testcount2 (Nil, _) = false
  | testcount2 (Cons (n, x, xs), m) =
      n = m andalso testcount2 (xs, m - 1)

这对我来说似乎更简洁：函数是tail-recursive，当它感觉到有什么可疑的东西时它会立即停止。所以如果它在头部被破坏，它不需要遍历整个列表。缺点是它需要知道我们还不知道的长度。但是我们可以通过假设所宣传的内容是正确的来进行补偿，直到事实确实如此为止。

测试这个函数，你不仅需要给它一个goodList或一个badList，还要给它一个m:

- testcount2 (goodList, 4);
> val it = true : bool
- testcount2 (badList, 4);
> val it = false : bool
- testcount2 (badList, 3);
> val it = false : bool

重要的是这个函数不只是比较 n = m，因为在 badList 中，这会导致同意 badList 是 3 个元素长，因为 n = m 在所有 Cons 情况下的每次迭代都为真。这在要求我们达到 0 的两个 Nil 案例中有所帮助，例如~1 与 badList 的情况一样。

这个函数也可以包含在 test 中，以隐藏我们为它提供一个从 'a lenlist 本身派生的额外参数的事实：

fun size Nil = 0
  | size (Cons (n, _, _)) = n

fun test xs = testcount2 (xs, size xs)

到目前为止的一些道德：

有时需要创建辅助函数来解决您最初的问题。
这些辅助函数不限于与您提供的函数具有相同的类型签名（无论这是用于学校练习还是外部 API/library）。
有时它有助于扩展函数 returns 的类型。
有时它有助于扩展函数的参数。
仅仅因为你的任务是“编写一个函数 foo -> bar”，这并不意味着你不能通过编写 return 比 foo 多或少的函数来创建它] 或 bar.

现在，关于在二叉树上解决这个问题的一些提示：

重复数据类型，

datatype 'a bin_tree = 
    Leaf of 'a
  | Node of 'a bin_tree    (* left tree *)
           * int           (* size of left tree *)
           * int           (* size of right tree *)
           * 'a bin_tree   (* right tree *)

您可以根据上述想法为您的函数构建一个骨架：

fun testcount3 (Leaf x, ...) = ...
  | testcount3 (Leaf x, ...) = ...
  | testcount3 (Node (left, leftC, rightC, right), ...) = ...

我在这里嵌入了一些提示：

您的解决方案可能应该包含针对 Leaf x 和 Node (left, leftC, rightC, right) 的模式匹配。并且考虑到“额外参数”类型的解决方案（至少证明对列表很好，但我们会看到）需要两个 Leaf x 案例。为什么会这样？
如果在列表的情况下，“额外参数”m 代表列表的预期长度，那么在树的情况下，“额外参数”代表什么？你不能说“这是列表的长度”，因为它是一棵树。如何捕捉树枝的部分？
如果这仍然太难，请考虑解决没有 copy-pasting 的列表的问题。也就是说，您可以查看此答案中的解决方案（但尽量不要查看），但不允许 copy-paste 代码。如果你想复制它，你必须输入它。
首先，尝试定义使用的辅助函数 sizeo 从 testcount2 生成 test，但用于树木。因此，也许将其命名为 sizeTree 以避免名称重叠，但除此之外，请尝试使其相似。这是骨架：

fun sizeTree (Leaf x) = ...
  | sizeTree (Node (left, leftC, rightC, right)) = ...

将 testcount3 和 sizeTree 结合在一起，一旦编写，应该很容易。

验证二叉树的大小？

verifying size of binary trees?

sml

smlnj