スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

F#入門基本編落穂拾い その21 (ツリー構造(1) Binary Tree)

リスト構造に引き続き今回はツリー構造を紹介していきたいと思います。
ツリーとしうのは、ファイルのディレクトリ構造のように、一つの根っこから、何本かづつ枝分かれしていくデータ構造です。
例(適当に枝分かれしたツリー) 
 
    9
   /
  5-8
 /
3-6
 \
  7-5
 
まずは、上の例よりもっと単純な形の、枝分かれしないか、するとしたら2本以下であるツリーを扱います。
 

    9
   /
  4
 / \
3   5
 \
  7
   \
    2
これを更に
 
      E
     /
    9
   / \
  4   E 
 / \ 
3   5-E
 \   \
  7-E E
   \
    2-E
     \
      E
      
という枝分かれは0か2本という形として扱うことにします。(EはEmptyの頭文字)
一般に必ず0か2本の枝分かれをしているツリーを二分木(Binary Tree)といいます。
 
さて、これをどのような型として定義すればよいのでしょうか。
ここでリスト構造の定義を思い出してください。実はリスト構造というのは一本の枝分かれしかしないツリー構造としても、考えることができて、
5-2-1-E
に対して
type myList<'a> =
    |Empty
    |Ele of ('a * myList<'a>) 
と定義して
Ele (5, Ele (2, Ele (1, Empty)))のように値を定義して利用できるのでした。
同様に考えるとBinary Treeは例えば次のように定義できます。
 
type BTree<'a> =
    |Empty
    |Node of ('a * BTree<'a> * BTree<'a>)
    
(Nodeは通常「節」という日本語に訳されます。)
Nodeは保持する値と、それにつながる2本の「子供二分木」のタプルとして表現されています。
 
それでは、Nodeをデータとして表現してみます。
 
   E
  /
 9
  \
   E     
 
> let t1 = Node (9,Empty,Empty);;
val t1 : BTree<int> = Node (9, Empty, Empty)
 
 5-E
  \
   E
 
> let t2 = Node (5,Empty,Empty);;
val t2 : BTree<int> = Node (5, Empty, Empty)
 
    E
   /
  9
 / \
4   E 
 \ 
  5-E
   \
    E
   
> let t3 = Node (4,t1,t2);;
val t3 : BTree<int> = Node (4, Node (9, Empty, Empty), Node (5, Empty, Empty))
 
  7-E 
   \
    2-E
     \
      E
 
> let t4 = Node(7,Empty,Node(2,Empty,Empty));;
val t4 : BTree<int> = Node (7, Empty, Node (2, Empty, Empty))
 
      E
     /
    9
   / \
  4   E 
 / \ 
3   5-E
 \   \
  7-E E
   \
    2-E
     \
      E
      
    
> let t = Node(3,t3,t4);;
val t : BTree<int> =
  Node
    (3, Node (4, Node (9, Empty, Empty), Node (5, Empty, Empty)),
     Node (7, Empty, Node (2, Empty, Empty)))
 
さて、この形のツリーに対して、まずはすべての要素を表示する関数を定義してみます。
 
> let rec dispNode btree =
    match btree with
    |Empty
        -> ()
    |Node(v,rightBT,leftBT)
        ->printfn "%d" v   //値を表示
          dispNode rightBT //右(図では上)の二分木に対してこの関数を適用
          dispNode leftBT  //左(図では下)の二分木に対してこの関数を適用
;;
val dispNode : BTree<int> -> unit
 
(実行例)
> dispNode t;;
3
4
9
5
7
2
val it : unit = ()

すこし分かりにくいかもしれませんのでコメントを入れてみます。
 
let rec dispNode btree =
    match btree with
    |Empty
        -> ()
    |Node(v,rightBT,leftBT)
        ->printfn "%d" v   //値を表示
          printfn "今ノードの値は%dです。" v
          printfn "今から右(上)側のbtreeに対して関数を適用します。"
          dispNode rightBT //右(図では上)の二分木に対してこの関数を適用
          printfn "今ノードの値は%dです。" v
          printfn "右(上)側のbtreeに対しては適用が終わったので、左(下)側に対して適用します。"
          dispNode leftBT  //左(図では下)の二分木に対してこの関数を適用
          printfn "今ノードの値は%dです。" v
          printfn "関数を抜けます"
 
      E
     /
    9
   / \
  4   E 
 / \ 
3   5-E
 \   \
  7-E E
   \
    2-E
     \
      E
(実行例)
> dispNode t;;
3
今ノードの値は3です。
今から右(上)側のbtreeに対して関数を適用します。
4
今ノードの値は4です。
今から右(上)側のbtreeに対して関数を適用します。
9
今ノードの値は9です。
今から右(上)側のbtreeに対して関数を適用します。
今ノードの値は9です。
右(上)側のbtreeに対しては適用が終わったので、左(下)側に対して適用します。
今ノードの値は9です。
関数を抜けます
今ノードの値は4です。
右(上)側のbtreeに対しては適用が終わったので、左(下)側に対して適用します。
5
今ノードの値は5です。
今から右(上)側のbtreeに対して関数を適用します。
今ノードの値は5です。
右(上)側のbtreeに対しては適用が終わったので、左(下)側に対して適用します。
今ノードの値は5です。
関数を抜けます
今ノードの値は4です。
関数を抜けます
今ノードの値は3です。
右(上)側のbtreeに対しては適用が終わったので、左(下)側に対して適用します。
7
今ノードの値は7です。
今から右(上)側のbtreeに対して関数を適用します。
今ノードの値は7です。
右(上)側のbtreeに対しては適用が終わったので、左(下)側に対して適用します。
2
今ノードの値は2です。
今から右(上)側のbtreeに対して関数を適用します。
今ノードの値は2です。
右(上)側のbtreeに対しては適用が終わったので、左(下)側に対して適用します。
今ノードの値は2です。
関数を抜けます
今ノードの値は7です。
関数を抜けます
今ノードの値は3です。
関数を抜けます
val it : unit = ()
 
 
リストに対する再帰関数では、行って戻ってだけだったのが、二分木に対しては「行って戻って」「行って戻って」という、ことになっています。
 
さて問題です。
 
> let rec dispNode btree =
    match btree with
    |Empty
        -> ()
    |Node(v,rightBT,leftBT)
        ->dispNode rightBT //右(図では上)の二分木に対してこの関数を適用
          printfn "%d" v   //値を表示
          dispNode leftBT  //左(図では下)の二分木に対してこの関数を適用
;;
として dispNode t とするとどう表示されるでしょうか。
      E
     /
    9
   / \
  4   E 
 / \ 
3   5-E
 \   \
  7-E E
   \
    2-E
     \
      E
(答え)
> dispNode t;;
9
4
5
3
7
2
val it : unit = ()
>
 
さて次にNodeの値全てを加えて返す関数を定義してみます。
 
> let rec sumUpNodeValue btree =
    match btree with
    |Empty
        -> 0
    |Node(v,rightBT,leftBT)
        ->(sumUpNodeValue rightBT) + v + (sumUpNodeValue leftBT);;
 
val sumUpNodeValue : BTree<int> -> int
 
> sumUpNodeValue t;;
val it : int = 30
 
ということでしたが、コメントを執拗にいれて実行してみると次のようになります。
 
> let rec sumUpNodeValue btree =
    match btree with
    |Empty
        ->0
    |Node(v,rightBT,leftBT)
        ->printfn "今ノードの値は%dです。" v
          let rSum =  sumUpNodeValue rightBT 
          printfn "今ノードの値は%dですが右(上)側のノードの総計は%dでした"  v rSum
          let lSum =sumUpNodeValue leftBT 
          printfn "今ノードの値は%dですが左(下)側のノードの総計は%dでした"  v lSum
          printfn "よってノードの値%dと右(上)側のノードの総計%dと左(下)側のノードの総計%d" v rSum lSum
          printfn "の和%dを返して関数を抜けます" (v+rSum+lSum)
          v+rSum+lSum;;
 
val sumUpNodeValue : BTree<int> -> int
 
      E
     /
    9
   / \
  4   E 
 / \ 
3   5-E
 \   \
  7-E E
   \
    2-E
     \
      E
    
> sumUpNodeValue t;;
今ノードの値は3です。
今ノードの値は4です。
今ノードの値は9です。
今ノードの値は9ですが右(上)側のノードの総計は0でした
今ノードの値は9ですが左(下)側のノードの総計は0でした
よってノードの値9と右(上)側のノードの総計0と左(下)側のノードの総計0
の和9を返して関数を抜けます
今ノードの値は4ですが右(上)側のノードの総計は9でした
今ノードの値は5です。
今ノードの値は5ですが右(上)側のノードの総計は0でした
今ノードの値は5ですが左(下)側のノードの総計は0でした
よってノードの値5と右(上)側のノードの総計0と左(下)側のノードの総計0
の和5を返して関数を抜けます
今ノードの値は4ですが左(下)側のノードの総計は5でした
よってノードの値4と右(上)側のノードの総計9と左(下)側のノードの総計5
の和18を返して関数を抜けます
今ノードの値は3ですが右(上)側のノードの総計は18でした
今ノードの値は7です。
今ノードの値は7ですが右(上)側のノードの総計は0でした
今ノードの値は2です。
今ノードの値は2ですが右(上)側のノードの総計は0でした
今ノードの値は2ですが左(下)側のノードの総計は0でした
よってノードの値2と右(上)側のノードの総計0と左(下)側のノードの総計0
の和2を返して関数を抜けます
今ノードの値は7ですが左(下)側のノードの総計は2でした
よってノードの値7と右(上)側のノードの総計0と左(下)側のノードの総計2
の和9を返して関数を抜けます
今ノードの値は3ですが左(下)側のノードの総計は9でした
よってノードの値3と右(上)側のノードの総計18と左(下)側のノードの総計9
の和30を返して関数を抜けます
val it : int = 30
 
(問題)ツリー内のすべての整数をリストにして返す関数toListを定義してください。(リストにする順番は何でもかまいません。)
 
(解答例1) 
> let rec toList btree =
    match btree with
    |Empty
        -> []
    |Node(v,rightBT,leftBT)
        ->v :: (toList rightBT) @ (toList leftBT);;
 
val toList : BTree<'a> -> 'a list
 
(実行例)
> toList t;;
val it : int list = [3; 4; 9; 5; 7; 2]
 
リストの連結を使わずに答えの種[]を育てて行くという手法では次のようになります。
 
(解答例2)
let toList btree =
    let rec sub bt res =
        match bt with
        |Empty
            -> res //結果リストをそのまま返す
        |Node(v,rightBT,leftBT)
              //右側で育てた結果リストを左側に渡して育てて、最後にvを加えて返す  
            ->v :: (sub leftBT (sub rightBT res))
    sub btree []
    
(実行例)
> toList t;;
val it : int list = [3; 7; 2; 4; 5; 9]
 
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

Author:T GYOUTEN
F#と英単語とフリーソフトと読書に興味があります。
ホームページでフリーソフトも公開しています。どぞ御贔屓に。

最新記事
最新コメント
最新トラックバック
月別アーカイブ
カテゴリ
フリーエリア
フリーエリア
blogram投票ボタン
検索フォーム
RSSリンクの表示
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。