7.1 datatype文によるデータ型の定義

問 7.1

pre-order表現に使用する区切り文字を固定すると，任意の2分木は，唯一のpre-order表現を持つことを示せ． (ヒント：以下の2つの性質を示せばよい．（1）任意の2分木はpre-order表現を持つ．（2）2分木 $T$ と $T^{\prime}$ が同一のpre-order表現をもてば， $T=T^{\prime}$ である． )

解答例２分木の構造に関する帰納法でしめす。

1.

木がEmptyの時。空文字列が唯一のpre-order表現である。
2.

木がNode(a, $T$ , $T^{\prime}$ )の時。帰納法の仮定より、 $T$ および $T^{\prime}$ はそれぞれ唯一のpre-order表現 $P,P^{\prime}$ をもつ。与えられた木はpre-order表現 $a(P)(P^{\prime})$ を持つ。 $P,P^{\prime}$ が唯一の表現であるから、この表現も唯一である。

問 7.2

searchLP および searchRP を書き，decompose，さらに fromPreOrder を完成させ，テストを行え．

解答例 searchLP および searchRPの例を以下にしめす。

   fun searchLP s p =
       if substring(s,p,1) = "(" then p
       else searchLP s (p+1)

   fun searchRP s p n =
       case substring(s,p,1) of
           "(" => searchRP s (p+1) (n+1)
          | ")" => if n=0 then p else searchRP s (p+1) (n - 1)
          | _ => searchRP s (p+1) n

問 7.3

2分木の文字列表現には，上記のpre-order表現以外に，以下の2つの表現がある．

•

post-order表現．
2分木を（1）左部分木，（2）右部分木，（3）ルートの順にたどって得られる文字列に対応する表現．たとえば，図 tree.pdf に示した木は (()()b)((()()d)()c)a と表される．
•

in-order表現．
2分木を（1）左部分木，（2）ルート，（3）右部分木の順にたどって得られる文字列に対応する表現．たとえば図 tree.pdf に示した木は (()b())a((()d())c()) と表される．

区切り文字を固定するならば，2分木は，唯一のpost-order表現および in-order表現を持つことを示せ．

これら2つの表現から string tree 型データを生成する関数， fromPostOrder および fromInOrder を定義せよ．

解答例唯一のpost-order表現およびin-order表現を持つことの証明は、問 7.1におけるpre-order表現の場合と同様である。

fromPostOrder および fromInOrderを書くためには、対応する decomposeを書く必要がある。それらの定義例を以下に示す。

   fun decomposeIn s =
      let val lp1 = searchLP s 0
          val rp1 = searchRP s (lp1+1) 0
          val lp2 = searchLP s  rp1
          val rp2 = searchRP s (lp2+1) 0
      in {root=substring (s,rp1+1,lp2 - rp1 - 1),
          left=substring (s,lp1+1,rp1-lp1 -1),
          right=substring (s,lp2+1,rp2 - lp2-1)}
      end

   fun fromInOrder s =
       if s = "" then Empty
       else let val {root,left,right} = decomposeIn s
            in Node(root,fromInOrder left,fromInOrder right)
            end

   fun decomposePost s =
      let val lp1 = searchLP s 0
          val rp1 = searchRP s (lp1+1) 0
          val lp2 = searchLP s  rp1
          val rp2 = searchRP s (lp2+1) 0
      in {root=substring (s,rp2+1,size s - rp2 - 1),
          left=substring (s,lp1+1,rp1-lp1 -1),
          right=substring (s,lp2+1,rp2 - lp2-1)}
      end

   fun fromPostOrder s =
       if s = "" then Empty
       else let val {root,left,right} = decomposePost s
            in Node(root,fromPostOrder left,fromPostOrder right)
            end

問 7.4

上の例では，「空の木」を使って2分木を定義したが，「子を持たない木」を使った以下のような定義も可能である．

1.

データ $v$ のみからなるノード ${\it Leaf}(v)$ は2分木である．
2.

$v$ がデータ， $T_{1},T_{2}$ が2分木なら， ${\it Node}(v,T_{1},T_{2})$ は， $v$ をノードのデータ， $T_{1},T_{2}$ を左右の部分木とする2分木である．
3.

$v$ がデータ， $T$ が2分木なら， ${\it NodeL}(v,T)$ は， $v$ をノードのデータ， $T$ を左の部分木とする2分木である．
4.

$v$ がデータ， $T$ が2分木なら， ${\it NodeR}(v,T)$ は， $v$ をノードのデータ， $T$ を右の部分木とする2分木である．

この定義に対応するデータ型’a newTreeを定義せよ．

解答例問題の定義をそのままコードすると、以下の型定義を得る。

   datatype ’a newTree
     = Leaf of ’a
     | Node of ’a * ’a newTree * ’a newTree
     | NodeL of ’a * ’a newTree
     | NodeR of ’a * ’a newTree