2007年09月04日

掲示板のツリー表示と再帰プログラミング

関東大会での発表の直前、相方より、「掲示板の生データからツリー表示を作れないか」との相談を受けました。

「ちょっとムリ」とその場は断りました。大会発表までには自分の能力では余りに時間が足りないと思ったからです。

発表も終わり少し余裕が出てきたので、取り組んでみました。ツリー構造には再帰プログラミングだなぁということはうっすらと考えていたのですが、これがなかなか難しいものでした。


まずその構造を見てみましょう。ものすごく単純に言います。
xoopsBluesBB というモジュールのデータはデータベーステーブル一つだけで掲示板データを管理しています。これを取り出すとフィールドに「res_id」と「hig_id」というものが目に付きます。どうもこれが発言のidとそれにぶら下がる発言の関係を示しているようです。

このようになっています。

あるクラス、ある班でしりとりをしているところです。「発言をした順番(res_id)」で並んでいます。

res_id  hig_id  message
0  0  スターフルーツ
1  1  月
2  1  ツリー★
3  2  木
4  3  りんご
5  5  ごま
6  4  救急車
7  6  マルクス
8  8  スーパースター
9  8  すいか
10  10  家政婦は見た
11  7  しゃ乱Q
12  9  たけし
13  12  きゅーちゃん
14  11  たぬきは見た
15  13  宿題
17  11  田んぼがかれた

元発言とぶら下がる発言の関係はこうです。

hig_id は元になる発言の res_id + 1 になっている。

たったこれだけのルールです。ちなみに大元の発言は res_id、hig_id ともに 0,0 になっています。データは res_id、hig_id 順にソートされているものとします。

さて、実際にやってみるとこうなりました。

1.最初の行は確定。
2.2番目の行も確定。
3.3番目の行以降では前の確定している行の res_id + 1 となる hig_id を持つ行を探す。
4.見つかったらその行を確定行(最初は2行目)の下まで持ち上げて、その行を確定(以後確定行が何行目かをグローバルとして記憶)。3を再帰的に呼び出す。
5.見つからなかったらこんどは同じ hig_id を持つ発言を探し同列で枝分かれしているものを探す。
6.同列が見つかったら更に下に進むため再帰的に3を呼び出す。
7.同列が見つからなかったらその枝は終わりなので戻って次の行に進む

分かりにくいかも知れませんが、「3を呼び出す」の部分はfor 〜 Next のような繰り返しではなく、再帰的に自分自身を呼び出しています。つまりレスが続く限り自分を呼び出すことでツリーが伸びていくことになります。また一段もどるごとに階層を上がることになりますから、前の状態の続きになります。つまり一つ戻った発言と並列の発言の処理になります。

と書きましたが、これがまたややこしくて苦労しました。

中身は省略しますが、Excel VBA でやりました。Ruby などのオブジェクト指向のスクリプトプログラミング言語の方が適しているかも知れません。

結果はこのようになります。

res_id  hig_id  message
0  0  スターフルーツ
1  1  月
3  2  木
6  4  救急車
11  7  しゃ乱Q
13  12  きゅーちゃん
2  1  ツリー★
4  3  りんご
5  5  ごま
7  6  マルクス
8  8  スーパースター
12  9  たけし
15  13  宿題
9  8  すいか
10  10  家政婦は見た
14  11  たぬきは見た
17  11  田んぼがかれた

お分かりでしょうか。基本的に前の発言の res_id + 1 が hig_id となっているように並び、末端までいくと途中の枝が分岐している様子が読み取れますでしょうか。

これを階層が下りる度にスペースを一つ、発言前に「┗」を表示すると次のようになります。

○スターフルーツ
 ┗月
  ┗木
   ┗救急車
    ┗しゃ乱Q
     ┗きゅーちゃん
 ┗ツリー★
  ┗りんご
   ┗ごま
    ┗マルクス
     ┗スーパースター
      ┗たけし
       ┗宿題
     ┗すいか
      ┗家政婦は見た
       ┗たぬきは見た
       ┗田んぼがかれた

これでツリー表示(らしきもの)ができました。


以下のページが参考になるかと思います。

第7回 “再帰”でプログラミングの楽しさを実感する(IT Pro)
再帰的アルゴリズム(新潟大学個人ページ?「Tiny Basic for Windows」の一コーナーみたいです)

以前の記事で、フォルダの階層構造を再帰的に辿っていくプログラムの話がありました。こちらです。
posted by n_shimizu at 18:30 | TrackBack(0) | VBA
この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/5320264
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック