sml - 如何在机器学习编程语言中定义具有多种类型的树

Question

好吧，我被要求做接下来的事情:

要定义一个可以包含两种不同类型的二叉树:('a,'b) abtree，以下是要求:

1. 任何内部顶点(不是叶子)都必须是“a”或“b”类型，并且叶子没有值。

2. 对于树中的每个路径，所有 'a 值必须出现在 'b 值之前:路径示例:

   'a->'a->'a-'b (legal)
   'a->'b->'b (legal)
   'a->'a->'a (legal)
   'b->'b->'b (legal)
   'a->'b->'a (ILLEGAL)
   

而且我还需要定义另一棵树，它类似于上面描述的树，但现在我也有了 'c ，在第二个要求中，它说对于每个路径，我 'a 值出现在 'b 值之前，并且所有'b 值出现在 'c 值之前。

首先，我不确定如何定义二叉树以使其具有超过 1 种类型。我的意思是最简单的二叉树是:

datatype 'a tree =
          leaf
         | br of 'a * 'a tree * 'a tree;

以及如何定义一棵树来满足这些要求。

任何帮助将不胜感激。

谢谢。

<小时/>

好的，非常感谢。所以你的意思是这样的:

datatype 'b bTree = 
          leaf
        | bBranch of 'b * 'b bTree * 'b bTree
;
datatype ('a,'b) abTree = 
          leaf
        | aBranch of 'a * ('a, 'b) abTree * ('a,'b) abTree
        | bBranch of 'b * 'b bTree * 'b bTree
;

这就是我在上面提到的 3 类型树的情况下所做的:

datatype 'c cTree =  
    leaf
    | cBranch of 'c * 'c cTree * 'c cTree
;


datatype ('b, 'c) bcTree = 
            leaf
    | bBranch of 'b * ('b, 'c) bcTree * ('b,'c) bcTree
    | cBranch of 'c * 'c cTree * 'c cTree

;

datatype ('a, 'b, 'c) abcTree = 
    leaf
            | aBranch of 'a * ('a, 'b, 'c) abcTree * ('a, 'b, 'c) abcTree
            | bBranch of 'b * ('b, 'c) bcTree * ('b, 'c) bcTree
    | cBranch of 'c * 'c cTree * 'c cTree
;

我说得对吗？

另外，叶子的要求是什么意思？那个说叶子没有值(value)的人？

Answer 1

First, I am not sure how to define binary trees to have more than 1 type in them.

datatype ('a, 'b) twotypetree = ...

And also how I can define a tree to have these requirements.

定义twotypetree成为 abranch其中包含 'a值和两个('a, 'b) twotypetree s 或包含 'b tree 的 bbranch .

自 'b tree不能包含任何 'a s，a bnode不能有任何包含 'a 的子节点s，所以满足要求。