4

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

要定义一个可以包含 2 种不同类型的二叉树： ('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
;

我对吗？

另外，叶子的要求是什么意思？那个说叶子应该没有价值的东西？

4

1 回答 1

3

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

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

还有我如何定义一棵树来满足这些要求。

将 a 定义为twotypetree包含abranch一个'a值和两个('a, 'b) twotypetrees 的 an 或包含 a 的 bbranch 'b tree。

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

于 2010-12-21T20:53:07.833 回答