making-tree

たまに、プログラミングをする際に、

木構造をもったデータを作成する必要に迫られます。

手作業で作成するか？

...そんなの辛過ぎます。気が狂いそうです。

ミスを埋め込み、後に、データが正しくないがゆえの、

不毛なデバッグ作業が発生しそうです。

だったら、そこは木構造を持つデータ作成するプログラムを作成し、楽をしちゃいましょう。

データの構造

親nodeが子nodeを複数持つ下の形式で表現します。

nodeに続く最初の数字が、木の深さ、続く数字で同じ深さにいる兄弟ノードを識別します。

木の形式

node.木の深さを表す数字(0より始まる).兄弟番号(0より始まる)

{

hogehoge(<-nodeのメンバ)

node.木の深さを表す数字+1.兄弟番号(0より始まる)

{

hogehoge

}

node.木の深さを表す数字+1.兄弟番号+1

{

hogehoge

node.木の深さを表す数字+2.兄弟番号(0より始まる)

{

hogehoge

}

}

}

ex. 深さ２の木、各ノードには、二つの子ノードがいる。

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を作成する関数”の定義

木の深さと、木の寿命、兄弟番号を引数で取得

木の寿命が０のとき、この関数を終了

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に、木構造を持ったデータが生成されます。