たまに、プログラミングをする際に、
木構造をもったデータを作成する必要に迫られます。
手作業で作成するか?
...そんなの辛過ぎます。気が狂いそうです。
ミスを埋め込み、後に、データが正しくないがゆえの、
不毛なデバッグ作業が発生しそうです。
だったら、そこは木構造を持つデータ作成するプログラムを作成し、楽をしちゃいましょう。
データの構造
親nodeが子nodeを複数持つ下の形式で表現します。
nodeに続く最初の数字が、木の深さ、続く数字で同じ深さにいる兄弟ノードを識別します。
木の形式
node.木の深さを表す数字(0より始まる).兄弟番号(0より始まる)
{
hogehoge(<-nodeのメンバ)
node.木の深さを表す数字+1.兄弟番号(0より始まる)
{
hogehoge
}
node.木の深さを表す数字+1.兄弟番号+1
{
hogehoge
node.木の深さを表す数字+2.兄弟番号(0より始まる)
{
hogehoge
}
}
}
ex. 深さ2の木、各ノードには、二つの子ノードがいる。
node.0.0
{
hogehoge
node.1.0
{
hogehoge
node.2.0
{
hogehoge
}
node.2.1
{
hogehoge
}
}
node.1.1
{
hogehoge
node.2.0
{
hogehoge
}
node.2.1
{
hogehoge
}
}
}
作成するプログラムのアウトライン
明らかに再帰構造を持っているので、nodeを作成する関数で、再帰を使います。
再帰の終了条件は、予め定めた木の寿命に到達すること。
アウトラインは、こんな感じでしょうか。
”nodeを作成する関数”の定義
木の深さと、木の寿命、兄弟番号を引数で取得
木の寿命が0のとき、この関数を終了
node自身を作成⬇
node.木の深さを表す数字.兄弟番号
{
hogehoge
<-閉括弧は、ここではまだ閉じないよ。
子nodeの作成
作成したい子node数分、"nodeを作成する関数"をコール
その際に、与える引数は、
木の深さ+1, 木の寿命-1,子nodeの番号
}
以上、、、って感じです。
プログラム
木の寿命10、子ノード数2(ノード当たり)の木を生成するperlスクリプトを
下に貼付けておきます。
下記の環境で動作してます。
Mac OS X 10.9
perl --version
This is perl 5, version 12, subversion 4 (v5.12.4) built for darwin-thread-multi-2level
$perl make_tree.pl > tree
で、ファイルtreeに、木構造を持ったデータが生成されます。