多分木と呼ばれるツリー構造は、親となるノードに、複数の子ノードがぶら下がるような形になっています。

この時、ひとつのノードに下に最大 2 つの子ノードしか存在できないようなツリー構造を「二分木」と言います。

Windows や Mac OS X で利用できるディレクトリ構造もツリーで表現できますし、JavaScript などで利用する DOM もツリー構造になっています。

• root
  • n1
    • n1-1
      • n1-1-1
    • n1-2
  • n2
    • n2-1
    • n2-2
      • n2-2-1
  • n3
    • n3-1

ツリー構造を表現する構造体

ここでは、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

のように表示する方法です。

最初のツリー表記に表示順番をつけると、次のようになります。

• root (1)
  • n1 (2)
    • n1-1 (5)
      • n1-1-1 (10)
    • n1-2 (6)
  • n2 (3)
    • n2-1 (7)
    • n2-2 (8)
      • n2-2-1 (11)
  • n3 (4)
    • n3-1 (9)

子ノードよりも隣ノードを優先すれば良いわけですから、

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

最初の子ノードのみが子ノードを持つ場合だけ、期待した動作になります。ルートノードはひとつだけなので、最初の階層だけはうまく動作するという訳です。

予定よりも大幅に長くなってしまったので、続きは次回。