二叉查找树（Binary Search Tree，简称BST）是一种常用的数据结构，它能够高效地进行查找、插入和删除操作。二叉查找树的特点是，对于树中的每个节点，其左子树中的所有节点都小于该节点，而右子树中的所有节点都大于该节点。本文将介绍如何使用Java实现二叉查找树，并实现常见的操作。
二叉搜索树BST
二叉搜索树的核心思想和二分查找类似，都是基于分治思想，利用了有序性,通过比较和分治，将问题规模减半，从而实现高效的查找。二叉树具有以下特点：
- 若左子树不为空，则左子树上的所有节点的值均小于它的根节点的值；
- 若右子树不为空，则右子树上的所有节点的值均大于它的根节点的值；
- 左、右子树也分别为二叉排序树。
如下图则是一个二叉搜索树
二叉搜索树的操作
二叉搜索树的操作常见的有插入元素、删除元素、查找元素、遍历树等。
插入
二叉树中进行插入元素操作时，只需要找到插入元素的父节点，插入到对应的位置即可；步骤如下：
从根节点开始，依次比较当前节点和待插入节点的值，如果根节点为null,则说明树为空，直接将待插入节点设置为根节点即可；
如待插入节点的值等于当前节点的值，则表示该节点已经存在于二叉搜索树中了；
如待插入节点的值小于当前节点的值，则在当前节点的左子树中继续比较，直到左子树为空，则当前节点为插入节点的父节点，将元素插入到当前节点的左子树即可；
如待插入节点的值大于于当前节点的值，则在当前节点的右子树中继续比较，直到右子树为空，则当前节点为插入节点的父节点，将元素插入到当前节点的右子树即可；
删除
删除操作稍微复杂一些，因为需要考虑三种情况：
- 要删除的节点是叶子节点。
找到要删除的节点。
将其父节点指向该节点的指针置为 null。
- 要删除的节点只有一个子节点。
找到要删除的节点。
将其父节点指向该节点的指针指向其子节点。
3 要删除的节点有两个子节点。
找到要删除的节点。
找到其右子树中的最小节点（或左子树中的最大节点）。
用该最小节点的值替换要删除的节点的值。
删除右子树中的最小节点（此时它一定没有左子树，因此可以按照情况 1 或情况 2 处理）。
查找
二叉搜索树的查找方式和二分查找类似，查找步骤如下：
将要查找的数据与根节点进行比较，如果相等就返回
如果小于就到左子树中递归查找
如果大于就到右子树中递归查找
如果查到左子树或者右子树为空还没有的话则查找的数据不在树中。
遍历
二叉搜索树的遍历操作包括前序遍历、中序遍历和后序遍历。中序遍历二叉查找树会得到一个升序的序列。
Java实现
以下是使用代码实现的插入元素、删除元素、查找元素、遍历操作；
/**
* 二叉树节点实体类
*/
@Data
public class BinaryTreeNode<T> {
private T val;
private BinaryTreeNode<T> left;
private BinaryTreeNode<T> right;
public BinaryTreeNode(T val) {
this.val = val;
}
}
/**
* 二叉搜索树
*/
@Data
public class BinarySearchTreeExample {
public static BinaryTreeNode<Integer> root;
public BinarySearchTreeExample() {
root = null;
}
/**
* 插入
*/
public static boolean add(BinaryTreeNode<Integer> node) {
//插入节点为空，则返回false
if(node == null){
return false;
}
//如果根节点为空，则直接赋值给根节点
if(root == null){
root = node;
return true;
}
BinaryTreeNode<Integer> parent = root;
//初始化查找节点的父节点
BinaryTreeNode<Integer> prev = null;
//查找待插入元素的父节点
while (parent != null){
prev = parent;
//如果插入节点的值小于当前节点的值
if(node.getVal() < parent.getVal()){
parent = parent.getLeft();
}
//如果插入节点的值大于当前节点的值
else if(node.getVal() > parent.getVal()){
parent = parent.getRight();
}
//如果插入节点的值等于当前节点的值，则说明元素已存在返回false
else {
return false;
}
}
// 小于父节点的值则设置为父节点的左子节点
if(node.getVal() < prev.getVal()){
prev.setLeft(node);
return true;
}
// 大于父节点的值则设置为父节点的右子节点
else if(node.getVal() > prev.getVal()){
prev.setRight(node);
return true;
}
return false;
}
/**
* 删除
*/
public static boolean remove(int key) {
//根节点为空，则返回false
if (root == null){
return false;
}
removeRec(root,key);
return true;
}
/**
* 递归查询待删除的元素并删除
*/
public static BinaryTreeNode<Integer> removeRec(BinaryTreeNode<Integer> node,int key) {
//跟节点为空，则返回false
if(node == null) return node;
//左子树中递归删除待删除的元素
if(node.getVal() > key){
node.setLeft(removeRec(node.getLeft(),key));
}
//右子树中查找待删除的元素
else if (node.getVal() < key) {
node.setRight(removeRec(node.getRight(),key));
}
//找到要删除的节点
else {
// 情况1：节点有一个子节点或没有子节点
if(node.getLeft() == null){
return node.getRight();
}else if (node.getRight() == null){
return node.getLeft();
}else {
// 情况2：节点有两个子节点
//查找待删除节点的左子树中的最大值
BinaryTreeNode<Integer> temp = node.getLeft();
int minv = temp.getVal();
while (temp.getRight() != null) {
minv = temp.getRight().getVal();
temp = temp.getRight();
}
node.setVal(minv);
// 删除左子树中的最大节点
node.setLeft(removeRec(node.getLeft(),node.getVal()));
}
}
return node;
}
/**
* 查询给定值的元素是否存在
*/
public static boolean get(int value){
BinaryTreeNode<Integer> current = root;
while (current != null){
//当前值等于给定值，查找成功，则返回true
if(current.getVal() == value){
return true;
}
//当前值大于给定值，则向左子树查找
else if(current.getVal() > value){
current = current.getLeft();
}
//当前值小于给定值，则向右子树查找
else if(current.getVal() < value){
current = current.getRight();
}
}
return false;
}
public static List<Integer> inorder() {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
inorderTraversal(root,result);
return result;
}
/**
* 中序遍历递归
*/
public static void inorderTraversal(BinaryTreeNode<Integer> node,List<Integer> result){
if(node == null){
return;
}
inorderTraversal(node.getLeft(),result);
result.add(node.getVal());
inorderTraversal(node.getRight(),result);
}
public static void main(String[] args) {
BinarySearchTreeExample bst = new BinarySearchTreeExample();
bst.add(new BinaryTreeNode<>(10));
bst.add(new BinaryTreeNode<>(5));
bst.add(new BinaryTreeNode<>(12));
bst.add(new BinaryTreeNode<>(1));
bst.add(new BinaryTreeNode<>(7));
bst.add(new BinaryTreeNode<>(15));
bst.add(new BinaryTreeNode<>(6));
bst.add(new BinaryTreeNode<>(9));
bst.add(new BinaryTreeNode<>(13));
System.out.println(bst.inorder().toString());
bst.remove(7);
System.out.println(bst.inorder().toString());
System.out.println(bst.get(9));
}
}
总结
通过本文，我们学习了如何使用Java实现二叉查找树，并实现了插入、查找、删除和遍历等基本操作。二叉查找树是一种非常高效的数据结构，适用于需要频繁查找、插入和删除的场景
