Rhyme/ルックアップツリーADT-二叉ルックアップツリーの簡単なシミュレーションJava版
検索ツリーADT-二叉検索ツリーの簡単なシミュレーションJava版
package my.binary.search.tree;
/**
* ADT
* Integer
*
* @author RhymeChiang
* @date 2018/01/17
**/
public class BinarySearchTree<T extends Comparable super T>> {
/**
*
*/
private BinaryNode root;
/**
*
*
* @param
*/
private static class BinaryNode<T> {
private T element;
private BinaryNode left;
private BinaryNode right;
public BinaryNode() {
}
public BinaryNode(T element) {
this.element = element;
}
public BinaryNode(T element, BinaryNode left, BinaryNode right) {
this.element = element;
this.left = left;
this.right = right;
}
}
/**
*
*/
public void makeEmpty() {
root = null;
}
/**
*
*
* @return
*/
public boolean isEmpty() {
return root == null;
}
/**
* element
*
* @param element
* @return
*/
public boolean contains(T element) {
return contains(element, root);
}
/**
* element root
*
* @param element
* @param root
* @return
*/
private boolean contains(T element, BinaryNode root) {
if (root == null) {
return false;
}
int compareResult = element.compareTo(root.element);
if (compareResult > 0) {
return contains(element, root.right);
}
if (compareResult < 0) {
return contains(element, root.left);
}
return true;
}
/**
*
*
* @return
*/
public T findMin() {
if (findMin(root) != null) {
return findMin(root).element;
}
return null;
}
/**
*
*
* @param root
* @return
*/
private BinaryNode findMin(BinaryNode root) {
if (root == null) {
return null;
}
if (root.left != null) {
return findMin(root.left);
}
return root.left;
}
/**
*
*
* @return
*/
public T findMax() {
BinaryNode maxNode = findMax(root);
if (maxNode != null) {
return maxNode.element;
}
return null;
}
/**
*
*
* @param root
* @return
*/
private BinaryNode findMax(BinaryNode root) {
if (root == null) {
return null;
}
if (root.right != null) {
return findMax(root.right);
}
return root.right;
}
/**
* element
*
* @param element
*/
public void insert(T element) {
root = insert(element, root);
}
/**
* root
*
* @param element
* @param root
* @return
*/
private BinaryNode insert(T element, BinaryNode root) {
if (root == null) {
return new BinaryNode<>(element);
}
int compareResult = element.compareTo(root.element);
if (compareResult > 0) {
root.right = insert(element, root.right);
} else if (compareResult < 0) {
root.left = insert(element, root.left);
}
return root;
}
/**
* element
*
* @param element
*/
public void remove(T element) {
}
/**
* element
*
* @param element
* @param root
* @return
*/
private BinaryNode remove(T element, BinaryNode root) {
if (root == null) {
return null;
}
int compareResult = element.compareTo(root.element);
if (compareResult > 0) {
root.right = remove(element, root.right);
} else if (compareResult < 0) {
root.left = remove(element, root.left);
}
//
else if (root.left != null && root.right != null) {
root.element = findMin(root.right).element;
root.right = remove(root.element, root.right);
}
//
else {
root = (root.left != null) ? root.left : root.right;
}
return root;
}
}