javaデータ構造——Binary SearchTree(二叉検索ツリー)
3510 ワード
package com.tig.tree;
/**
*
* @author Tig
* @param
*
*/
public class BinarySearchTree> {
private BinaryNode root;
public BinarySearchTree() {
root = null;
}
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public boolean contains(E e) {
return contains(e, root);
}
public boolean contains(E e, BinaryNode t) {
if (t == null) {
return false;
}
int compareResult = e.compareTo(t.element);
if (compareResult < 0) {
return contains(e, t.left);
} else if (compareResult > 0) {
return contains(e, t.right);
} else {
return true;
}
}
public E findMin() {
if ( isEmpty() ) {
throw new RuntimeException(" ");
}
return findMin(root).element;
}
private BinaryNode findMin(BinaryNode t) {
if (t == null) {
return null;
} else if (t.left == null) {
return t;
}
return findMin(t.left);
}
public E findMax() {
if ( isEmpty() ) {
throw new RuntimeException(" ");
}
return findMax(root).element;
}
private BinaryNode findMax(BinaryNode t) {
if (t != null) {
while (t.right != null) {
t = t.right;
}
}
return t;
}
public void insert(E e) {
root = insert(e, root);
}
private BinaryNode insert(E e, BinaryNode t) {
if (t == null) {
return new BinaryNode(e);
}
int compareResult = e.compareTo(t.element);
if (compareResult < 0) {
t.left = insert(e, t.left);
} else if (compareResult > 0) {
t.right = insert(e, t.right);
} else
; // do nothing
return t;
}
public void remove(E e) {
root = remove(e, root);
}
private BinaryNode remove(E e, BinaryNode t) {
if (t == null) {
return t;
}
int compareResult = e.compareTo(t.element);
if (compareResult < 0) {
t.left = remove(e, t.left);
} else if (compareResult > 0) {
t.right = remove(e, t.right);
} else if (t.left != null && t.right != null) { //Two children
t.element = findMin(t.right).element;
t.right = remove(t.element, t.right);
} else { //One child
t = (t.left != null) ? t.left : t.right;
}
return t;
}
public void printTree() {
if ( isEmpty() ) {
System.out.println("Empty tree");
} else {
printTree(root);
}
}
private void printTree(BinaryNode t) {
if (t != null) {
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
private static class BinaryNode {
E element;
BinaryNode left;
BinaryNode right;
public BinaryNode(E element) {
this(element, null, null);
}
public BinaryNode(E element, BinaryNode left, BinaryNode right) {
this.element = element;
this.left = left;
this.right = right;
}
}
}
テストcase:package com.tig.tree;
import org.junit.Test;
public class BinarySearchTreeTest {
@Test
public void test() {
BinarySearchTree tree = new BinarySearchTree<>();
for (int i = 0; i < 10; i++) {
tree.insert(i);
}
System.out.println(" :" + tree.findMax());
System.out.println(" :" + tree.findMin());
tree.remove(5);
tree.printTree();
}
}