ツリー構造 (多分木 : N 分木) の実装では、ツリー構造を実現する構造体とツリー全体を再帰的に操作する手法について触れました。

今回はツリー構造を「幅優先で走査する」方法について考えます。

おさらい

前回に実装したコードは以下のような形になっています。

#include <stdio.h>

typedef struct node
{
  const char* name;
  int depth;
  struct node* child;
  struct node* next;
} node_t;

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;
  }
}

void display(node_t* node)
{
  int i;
  for (i=0;i<node->depth;i++)
  {
    printf(" ");
  }
  printf("- %s\n",node->name);
}

void show_tree_dfs(node_t* node)
{
  if (node == NULL) return;
  display(node);
  show_tree_dfs(node->child);
  show_tree_dfs(node->next);
}

int main()
{
  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);
  node_t n11,n12;
  append("n1-1",&n1,&n11);
  append("n2-2",&n1,&n12);
  node_t n21,n22;
  append("n2-1",&n2,&n21);
  append("n2-2",&n2,&n22);
  node_t n31;
  append("n3-1",&n3,&n31);
  node_t n111,n221;
  append("n1-1-1",&n11,&n111);
  append("n2-2-1",&n22,&n221);
  // display tree
  printf("show tree depth first\n");
  show_tree_dfs(&root);
  return 0;
}

main 関数や include 文もいれているので、コンパイルして動作させることができます。

main 関数では、以下のツリー構造を作成して、show_tree_dfs 関数を呼び出して、再帰的にツリー構成を表示しています。

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

幅優先の走査

さて、前回失敗した「幅優先」の走査を考えてみます。

幅優先の走査では、ルートノードから「深さ」が同じノードを全て走査してから、次の深さのノードに移っていきます。

上述したサンプルのツリー構成は

- 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)

ルートノード root を見た後は、n1 → n2 → n3 と走査しますが、そのときに、n1 の子ノード・n2 の子ノード・n3 の子ノードを記録しておき、同じ深さのノードがなくなった後で、記録しておいた子ノードを走査するようにすれば、うまくいきそうです。

子ノードの記録はキュー (待ち行列) で実装できるでしょう。ここではアルゴリズムだけを考えるので、キューのメモリ割当とか実装は気にしないようにします。

ただ、動作しないと意味はないので、待ち行列の行数を固定値にして、キューがあふれる場合はプログラムを終了するようにしちゃいます。

#define STACK_NUM 100
void show_tree_bfs(node_t* node)
{
  if (node == NULL) return;
  node_t* queue[STACK_NUM]; // *1
  int num = 0;
  queue[ num++ ] = node; // *2
  while ( 1 )
  {
    node_t* buf[STACK_NUM]; // *3
    int buf_num = 0;
    while ( num != 0 ) // *4
    {
      node = queue[ --num ]; // *5
      while (node != NULL) // *6
      {
        display(node); // *7
        if (node->child != NULL) // *8
        {
          buf[ buf_num++ ] = node->child; // *8
          if (buf_num >= STACK_NUM) exit(0); // *9
        }
        node = node->next; // *10
      }
    }
    if ( buf_num == 0 ) break; // *11
    while ( buf_num != 0 ) // *12
    {
      queue[ num++ ] = buf[ --buf_num ]; // *12
      if (num >= STACK_NUM) exit(0);
    }
  }
}

node_t* queue[STACK_NUM];

ノードを格納するキュー (作業ノード群) を宣言します。動作としては、キューになっていますが、実装自体はスタックになっています。

queue[ num++ ] = node;

まずキューに最初のノードを格納します。ルートノードが渡されたら、ルートノードがキューに格納されます。num++ となっているのに注意。num++ と ++num は意味が異なります。前者はまず num という値を渡してから +1 され、後者はまず num の値を +1 してから値を渡します。

node_t* buf[STACK_NUM];

ループの中で、見つけた子ノードを一時的に格納するスタック (バッファ) を宣言します。

while ( num != 0 )

num はキューに格納されたノードの数です。これが 0 であれば、格納されたキューの中身を全て走査したことになります。

node = queue[ --num ];

キューの最初に格納された値を取り出しています。この行だけ見ると、後から格納された値を取り出しているようですが、動作としては最初に見つけた子ノードから取り出されます。

while (node != NULL)

キューから取り出したノードを起点として、隣ノードがなくなるまで走査します。

display(node);

ノードの表示処理はここで行ないます。

if (node->child != NULL) buf[ buf_num++ ] = node->child;

対象ノードに子ノードが存在する場合、子ノードをバッファに格納しておきます。幅優先で走査を行なうため、バッファに一時的に保管しておきます。(深さ優先の場合と異なり) この時には子ノードの走査は行ないません。

if (buf_num >= STACK_NUM) exit(0);

buf_num はバッファに格納されたノードを数を示しています。これが STACK_NUM を超えると、正しく動作しないので、プログラムを終了しています。exit 関数をコールしているので stdlib.h をインクルードする必要があります。

node = node->next;

隣ノードに移ります。こうして同じ「深さ」のノードを辿って走査します。

if ( buf_num == 0 ) break;

buf_num が 0 の場合は、それ以上の「深さ」のノードが存在しないということですから、ループを抜けて処理を終了します。

while ( buf_num != 0 ) { queue[ num++ ] = buf[ --buf_num ]; }

buf_num が 0 でない場合、バッファに一時的に格納しておいた子ノード群をキュー (作業ノード群) にコピーします。

キューとスタック

キューとスタックは似ていますが、動作がやや異なります。

キューは待ち行列とも言われていて、最初に入ったものから先に抜けていきます (First in, First out)。一方、スタックは最後に積み上げたものから先に出て行きます (Last in, First out)。

前述の例だと

queue[ num++ ] = node;

で、行列 queue の末尾に要素を追加しています。追加した要素を使うときは

node = queue[ --num ];

のようにしているので、末尾の要素から取り出しています。

最初に見つけた子ノードから順番の処理をしていきたいので、単純にこの手法を使うと、順番が逆になってしまいます。

しかしながら、ここでの実装では、ふたつのスタックを利用することにより、キューのように動作するようになっています。