再帰なしで2分探索木を渡り歩こう!

どもども。
どうやるのかなぁと思ったので，調べたりして勉強しました。

最初はスタックでも使って記録していくのかなぁと思ったけど，
スタック不要な方法があった。
フラグを使うのもあったけど，2回以上渡り歩く際には，
フラグのリセットが必要になる予感。

ちなみに，これは，ワタシが考えたわけではないです。もちのろんですよ。

結論

再帰を使った方が楽だし，わかりやすい。
再帰を使わない理由がわからん。

サンプルコード

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

typedef struct tree {
  struct tree *parent;          /* これ重要 */
  struct tree *left;
  struct tree *right;
  int data;
} Tree;

/*
 * 再帰なしで，2分探索木を渡り歩こう。
 */
static void traverse(Tree *root, void f(Tree *node))
{
  if (!root) {
    printf("なるぽ。");
    return;
  }

  Tree *prev = root->parent;    /* 1つ前に見た節へのポインタ */
  Tree *curr = root;            /* 現在見ようとしている節へのポインタ */

  while (curr) {
    if (prev == curr->parent) {
      /* curr にやってきました。 */
      //f(curr);  // preorder なら，ここで関数を呼ぶ。
      /* まず左をみます。 */
      if (curr->left) {
        prev = curr;
        curr = curr->left;
        continue;
      }
      else {
        /* 左部分木がない場合は，左をみたことにする。 */
        prev = curr->left;
      }
    }

    if (prev == curr->left) {
      /* もう左側には行ってきました。*/
      f(curr); // inorder の場合はここで関数を適用。

      /* 左部分木を見たので，右部分木をチェックする。 */
      if (curr->right) {
        /* 右部分木がある場合は，そっちへ行ってチェックする。 */
        prev = curr;
        curr = curr->right;
        continue;
      }
      else {
        /* 右にはもうなにもない。。。 */
        prev = curr->right;
      }
    }

    if (prev == curr->right) {
      // f(curr);  // postorder ならここで。
      /* 左右の部分木へ行ってきたので，1つ上へ上る。 */
      prev = curr;
      curr = curr->parent;
    }
  }

  return;
}

static void print(Tree *p) {
  assert(p != NULL);
  printf("%d, ", p->data);
}

int main(void) {
  // こんな感じの木。
  //         10
  //      5      15
  //   2      13    18

  Tree root = { NULL, NULL, NULL, 10 };
  Tree left = { &root, NULL, NULL, 5 };
  Tree right = { &root, NULL, NULL, 15 };
  Tree lleft = { &left, NULL, NULL, 2 };
  Tree rleft = { &right, NULL, NULL, 13 };
  Tree rright = { &right, NULL, NULL, 18 };

  root.left = &left;
  root.right = &right;
  left.left = &lleft;
  right.left = &rleft;
  right.right = &rright;

  traverse(&root, print);
  printf("\n");

  return 0;
}

実行結果

% gcc -Wall -W -g bsearchtree.c -o bsearchtree

% ./bsearchtree
2, 5, 10, 13, 15, 18, 

たぶんこれでオッケー牧場。