在SML中对树计数后修改元组

Question

我有一个问题，我正在研究，我必须遍历一棵树一次，并计算每个节点有多少个子节点。

有两部分:数据类型和函数本身。

---

数据类型

数据类型要求内部节点存储任何类型的值，并且有1-3个子节点。叶子本身存储一个实数或一个字符串列表。

datatype leaf = Slist of string list | Real of real;
datatype tree = Empty
              | Leaf of leaf
              | Node of leaf * 'a tree
              | Node of leaf * 'a tree * 'a tree
              | Node of leaf * 'a tree * 'a tree * 'a tree

---

接下来，我必须定义一个函数，它接受一个树，并返回一个元组(n1, n2, n3)，其中n1是有一个子节点的节点数，n2有两个子节点的节点数，n3有三个子节点的节点数。

fun myChildren (t:'a tree) = childHelper (t, (0,0,0));

fun childHelper (t: 'a tree, (n1, n2, n3):int*int*int) =
  case t of
    Empty => 0
    | Node (x) => childrenHelper(t, (n1 + 1, n2, n3))
    | Node (x, y) => childrenHelper(t, (n1 + 1, n2 + 1, n3))
    | Node (x, y, z) => childrenHelper(t, (n1 + 1, n2 + 1, n3 + 1));

---

我刚开始使用数据类型和用例，所以对我来说很困惑。我想知道，我的数据类型是表示树的最佳方式吗?如何让函数递归地遍历树呢?它只计算树的第一个节点，而不是所有节点。我也省略了它是叶节点的情况，因为此时我不需要做任何事情。

我知道在列表中，你可以执行hd::tl，有没有一种方法可以在树上执行这样，遍历节点后，在每个节点上调用函数?

例如，对于Node (x, y, z)，它应该在每个节点上调用childhelper，但同时，维护元组上的数字。有什么好主意吗?

Answer 1

首先，一个数据类型不能有多个命名相同的构造函数。其中一个将不可避免地笼罩另一个。如果您运行这段代码，您将得到类似以下的警告:

! datatype tree = Empty
!               | Leaf of leaf
!               | Node of leaf * 'a tree
!               | Node of leaf * 'a tree * 'a tree
!               | Node of leaf * 'a tree * 'a tree * 'a tree
! Unguarded type variables at the top-level

这是因为定义使用的类型参数'a没有声明为树类型的一部分。将其更改为datatype 'a tree = ...，你会得到这个错误:

!                  | Node of leaf * 'a tree * 'a tree
!                    ^^^^
! Illegal constructor specification: the constructor cannot be specified twice for the same datatype

你可以使用三个不同的构造函数，例如

datatype 'a tree = Empty
                 | Node0 of leaf
                 | Node1 of leaf * 'a tree
                 | Node2 of leaf * 'a tree * 'a tree
                 | Node3 of leaf * 'a tree * 'a tree * 'a tree

我的数据类型是表示树的最佳方式吗?

是的，你的数据类型很好。

我如何使我的函数递归地遍历树?

你可以用不同的方法遍历树。参见树遍历和折叠树。

在一个列表中，你可以做hd::tl，有没有一种方法可以在树上做这样，在遍历节点后，我调用每个节点上的函数?

您可以创建一个类似于fold的副同态函数，但其中参数化函数将整个节点而不仅仅是节点中的元素作为参数:

fun para f e t =
   let val e1 = f (e, t)
   in  case t of
            Empty                 => e1
          | Node0 x                => e1
          | Node1 (x, t1)         => para f e1 t1
          | Node2 (x, t1, t2)     => para f (para f e1 t1) t2
          | Node3 (x, t1, t2, t3) => para f (para f (para f e1 t1) t2) t3
   end

计算具有1、2和3个子树的节点的数量是这个函数的专门化:

fun nodecount t =
    let fun helper ((one, two, three), t) =
            case t of
                 Empty   => e1
               | Node0 _  => (one, two, three)
               | Node1 _ => (one+1, two, three)
               | Node2 _ => (one, two+1, three)
               | Node3 _ => (one, two, three+1)
    in para helper (0,0,0) t end

---

Edit:是的，上面的数据类型实际上是冗余的，因为只有一个叶子x的树可以写成:

val one_leaf = Node0 (x)
val one_leaf = Node1 (x, Empty)
val one_leaf = Node2 (x, Empty, Empty)
val one_leaf = Node3 (x, Empty, Empty, Empty)

如果您删除Empty，这种冗余将消失，但您不能再表示空树。克服这个问题的一个简单方法是使用两个类型:

datatype 'a tree = Empty | NonEmpty of 'a tree_aux
and 'a tree_aux = Node0 of leaf
                | Node1 of leaf * 'a tree_aux
                | Node2 of leaf * 'a tree_aux * 'a tree_aux
                | Node3 of leaf * 'a tree_aux * 'a tree_aux * 'a tree_aux 

或者如果您喜欢更少的构造函数和由已有的构造函数组成的类型:

datatype leaf = Slist of string list | Real of real;
datatype 'a tree = Empty | NonEmpty of 'a tree_aux
and 'a tree_aux = Node of leaf * ('a tree_aux * ('a tree_aux * 'a tree_aux option) option) option

但是这有点麻烦