多分木と呼ばれるツリー構造は、親となるノードに、複数の子ノードがぶら下がるような形になっています。
この時、ひとつのノードに下に最大 2 つの子ノードしか存在できないようなツリー構造を「二分木」と言います。
Windows や Mac OS X で利用できるディレクトリ構造もツリーで表現できますし、JavaScript などで利用する DOM もツリー構造になっています。
ツリー構造を表現する構造体
ここでは、C 言語で実装してみます。
perl, javascript や php などのスクリプト言語への変換はそれほど難しくないでしょう。
ノードの構造は、以下のように記述できます。
typedef struct node {
struct node* child;
struct node* next;
} node_t;
child は、ノードの下にある一番最初の子ノードです。
next は、ノードの隣にあるノードを示します。ノードの深さは変わりません。
最初に挙げた例の場合、ルートノード (root) とその子ノード (n1, n2, n3) は、以下のようになります。
// root node
root.child = &n1;
root.next = NULL;
// the 1st child of root
n1.child = &n1_1;
n1.next = &n2;
// the 2nd child of root
n2.child = &n2_1;
n2.next = &n3;
// the 3rd child of root
n3.child = &n3_1;
n3.next = NULL;
[2008.05.19 追記] 上記コードの間違いを訂正。
next だけを見ると、リンクリストのような構造になっています。
親のノードが子ノードの配列を所持するという方法もできますが、この実装の方が使用メモリを押さえることができるかと思います。
構造としては、二分木と同じです。多分木を二分木で表現していることになります。
これだけだとつまらないので、ノードの内容を少し拡張して実装します。
typedef struct node {
const char* name;
int depth;
struct node* child;
struct node* next;
} node_t;
ノード名称 name とルートノードからの深さを示す depth というパラメータを追加しました。
ノードジェネレータ
ノードを作成する関数を作成してみます。
最低限、新規に作成するノードとその親になるノードのポインタ (ノードオブジェクトを示す ID 番号のようなもの) を渡す必要がありそうです。ノード名称を定義したので、設定する名称も渡すようにします。
void append(const char* name, node_t* parent, node_t* node)
{
node->name = name;
node->depth = 0;
node->child = NULL;
node->next = NULL;
if (parent == NULL) return;
node->depth = parent->depth + 1;
if (parent->child == NULL)
{
parent->child = node;
}
else
{
node_t* last = parent->child;
while (last->next != NULL)
{
last = last->next;
}
last->next = node;
}
}
関数 append は、指定した親ノードに新しく子ノードを追加する関数になっています。
親ノードを NULL (無指定) にすると、親ノードがないということになるので、そのノードはルートノードとして扱います。
関数 append 内の最初の 4 行で新しく作成するノードの初期化を行なっています。
node->name = name;
node->depth = 0;
node->child = NULL;
node->next = NULL;
親ノードが無指定だと、それ以上の操作は必要ないので、そのまま抜けます。
親ノードが指定されている場合、その親ノードの新しい子ノードとして登録する必要があります。
まだ、親ノードにひとつも子ノードが存在していない場合、
if (parent->child == NULL)
{
parent->child = node;
}
すでに子ノードが存在している場合は、全ての子ノードをチェックして、子ノードの末尾に追加します。
else
{
node_t* last = parent->child;
while (last->next != NULL)
{
last = last->next;
}
last->next = node;
}
ここで last は、対象の親ノードに対して、末尾の子ノードです。while ループで next が NULL になる子ノードを探します。
node_t root;
append("root",NULL,&root); // create root
node_t n1,n2,n3;
append("n1",&root,&n1);
append("n2",&root,&n2);
append("n3",&root,&n3);
のようにして利用します。
深さ優先の走査
ツリーの内容を表示する関数を考えてみます。例えば、上述したツリー構造を
- root
- n1
- n1-1
- n1-1-1
- n1-2
- n2
- n2-1
- n2-2
- n2-2-1
- n3
- n3-1
のように表示する関数です。
まず、ノードを表示する関数をとりあえず見繕います。
void display(node_t* node)
{
int i;
for (i=0;i<node->depth;i++)
{
printf(" ");
}
printf("- %s\n",node->name);
}
printf を使っているので、stdio.h のインクルードが必要です。
ツリー表示には、再帰を使うと非常に楽に実装できます。ノードは、自身の子ノード、あるいは、隣ノードを知っているので、それを再帰的に渡せばいいだけです。
void show_tree_dfs(node_t* node)
{
if (node == NULL) return;
display(node);
show_tree_dfs(node->child);
show_tree_dfs(node->next);
}
show_tree_dfs の最初の行では、渡されたノードのポインタが NULL かどうかをチェックしています。NULL であれば、実体のないノードなので、何もしないで関数を抜けます。
次に自身の情報を表示しています。
続いて、子ノードと隣ノードを再帰的に渡します。ここは
void show_tree_dfs(node_t* node)
{
if (node == NULL) return;
display(node);
if (node->child) show_tree_dfs(node->child);
if (node->next) show_tree_dfs(node->next);
}
のように NULL でない場合のみ、渡すようにした方がいいかもしれません。
ただ、今回は関数の最初の行でチェックしているので、あえて簡潔にすませるようにしました。
この例では、ノードに子供があった場合に、子ノードの内容を表示してから隣ノードを表示しています。ルートからの「深さ」が深い方を優先的に走査するので、「深さ優先の走査」と言えます。
幅優先の走査 (失敗例)
一方で、ルートノードからの「深さ」が同じノードを全て列挙してから、次の深さのノードを表示するという実装も考えられます。
- root
- n1
- n2
- n3
- n1-1
- n1-2
- n2-1
- n2-2
- n3-1
- n1-1-1
- n2-2-1
のように表示する方法です。
最初のツリー表記に表示順番をつけると、次のようになります。
子ノードよりも隣ノードを優先すれば良いわけですから、
void show_tree_not_bfs(node_t* node)
{
if (node == NULL) return;
display(node);
show_tree_not_bfs(node->next);
show_tree_not_bfs(node->child);
}
のような関数になるでしょうか。
これを実行してみると、ルートノードとその子ノード (深さ 1 のノード) に対しては期待通りに動作します。しかし、その後がうまくいきません。
- root
- n1
- n2
- n3
- n3-1
- n2-1
- n2-2
- n2-2-1
- n1-1
- n1-2
- n1-1-1
最初の子ノードのみが子ノードを持つ場合だけ、期待した動作になります。ルートノードはひとつだけなので、最初の階層だけはうまく動作するという訳です。
予定よりも大幅に長くなってしまったので、続きは次回。
![[図] CGI スクリプトの基本フロー](http://serennz.sakura.ne.jp/sb/img/img253_cgi_script_flow.png)
![[図] Serene Bach 3 エラー画面](http://serennz.sakura.ne.jp/sb/img/img252_sb3_new_error.png)
solipo ver 0.07 を公開しています。→ [
![[画像]solipo 設定ダイアログ](http://serennz.sakura.ne.jp/toybox/solipo/solipo_settings.png "solipo 設定ダイアログ")