「ツリー構造 (多分木 : N 分木) の実装」「ツリー構造の幅優先走査」とツリー構造を表現するコードについて記述してきました。

ここでは、先の記事で使ったコードをリファクタリングして、より汎用性と移植性の高いコードを作成してみたいと思います。

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

これまでのコードでは、ルートノードからの「深さ」を示す depth という変数を構造体の中で保持していました。

ルートノードからの深さは比較的簡単に求めることができるので、あえて持つ必要はありません。

利用頻度を考慮するとあえてメンバーとして保持しなくてもよいケースがほとんどでしょう。むしろこのような特殊な変数を保持することでコードの見通しなどが悪くなってしまったりする危険性があります。

ツリー構造を表現するには、最低限子ノードと隣ノードのポインタを保持しておけばいいわけで、それにノードで保持したい情報を加えた構造体にするのがよいでしょう。

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

のように depth をなくし、構造体をシンプルにします。

ノードジェネレイター

これまでのコードでは、以下のような append 関数を用意して、ノードの初期化を行なっていました。

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

汎用性を高め、後からのメンテナンスを考慮すると、初期化部分は分離した方がよいでしょう。

ふうこさんからのご指摘の通り、node_t のポインタを返り値として返す create 関数を作成してみます。

node_t* create(const char* name)
{
  node_t* node; // *1
  node->name = name;
  node->child = NULL;
  node->next = NULL;
  return node;
}

このようにしたいところですが、このコードは正しく動作しません。

*1 で指定している node はローカルな変数なので、create 関数のブロックを抜けると消えてしまいます。malloc 関数を使ってメモリを確保する必要があります。

node_t* create(const char* name)
{
  node_t* node = (node_t*)malloc( sizeof(node_t) );
  if ( node == NULL ) exit( EXIT_FAILURE );
  node->name = name;
  node->child = NULL;
  node->next = NULL;
  return node;
}

ノードデストラクタ

割り当てたメモリは、どこかで解放する必要があります。

今回のような短いプログラムでは、特に必要ではないかもしれませんが、念のため後始末を行なう関数も作成しておきましょう。

void destroy(node_t* node)
{
  free(node);
  node = NULL;
}

ノードを破棄する create 関数は、シンプルで単純に free 関数を呼び出しているだけです。二重に free しないようにノードのポインタに NULL をセットしています。

ついでにツリーそのものを破棄する関数も考えてみます。ルートノードを渡したら、そのツリーの全ノードを解放します。

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

ここでも再帰的にノードを辿っていき、削除を実行しています。

注意して欲しいのは、自身の破棄を再帰した後に行なっているところです。こうしないと、再帰する前に自身が破棄されてしまい、正しく動作しません。

関連関数の変更

ノードの構造体から depth というパラメータを除いたので、ノードを表示する関数などはそのままでは動きません。

「深さ」を外部から引き渡すように変更します。

void append(node_t* parent, node_t* node)
{
  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 depth)
{
  int i;
  for (i=0;i<depth;i++)
  {
    printf(" ");
  }
  printf("- %s\n",node->name);
}

void show_tree_dfs(node_t* node, int depth)
{
  if (node == NULL) return;
  display(node, depth);
  show_tree_dfs(node->child, depth + 1);
  show_tree_dfs(node->next, depth);
}

#define STACK_NUM 100
void show_tree_bfs(node_t* node)
{
  if (node == NULL) return;
  node_t* queue[STACK_NUM];
  int depth = 0;
  int num = 0;
  queue[ num++ ] = node;
  while ( 1 )
  {
    node_t* buf[STACK_NUM];
    int buf_num = 0;
    while ( num != 0 )
    {
      node = queue[ --num ];
      while (node != NULL)
      {
        display(node, depth);
        if (node->child != NULL)
        {
          buf[ buf_num++ ] = node->child;
          if (buf_num >= STACK_NUM) exit( EXIT_FAILURE );
        }
        node = node->next;
      }
    }
    if ( buf_num == 0 ) break;
    while ( buf_num != 0 )
    {
      queue[ num++ ] = buf[ --buf_num ];
      if (num >= STACK_NUM) exit( EXIT_FAILURE );
    }
    depth++;
  }
}

ツリーを深さ優先で再帰的に走査する関数 show_tree_dfs でも「深さ」のパラメータを渡すように変更しています。

子ノードを辿るときだけ、depth + 1 で引き渡しているのがポイントです。

完成

できあがったプログラムは、それなりに長くなってしまうので「続き」に記載します。