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 回答