二分探索木（Javaサンプルプログラム）
以下の記事を参考にして、二分探索木のJavaプログラムを作成してみました。
・
【1日1Java】ジェネリックスを使って二分探索木を実装
・
二分木図を印刷する方法は？
削除メソッドについては以下の記事を参考にしました。
・
二分探索木削除操作
備考：
・NodeはジェネリックにせずIntegerにして一切のジェネリックは排除。
・なるべくコードを見やすいようにクリーニングしました。
・削除メソッドは上記一番目のコードを無理やり3番目の記事のコードに置き換えているため
整合性に欠けます。
・中身のアルゴリズムに関しては上記記事を参考にしてください。
●BinTreeNode.java
package treeInt;
// ツリーノードの実装
public class BinTreeNode {
Integer element; // 数値をノードの要素に持つ。
BinTreeNode left; // 左ノード
BinTreeNode right; // 右ノード
public BinTreeNode() {
}
public BinTreeNode(Integer e) {
this.element=e;
}
// ツリーを辿って階層構造をCUIイメージで表示するためのメソッド
// 再帰を使って表示している。
public StringBuilder toString(StringBuilder prefix, boolean isTail, StringBuilder sb) {
if (right != null) {
right.toString(
new StringBuilder().append(prefix)
.append(isTail ? "| " : " "), false, sb);
}
sb.append(prefix)
.append(isTail ? "+-- " : "+-- ").append(element).append("\n");
if (left != null) {
left.toString(
new StringBuilder().append(prefix)
.append(isTail ? " " : "| "), true, sb);
}
return sb;
}
@Override
public String toString() {
return this.toString(new StringBuilder(), true, new StringBuilder()).toString();
}
}
●BinTree.java
package treeInt;
public class BinTree {
BinTreeNode root;
int count; // 登録数をカウント
public void search(Integer e) {
if (root == null) {
return;
} else {
BinTreeNode parent = null;
BinTreeNode current = root;
search(e, parent, current);
}
}
public void search(Integer e, BinTreeNode parent, BinTreeNode current) {
if (e == current.element) {
System.out.println(e + " ⇒ Search success");
return;
} else if (e <= current.element && current.left != null) {
search(e, current, current.left);
} else if (e > current.element && current.right != null) {
search(e, current, current.right);
}
}
public void insert(Integer e) {
// rootが初期状態であれば最初に初期化して数値をノードに登録する
if (root == null) {
root = new BinTreeNode(e);
count = 0;
} else {
// 親のノードをnull,現在のノードをルートに設定してサブメソッドを呼び出す
BinTreeNode parent = null;
BinTreeNode current = root;
insert(e, parent, current);
}
}
public void insert(Integer e, BinTreeNode parent, BinTreeNode current) {
// 登録する数値が既に会った場合は何もせずにリターンする
if (e == current.element) {
return;
} else {
// そうでなければサブノードを再帰的に辿る。
// 親のノードを現在のノードに設定して下位のノードを辿る準備をする
parent = current;
// 登録する数値が現在のノードの数値よりも小さい場合は左ノード、
// 大きい場合は右ノードを現在のノードに設定する。
current = (e <= current.element) ? current.left : current.right;
// 現在のノードがnullになったら登録処理を行う。
if (current == null) {
current = new BinTreeNode(e);
count++;
// 親のノードよりも小さければ左ノードに追加
// そうでなければ右ノードに追加する。
if (e <= parent.element) {
parent.left = current;
} else {
parent.right = current;
}
} else {
// まだ登録できないため再帰的に辿っていく
insert(e, parent, current);
}
}
}
public void delete(Integer e) {
if (root == null) {
return;
} else {
BinTreeNode parent = null;
BinTreeNode current = root;
deleteNode(current, e);
}
}
// currentの最も左の方向にあるノードを返す
// それがcurrentのサブツリーエントリの中の最も小さいノードである。
public BinTreeNode minNode(BinTreeNode current) {
BinTreeNode tmp = current;
while (tmp != null && tmp.left != null)
tmp = tmp.left;
return tmp;
}
// ツリーから与えられたノードを削除する。
public BinTreeNode deleteNode(BinTreeNode current, int e) {
// currentが空ならば、current(null)を返す。
if (current == null)
return current;
// 削除すべきノードは、leftのサブツリーにある
if (e < current.element)
current.left = deleteNode(current.left, e);
// 削除すべきノードは、rightのサブツリーにある
else if (e > current.element)
current.right = deleteNode(current.right, e);
// currentのノードが削除されるべきである
else {
// Case 1 + Case 2
// leftがnullであるということは、２つの場合のどちらかという意味がある
if (current.left == null) {
return current.right;
}
// Case 2
// ノードはleftを持っているが、rightを持っていない。
// だから単一の子だけをもっている。
else if (current.right == null) {
return current.left;
}
// Case 3
// 最初にsuccessorを見つける
// successorは二分木をinorderで探索して次(next)にくるelementを持っているノード
// だからrightサブツリー内のもっともleft方向のノードである。
BinTreeNode successor = minNode(current.right);
// currentノードをsuccessorに置き換える
current.element = successor.element;
// 今単純にcurrentの右からsuccessorを削除する
current.right = deleteNode(current.right, successor.element);
count--;
}
return current;
}
// 前順 (preorder)
public void preorder() {
preorder(root);
System.out.println();
}
public void preorder(BinTreeNode treeNode) {
if (treeNode == null) {
return;
}
System.out.print(treeNode.element + " ");
preorder(treeNode.left);
preorder(treeNode.right);
}
// 間順 (inorder)
public void inorder() {
inorder(root);
System.out.println();
}
public void inorder(BinTreeNode treeNode) {
if (treeNode == null) {
return;
}
inorder(treeNode.left);
System.out.print(treeNode.element + " ");
inorder(treeNode.right);
}
// 後順 (postorder)
public void postorder() {
postorder(root);
System.out.println();
}
public void postorder(BinTreeNode treeNode) {
if (treeNode == null) {
return;
}
postorder(treeNode.left);
postorder(treeNode.right);
System.out.print(treeNode.element + " ");
}
@Override
public String toString() {
return root.toString();
}
}
・
二分探索木（Javaサンプルプログラム）・続き
