さまざまなデータ構造（９）二分木２

2019-02-27データ構造

こんにちは。前回は二分木とその走査について取り上げました。今回はプログラムを整理しておきたいと思います。

二分木を作り走査するプログラム

それでは、実行用のプログラムを掲載します。

package data_structure;

public class MyTreeNodeExec {

  public static void main(String[] args) {

    MyTreeNode<String> node1 = new MyTreeNode<String>("i", null, null);
    MyTreeNode<String> node2 = new MyTreeNode<String>("h", null, null);
    MyTreeNode<String> node3 = new MyTreeNode<String>("g", node1, null);
    MyTreeNode<String> node4 = new MyTreeNode<String>("f", null, null);
    MyTreeNode<String> node5 = new MyTreeNode<String>("e", null, null);
    MyTreeNode<String> node6 = new MyTreeNode<String>("d", null, node2);
    MyTreeNode<String> node7 = new MyTreeNode<String>("c", node4, node3);
    MyTreeNode<String> node8 = new MyTreeNode<String>("b", node6, node5);
    MyTreeNode<String> node9 = new MyTreeNode<String>("a", node8, node7);

    printTree(node9);
    System.out.println("PreOrder  :  " + preOrder(node9));
    System.out.println("InOrder   : " + inOrder(node9));
    System.out.println("PostOrder : " + postOrder(node9));
    System.out.println("DepthFirstSearch   : " + depthFirst(node9));
    System.out.println("BreadthFirstSearch : " + breadthFirst(node9));
  }

  public static String preOrder(MyTreeNode<String> node) {

    String result = node.getElement();

    if (node.getLeft() != null) {
      result += " " + preOrder(node.getLeft());
    }

    if (node.getRight() != null) {
      result += " " + preOrder(node.getRight());
    }

    return result;
  }

  public static String inOrder(MyTreeNode<String> node) {

    String result = "";

    if (node.getLeft() != null) {
      result += inOrder(node.getLeft());
    }

    result += " " + node.getElement();

    if (node.getRight() != null) {
      result += inOrder(node.getRight());
    }

    return result;
  }

  public static String postOrder(MyTreeNode<String> node) {

    String result = "";

    if (node.getLeft() != null) {
      result += postOrder(node.getLeft());
    }

    if (node.getRight() != null) {
      result += postOrder(node.getRight());
    }

    result += " " + node.getElement();

    return result;
  }

  public static String depthFirst(MyTreeNode<String> node) {

    MyStack<MyTreeNode<String>> stack = new MyStack<MyTreeNode<String>>();
    MyTreeNode<String> tmp;
    String result = "";

    stack.push(node);

    while (!stack.empty()) {
      tmp = stack.pop();
      result += " " + tmp.getElement();

      if (tmp.getRight() != null) {
        stack.push(tmp.getRight());
      }

      if (tmp.getLeft() != null) {
        stack.push(tmp.getLeft());
      }
    }

    return result;
  }

  public static String breadthFirst(MyTreeNode<String> node) {

    MyQueue<MyTreeNode<String>> queue = new MyQueue<MyTreeNode<String>>();
    MyTreeNode<String> tmp;
    String result = "";

    queue.offer(node);

    while (!queue.isEmpty()) {
      tmp = queue.poll();
      result += " " + tmp.getElement();

      if (tmp.getLeft() != null) {
        queue.offer(tmp.getLeft());
      }

      if (tmp.getRight() != null) {
        queue.offer(tmp.getRight());
      }
    }

    return result;
  }

  public static void printTree(MyTreeNode<String> root) {
    System.out.println(TreeToString(0, "", root));
  }

  private static String TreeToString(int n, String direction, MyTreeNode<String> node) {

    String result = "";

    result += node.getElement();

    if (node.getLeft() != null && node.getRight() != null) {
      result += "\t┬";
    } else if (node.getRight() != null) {
      result += "\t─";
    } else if (node.getLeft() != null) {
      result += "\t┐";
    }

    if (node.getRight() != null && node.getLeft() != null) {
      result += TreeToString(n + 1, direction + "R", node.getRight());
    } else if (node.getRight() != null) {
      result += TreeToString(n + 1, direction + "r", node.getRight());
    }

    if (node.getLeft() != null) {
      result += "\n";
      for (int i = 0; i <= n; i++) {
        result += "\t";
        if (i < n && direction.substring(i, i + 1).equals("R")) {
          result += "│";
        } else if (i < n) {
          result += "　";
        }
      }
      result += "└";
      result += TreeToString(n + 1, direction + "L", node.getLeft());
    }

    return result;
  }
}

プログラム中のprintTreeメソッドとTreeToStringメソッドは前回紹介していませんでした。木が木のように見えるように表示するための部分になります。ちょっと説明が面倒なので、詳しい説明は割愛したいと思いますが、

親ノード┬左の子ノード─さらに孫ノード（左側の子の左側の孫）
　　　　└右の子ノード┐
　　　　　　　　　　　└もう一つの孫ノード（右側の子の右側の孫）

のように表示しているプログラムです。複雑になってしまったのは、見栄えをよくするために場合分けしたためです。

二分木を走査した結果

上のプログラムの実行結果は次になります。

a ┬c ┬g ┐
  │  │  └i
  │  └f
  └b ┬e
     └d ─h
PreOrder  :  a b d h e c f g i
InOrder   :  d h b e a f c i g
PostOrder :  h d e b f i g c a
DepthFirstSearch   :  a b d h e c f g i
BreadthFirstSearch :  a b c d e f g h i

プログラムをまとめただけですが、TreeToStringメソッドを作るのが案外時間がかかってしまいました。ということで、今回はこれでおしまい。それではまた。