お知らせ

ただいま、シンタックスハイライターの設定を見直しております。
プログラムが見にくくなっているページがありますが、ご容赦ください。

さまざまなデータ構造(9)二分木2

データ構造

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

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

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

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メソッドを作るのが案外時間がかかってしまいました。ということで、今回はこれでおしまい。それではまた。

この記事を書いた人
春日井 優

高校で情報科という教科を担当しています。以前は数学科も担当していました。(今でも数学科の教員免許状は有効です。)プログラムを覚えたのは、「ゲームセンターあらし」という漫画のキャラクターがBASICを解説する「こんにちはマイコン」を読んだことがきっかけでした。

Posted by kasugai