/**
-
节点
-
@param
*/
private static class BinaryNode {
BinaryNode(AnyType theElement) {
this(theElement, null, null);
}
BinaryNode(AnyType theElement, BinaryNode left, BinaryNode right) {
element = theElement;
left = left;
right = right;
}
AnyType element; // the data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}
1.3、构造器和成员变量
private BinaryNode root;
private Comparator<? super AnyType> cmp;
/**
- 无参构造器
*/
public BinarySearchTree() {
this(null);
}
/**
-
带参构造器，比较器
-
@param c 比较器
*/
public BinarySearchTree(Comparator<? super AnyType> c) {
root = null;
cmp = c;
}
1.3、公共方法（public method）
主要包括插入，删除，找到最大值、最小值，清空树，查看元素是否包含；
/**
- 清空树
*/
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public boolean contains(AnyType x){
return contains(x,root);
}
public AnyType findMin(){
if (isEmpty()) throw new BufferUnderflowException();
return findMin(root).element;
}
public AnyType findMax(){
if (isEmpty()) throw new BufferUnderflowException();
return findMax(root).element;
}
public void insert(AnyType x){
root = insert(x, root);
}
public void remove(AnyType x){
root = remove(x,root);
}
1.4、比较函数
如果有比较器，就使用比较器，否则要求对象实现了Comparable接口；
private int myCompare(AnyType lhs, AnyType rhs) {
if (cmp != null) {
return cmp.compare(lhs, rhs);
} else {
return lhs.compareTo(rhs);
}
}
1.5、contains 函数
本质就是一个树的遍历；
private boolean contains(AnyType x, BinaryNode t) {
if (t == null) {
return false;
}
int compareResult = myCompare(x, t.element);
if (compareResult < 0) {
return contains(x, t.left);
} else if (compareResult > 0) {
return contains(x, t.rig
【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开：qq.cn.hn/FTf 免费领取
ht);
} else {
return true;
}
}
1.6、findMin
因为二叉搜索树的性质，最小值一定是树的最左节点,要注意树为空的情况。
/**
-
Internal method to find the smallest item in a subtree
-
@param t the node that roots the subtree
-
@return node containing the smallest item
*/
private BinaryNode findMin(BinaryNode t) {
if (t == null) {
return null;
}
if (t.left == null) {
return t;
}
return findMin(t.left);
}
1.7、findMax
最右节点；
/**
-
Internal method to find the largest item in a subtree
-
@param t the node that roots the subtree
-
@return the node containing the largest item
*/
private BinaryNode findMax(BinaryNode t){
if (t == null){
return null;
}
if (t.right == null){
return t;
}
return findMax(t.right);
}
1.8、insert
这个主要是根据二叉搜索树的性质，注意当树为空的情况，就可以加入新的节点了，还有当该值已经存在时，默认不进行操作；
/**
-
Internal method to insert into a subtree
-
@param x the item to insert
-
@param t the node that roots the subtree
-
@return the new root of the subtree
*/
private BinaryNode insert(AnyType x, BinaryNode t){
if (t == null){
return new BinaryNode<>(x,null,null);
}
int compareResult = myCompare(x,t.element);
if (compareResult < 0){
t.left = insert(x,t.left);
}
else if (compareResult > 0){
t.right = insert(x,t.right);
}
else{
//Duplicate; do nothing
}
return t;
}
1.9、remove
注意当空树时，返回null；
最后一个三元表达式，是在之前已经排除掉节点有两个儿子的情况下使用的。
/**
-
Internal method to remove from a subtree
-
@param x the item to remove
-
@param t the node that roots the subtree
-
@return the new root of the subtree
*/
private BinaryNode remove(AnyType x, BinaryNode t){
if (t == null){
return t; // Item not found ,do nothing
}
int compareResult = myCompare(x,t.element);
if (compareResult < 0){
t.left = remove(x,t.left);
}
else if (compareResult > 0){
t.right = remove(x,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
t = (t.left !=null) ? t.left:t.right;
return t;
}
/**
-
@author LongRookie
-
@description: 二叉搜索树
-
@date 2021/6/26 19:41
*/
import com.sun.source.tree.BinaryTree;
import java.nio.BufferUnderflowException;
import java.util.Comparator;
/**
- 二叉搜索树
*/
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
/**
-
节点
-
@param
*/
private static class BinaryNode {
BinaryNode(AnyType theElement) {
this(theElement, null, null);
}
BinaryNode(AnyType theElement, BinaryNode left, BinaryNode right) {
element = theElement;
left = left;
right = right;
}
AnyType element; // the data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}
private BinaryNode root;
private Comparator<? super AnyType> cmp;
/**
- 无参构造器
*/
public BinarySearchTree() {
this(null);
}
/**
-
带参构造器，比较器
-
@param c 比较器
*/
public BinarySearchTree(Comparator<? super AnyType> c) {
root = null;
cmp = c;
}
/**
- 清空树
*/
public void makeEmpty() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public boolean contains(AnyType x){
return contains(x,root);
}
public AnyType findMin(){
if (isEmpty()) throw new BufferUnderflowException();
return findMin(root).element;
}
public AnyType findMax(){
if (isEmpty()) throw new BufferUnderflowException();
return findMax(root).element;
}
public void insert(AnyType x){
root = insert(x, root);
}
public void remove(AnyType x){
root = remove(x,root);
}