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

Java Programming

どもども。
どうも寝ている間に偏頭痛がきたらしく，現在しんどい whitypig です。
というのも，途中，頭が痛くて起きたのだ。けど，非常にねみかったので，
頑張って寝た。当方，寝る前には冷えピタを張るようにしているので，
それで多少は和らいだか。
それでも頭を振ったりすると，痛い。


そうそう。プロテインを飲まないと，偏頭痛が訪れる確率が高い，
という何とも不思議なデータが取れた。
去年の正月，実家に帰ったときもそうだった。
プロテインと行っても，ザバスのウェイトダウンね。ソイ。
他にもミネラルやらなんやらが入っているらしい。
すでに届いたのですが，昨日はちょうど切らしていて，飲めなかったのです。
以前，マグネシウムをとるといいかもよ，と言われてから，マルチビタミンとか，
マルチミネラルをがしがし飲み始めたんですが，それ以降，発現頻度が下がった気がする。
なんか関係あるのかもね〜。


いやー，前置きが長くなりましたな。
現在，Java やり中なので，こないだの，2分探索木を再帰なしで渡り歩く，
を Java で書いてみようと思い，書いた次第です。

class Node {
  // この辺は，private にするべき?
  Node parent;
  Node left;
  Node right;
  int data;

  Node(Node parent, int data) {
    this.parent = parent;
    this.left = null;
    this.right = null;
    this.data = data;
  }

  Node(Node parent, Node left, Node right, int data) {
    this.parent = parent;
    this.left = left;
    this.right = right;
    this.data = data;
  }

  // フィールドを private にしなければ，いらんちゃーいらんか。
  public void setLeft(Node node) {
    left = node;
  }

  public void setRight(Node node) {
    right = node;
  }

  public void printNode() {
    System.out.print(data + ", ");
  }

}

public class BinSearchTree {
  private static Node root;

  public static void main(String[] args) {
    setupTree();
    traverse(root);
    System.out.println("");
  }

  /**
   * 2分木を，再帰を使わずに，渡り歩く。
   */
  private static void traverse(Node root) {
    Node prev = root.parent;
    Node curr = root;

    while (curr != null) {
      if (prev == curr.parent) {
        // 左部分木があるかどうかチェック。
        if (curr.left != null) {
          // あれば，それを見に行く。
          prev = curr;
          curr = curr.left;
          continue;
        }
        else {
          // なければ，見たことにする。
          prev = curr.left;
        }
      }

      // 左部分木を見たので，次は右。
      // 左部分木を見たときと同様の処理。
      if (prev == curr.left) {
        curr.printNode();
        // 右部分木があれば，見に行くよ。
        if (curr.right != null) {
          prev = curr;
          curr = curr.right;
          continue;
        }
        else {
          // なければ見たことに。
          prev = curr.right;
        }
      }

      // 右にいって帰ってきた。
      if (prev == curr.right) {
        // 上に1つ上る
        prev = curr;
        curr = curr.parent;
      }
    }
  }

  /**
   * お助けメソッド。
   */
  private static void setupTree() {
    root = new Node(null, 10);
    Node left = new Node(root, 5);
    root.setLeft(left);
    Node lleft = new Node(left, 2);
    left.setLeft(lleft);
    Node right = new Node(root, 15);
    root.setRight(right);
    Node rleft = new Node(right, 13);
    Node rright = new Node(right, 18);
    right.setLeft(rleft);
    right.setRight(rright);
  }
}

% javac BinSearchTree.java

% java BinSearchTree
2, 5, 10, 13, 15, 18,

こないだと同じく，たぶん大丈夫なはず。