好吧,我被要求做接下来的事情:
要定义一个可以包含 2 种不同类型的二叉树: ('a,'b) abtree,这些是要求:
- 任何内部顶点(不是叶子)必须是 'a 或 'b 类型,并且叶子没有值。
对于树中的每条路径,所有 '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
;
我对吗?
另外,叶子的要求是什么意思?那个说叶子应该没有价值的东西?