2分探索木の全てのパスに対してなんかする。

C Programming

どうもです。
4回目のコーヒーゼリーをまだ作ってない whitypig です。
いや，4回目を作ろうと思って，ゼラチンを買ってきたのはいいが，
インスタントコーヒーを買ってくるのを忘れた。
さすがにコーヒーメーカーで作ったコーヒーを使う気にはなれず，
また，コンビニに行けばあるけど，高いので渋々あきらめました。

2分木のすべての経路に対してなんかしたい。

全てのノードについてなんかするはいけるけど，根から葉までの各パスについて
なんかしたいというのは，ググっても見つかりませんでした。
だもんで，頑張って書いたんだけど，不安だから，さらして，
間違いを指摘してもらおうというのが，今回の裏テーマ。
あっ，裏テーマ言っちゃった。

ソース

実際に使ったものを若干修正したので動くか不安。
不安なら，確かめよう!
というわけで，必要な部品も用意してきた。
ちなみに，root の親ノードは，NULL というのが前提です。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

enum { NUM = 10, };

typedef struct node {
  int key;
  struct node *left;
  struct node *right;
  struct node *parent;
  /* その他のメンバは何でも。 */
} NODE;

static void do_something_on_each_path();
static void do_something_on_path(NODE *path[]);
static void setup_random_array(int array[], int n);
static void setup_tree(NODE **root, int array[], int n);
static void setup_random_tree(NODE **root);
static void dispose_tree(NODE *root);
static int insert(NODE **root, int key);

int main(void)
{
  do_something_on_each_path();
  return 0;
}

/**
 * 全てのパスを調べる。
 * ここで言うパスとは，根から葉までの1つの経路のこと。
 * 5回，木を作って各パスを表示してみる。
 */
static void do_something_on_each_path(void)
{
  /*
   * 適当にバランスの取れた 2 分木なら，
   * 10万くらいまでのノードを 40 でカバーできるはず。
   * 心配なら，path を動的に確保するリストなり，
   * スタックなりにすればいいと思います。
   * というか，スタックにするべき。
   */
  NODE *path[40] = { NULL }; /* パスを記録する */
  int path_ix = -1;
  int i;
  NODE *root = NULL;
  NODE *p = NULL, *pp = NULL;
  const int TIMES_OF_TEST = 5;    /* テストの回数 */
  int times = 0;                 /* 実行したテストの回数 */

init:
  if (times >= TIMES_OF_TEST) {
    return;
  }
  for (i = 0; i < 40; i++) {
    path[i] = NULL;
  }
  root = NULL;
  /* 適当な木を作る */
  printf("[%3d]\n", times + 1);
  setup_random_tree(&root);
  /* 一番左のパスを記録して，それを基準にする */
  path_ix = 0;
  for (p = root, pp = NULL; p != NULL;) {
    path[path_ix++] = p;
    pp = p;
    if (p->left != NULL) {
      p = p->left;
    }
    else if (p->right != NULL) {
      /* 左に行けなかったら右に行けるか調べる */
      /* 実は，ここの else if が抜けていてバグってたのらぁ。*/
      p = p->right;
    }
    else {
      /* 葉まで降りてきた */
      break;
    }
  }
  /* まず，このパスに対してしたいことをする */
  do_something_on_path(path);

  /* 一番左のパスを元に調べて行く。 */
  for (;;) {
    for (;;) {
      /* 前回のパスの途中で，行ってない最下の分岐点まで降りる */
      p = path[--path_ix];
      pp = p->parent;
      if (pp == NULL) {
        /* root に帰ってきた */
        dispose_tree(root);     /* 木を解放してあげる */
        times++;
        goto init;
      }
      if (p == pp->left && pp->right != NULL) {
        /* その1つ上に右の分岐点があればそちらへ行く */
        p = pp->right;
        break;
      }
    }
    /* p から葉まで，path に記録しながら降りる */
    for (;;) {
      path[path_ix++] = p;
      if (p->left != NULL) {
        p = p->left;
      }
      else if (p->right != NULL) {
        p = p->right;
      }
      else {
        /* 葉まで降りてきた */
        path[path_ix] = NULL;
        do_something_on_path(path);
        break;
      }
    }
  }
}

/**
 * パスを表示するだけ。
 * path[] は NULL で終端されていると仮定できる。
 */
static void do_something_on_path(NODE *path[])
{
  int i;
  for (i = 0; path[i] != NULL; i++) {
    assert(i < 40);
    printf("%d,", path[i]->key);
  }
  printf("\n");
}

static void setup_tree(NODE **root, int array[], int n)
{
  int i;

  for (i = 0; i < n; i++) {
    assert(insert(root, array[i]) == 0);
  }
}

static void setup_random_tree(NODE **root)
{
  int i;
  int array[NUM] = { -1 };
  setup_random_array(array, NUM);
  printf("[array]: ");
  for (i = 0; i < NUM; i++) {
    printf("%d, ", array[i]);
  }
  printf("\n");
  setup_tree(root, array, NUM);
}

/**
 * ランダムで重複なしの値を配列に格納する。
 */
static void setup_random_array(int array[], int n)
{
  int i, j, val;
  char f_created[(NUM * 10 + 7) / (sizeof(char) * 8)] = { 0 };

  /* ランダムデータを用意する */
  srand(clock() + rand());
  for (i = 0; i < n; i++) {
    for (;;) {
      val = rand() % (NUM * 10);
      char c = f_created[val / 8 ];
      if ((c & (1U << (val % 8))) == 0) {
        f_created[val / 8] |= (1U << (val % 8));
        array[i] = val;
        break;
      }
    }
  }
  /* 重複チェック */
  for (i = 0; i < NUM; i++) {
    for (j = 0; j < NUM; j++) {
      if (i != j) {
        assert(array[i] != array[j]);
      }
    }
  }
}

static void dispose_tree(NODE *p)
{
  if (p == NULL) {
    return;
  }
  else {
    dispose_tree(p->left);
    dispose_tree(p->right);
    free(p);
  }
}

int insert(NODE **root, int key)
{
  NODE *p = NULL, *pp = NULL;

  if (root == NULL) {
    return -1;
  }

  if (*root == NULL) {
    *root = malloc(sizeof(NODE));
    (*root)->key = key;
    (*root)->parent = NULL;
    (*root)->left = (*root)->right = NULL;
    return 0;
  }

  p = *root;
  pp = NULL;
  while (p) {
    pp = p;
    if (key < p->key) {
      p = p->left;
    }
    else if (key > p->key) {
      p = p->right;
    }
    else {
      /* キーが重複している */
      return -1;
    }
  }

  NODE *newnode = malloc(sizeof(NODE));
  newnode->left = newnode->right = NULL;
  newnode->key = key;
  newnode->parent = pp;

  if (key < pp->key) {
    pp->left = newnode;
  }
  else {
    pp->right = newnode;
  }
  return 0;
}

実行結果

配列の中身と，各パスを表示しています。
配列の 0 番目から順番に木に挿入しています。
2個目のパターンまで紙に書いて，手動で確認したところで
バグを発見して。んで，それを修正したので，たぶん大丈夫なはず。

% ./allpath
[  1]
[array]: 19, 27, 79, 75, 28, 17, 25, 13, 57, 59, 
19,17,13,
19,27,25,
19,27,79,75,28,57,59,
[  2]
[array]: 43, 72, 42, 74, 32, 19, 73, 8, 20, 1, 
43,42,32,19,8,1,
43,42,32,19,20,
43,72,74,73,
[  3]
[array]: 45, 16, 23, 75, 97, 32, 25, 18, 98, 73, 
45,16,23,18,
45,16,23,32,25,
45,75,73,
45,75,97,98,
[  4]
[array]: 91, 46, 77, 62, 78, 86, 55, 30, 73, 32, 
91,46,30,32,
91,46,77,62,55,
91,46,77,62,73,
91,46,77,78,86,
[  5]
[array]: 94, 56, 98, 47, 81, 93, 33, 70, 78, 37, 
94,56,47,33,37,
94,56,81,70,78,
94,56,81,93,
94,98,

まとめ

頭がよい人はもっとスマートな方法で見つけられると思うので，
何か知っている人は，参考ページなどを教えてもらえたら，
ワタシは非常にうれしいです。
あと，綺麗ではないソースだとは思いますが，
突っ込んでくれるとうれしいです。