import java.util.*;
class BinaryTree<T extends Comparable<? super T>> {
class Node<T>{
Node<T> left;
Node<T> right;
T key;
Node(T newKey) {
left = null;
right = null;
key = newKey;
}
}
private Node<T> root;
public BinaryTree() {
root = null;
}
public void insert(T newKey) {
Node<T> workNode = root;
Node<T> parentNode = null;
while (workNode != null) {
parentNode = workNode;
if (newKey.compareTo(workNode.key) < 0) {
workNode = workNode.left;
} else {
workNode = workNode.right;
}
}
if (parentNode == null) {
root = new Node<T>(newKey);
} else if (newKey.compareTo(parentNode.key) < 0) {
parentNode.left = new Node<T>(newKey);
} else {
parentNode.right = new Node<T>(newKey);
}
}
public Node<T> delete(T key) {
if (root == null) {
return null;
}
Node<T> workNode = root;
Node<T> parentNode = null;
while (key.compareTo(workNode.key) != 0) {
if (key.compareTo(workNode.key) < 0) {
if (workNode.left == null) {
return null;
}
parentNode = workNode;
workNode = workNode.left;
} else {
if (workNode.right == null) {
return null;
}
parentNode = workNode;
workNode = workNode.right;
}
}
if (workNode.right == null) {
setChild(parentNode, workNode.left, workNode.key);
return workNode;
} else if (workNode.left == null) {
setChild(parentNode, workNode.right, workNode.key);
return workNode;
} else {
Node<T> replaceNode = workNode.left;
Node<T> parentReplaceNode = workNode;
while (replaceNode.right != null) {
parentReplaceNode = replaceNode;
replaceNode = replaceNode.right;
}
if (parentReplaceNode == workNode) {
setChild(parentNode, replaceNode, workNode.key);
parentReplaceNode.left = null;
replaceNode.right = workNode.right;
return workNode;
} else {
setChild(parentNode, replaceNode, workNode.key);
parentReplaceNode.right = replaceNode.left;
replaceNode.left = workNode.left;
replaceNode.right = workNode.right;
return workNode;
}
}
}
private Node<T> setChild
(Node<T> targetNode, Node<T> newNode, T key) {
if (targetNode == null) {
root = newNode;
return null;
} else if (key.compareTo(targetNode.key) < 0) {
targetNode.left = newNode;
return targetNode;
} else {
targetNode.right = newNode;
return targetNode;
}
}
public void printTree() {
if (root == null) {
} else {
traverseInorder(root);
}
}
private void traverseInorder(Node<T> tempNode) {
if (tempNode != null) {
traverseInorder(tempNode.left);
System.
out.
print("(" + tempNode.
key + ") "); traverseInorder(tempNode.right);
} else {
return;
}
}
public static void main
(String[] args
) { final int MAXKEY = 100;
BinaryTree<Integer> tree = new BinaryTree<>();
int numberOfNodes = rand.nextInt(10);
for (int i = 0; i < numberOfNodes; i++) {
tree.insert(rand.nextInt(MAXKEY));
}
tree.printTree();
for (int i = 0; i < numberOfNodes; ++i) {
int input = 0;
do {
input = rand.nextInt(MAXKEY);
} while (tree.delete(input) == null);
System.
out.
println("(" + input
+ ") を削除"); tree.printTree();
}
}
}