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

发布于 2024-10-08 16:44:48 字数 1475 浏览 5 评论 0原文

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

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

任何内部顶点（不是叶子）都必须是以下类型'a 或 'b 和叶子没有价值。

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

'a->'a->'a-'b（合法）
'a->'b->'b（合法）
'a->'a->'a（合法）
'b->'b->'b（合法）
'a->'b->'a（非法）

而且我还需要定义另一棵树，它与上面描述的树类似，但现在我有了还有 '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
;

我对吗？

另外，叶子的要求意味着什么？那个说叶子没有价值的人？

原文

Well, I am asked to do the next thing:

To define a binary tree which can contain 2 different types: ('a,'b) abtree and these are the requirements:

Any inner vertex (not a leaf) must be of the type 'a or 'b and the leafs have no value.

For every path in the tree all 'a values must appear before the 'b value: examples of paths:

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

and also I need to define another tree which is like the one described above but now I have got also 'c and in the second requirement it says that for every path I 'a values appear before the 'b values and all the 'b values appear before the 'c values.

First, I am not sure how to define binary trees to have more than 1 type in them.
I mean the simplest binary tree is:

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

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

Any help will be appreciated.

Thanks.

OK, thanks a lot. So you mean something like that:

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
;

and that's what I did for the case it's a 3 type tree as I mentioned above:

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
;

Am I right?

Also, what does the requirement of leafs means? The one that says that the leafs should have no value?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

十年九夏 2024-10-15 16:44:48

首先，我不确定如何定义二叉树以使其具有超过 1 种类型。

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

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

将 twotypetree 定义为包含 'a 值和两个 ('a, 'b) Twotypetreeabranch code>s 或包含 'b 树 的 bbranch。

由于 'b 树 不能包含任何 'a，因此 bnode 不能有任何包含 ' 的子节点as，所以满足要求。

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.

Define a twotypetree to be either an abranch which contains an 'a value and two ('a, 'b) twotypetrees or a bbranch which contains a 'b tree.

Since a 'b tree can't contain any 'as, a bnode can't have any child nodes which contain 'as, so the requirement is met.

回复收藏 0 原文

~没有更多了~