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 も取得しており、2 番目の要件では、すべてのパスについて I 'a 値が 'b 値の前に表示され、すべての 'b 値'c 値の前に表示されます。

まず、二分木を定義して複数の型を持つようにする方法がわかりません。つまり、最も単純な二分木は次のとおりです。

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

まず、二分木を定義して複数の型を持つようにする方法がわかりません。

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

また、これらの要件を満たすようにツリーを定義する方法についても説明します。

a を、値と 2 つのを含む anまたは a を含む bbranch のtwotypetreeいずれかに定義します。abranch'a('a, 'b) twotypetree'b tree

aはs を'b tree含むことができないため、 aは s を含む子ノードを持つことができないため、要件が満たされます。'abnode'a

于 2010-12-21T20:53:07.833 に答える