スポンサーサイト

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

F#入門基本編落穂拾い その22 (ツリー構造(2) Rose Tree)

さて前回は二分木を次の定義方法で定義して処理してきました。
 
type BTree<'a> =
    |Empty
    |Node of ('a * BTree<'a> * BTree<'a>)
 
今回は2本以上の枝分かれも処理できる定義方法を紹介します。
 
    9
   /
  4-8
 /
3-6
 \
  7-5
 
このような、枝分かれの本数が決まっていないツリー構造をバラの木(rose tree)といいます。
 
定義としては、今回は次のようなものを採用します。
 
type RTree<'a> =
    |Empty
    |Node of ('a * (RTree<'a> list))
 
その上で上のツリーは
 
    9-E
   /
  4-8-E
 /
3-6-E
 \
  7-5-E
  
として扱うことにします。
それでは、上のツリーをデータ化していきます。
 
9-E
 
> let t1 = Node(9,[Empty]);;
val t1 : RTree<int> = Node (9, [Empty])
 
    9-E
   /
  4-8-E
 
> let t2 = Node(4,[t1;Node(8,[Empty])]);;
val t2 : RTree<int> = Node (4, [Node (9, [Empty]); Node (8, [Empty])])
 
    9-E
   /
  4-8-E
 /
3-6-E
 \
  7-5-E
  
> let t = Node(3,[t2;Node(6,[Empty]);Node(7,[Node(5,[Empty])])]);;
 
val t : RTree<int> =
  Node
    (3,
     [Node (4, [Node (9, [Empty]); Node (8, [Empty])]); Node (6, [Empty]);
      Node (7, [Node (5, [Empty])])])
      
さて、この形のツリーに対して、まずはすべての要素を表示する関数を定義してみます。
 
> let rec dispNode rtree =
    match rtree with
    |Empty
        -> ()
    |Node(v,lst)
        ->printfn "%d" v   //値を表示
          List.iter (fun r -> dispNode r) lst //リストの全てのツリーに対して再帰的に適用
 ;;
 
val dispNode : RTree<int> -> unit
 
(実行例)
> dispNode t;;
3
4
9
8
6
7
5
val it : unit = ()
 
次にNodeの値全てを加えて返す関数を定義してみます。
 
> let rec sumUpNodeValue rtree =
    match rtree with
    |Empty
        -> 0
    |Node(v,lst)
        ->v + List.fold (fun sum r -> sum + sumUpNodeValue r) 0 lst;;
 
val sumUpNodeValue : RTree<int> -> int
 
(実行例)
> sumUpNodeValue t;;
val it : int = 42
 
(問題)ツリー内のすべての整数をリストにして返す関数toListを定義してください。(リストにする順番は何でもかまいません。)
 
(解答例1)
> let rec toList rtree =
    match rtree with
    |Empty
        -> []
    |Node(v,lst)
        ->v :: List.fold (fun accLst r -> accLst @ (toList r)) [] lst;;
 
val toList : RTree<'a> -> 'a list
 
(実行例)
> toList t;;
val it : int list = [3; 4; 9; 8; 6; 7; 5]
 
(解答例2)
> let toList rtree =
    let rec sub rt res =
        match rt with
        |Empty
            -> res //結果リストをそのまま返す
        |Node(v,lst)
              //結果リストをリスト内のbtreeで育てて、最後にvを加えて返す  
            ->v :: List.fold (fun acc rt -> sub rt acc ) res lst
    sub rtree [];;
 
val toList : RTree<'a> -> 'a list
 
(実行例)
> toList t;;
val it : int list = [3; 7; 5; 6; 4; 8; 9]
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

T GYOUTEN

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

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

この人とブロともになる

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