什么是二叉查找树
二叉查找树，英文名Binary Search Tree，又叫二叉搜索树，二叉排序树
二叉查找树是一种特殊的二叉树，它在二叉树的基础上，增加了如下规定
- 树的每个节点包含一个数值，并且数值是可以比较大小的
- 树的每个节点的值不能重复
- 对于任何一个节点，其左子节点的值小于父节点，右子节点的值大于父节点
简单来说，就是数值左小右大的二叉树
二叉查找树的特点就决定了，它是用来排序和查找用的
二叉查找树插入规则
二叉查找树的插入操作特别简单，小的往左插，大的往右插，已存在的不插就行了
- 如果树为空，则直接将插入的值作为根节点
- 如果树不为空，则将插入值和根节点大小做比较，相等则不插入，小于根节点则插入左子树，大于根节点则插入右子树，如果不存在子树，则直接以当前值作为子树根节点
- 对于子树，采用和根节点一样的策略，递归寻找插入位置
二叉查找树删除规则
二叉查找树的删除操作，则要讲究一点技巧了
因为树中间的枝节点被删除后，会留下一个空洞，一定要想办法补上空位才行
我们的做法是，将被删除位置的右子节点移上来填充空位，因为右子节点的值是大于父节点的，移上来仍然可以保持左小右大的特征
右子节点移上来之后，右子节点的位置就会变成空位了，此时我们只要再按上面的方式进行递归，把右子节点的右子节点再移上来，直到没有右子节点为止
完整的删除规则如下
- 首先，得对二叉查找树进行遍历，找到要删除的节点
- 如果被删节点正好是根节点，则直接将根节点指针置空，删除结束
- 如果被删节点无子树，则直接将其从父节点移除，删除结束
- 如果被删节点只有一颗子树，则将被删节点父节点的指针，直接指向该子树的根节点
- 如果被删节点有两颗子树，则将右子树根节点的值移动到被删节点上，再以同样的方式，递归删除右子树根节点
具体流程如下图所示，红色代表待删除节点，黑色表示已被替换的节点
代码实现
二叉查找树的基本功能包括：插入、移除、遍历、查找最大值、查找最小值
public class BinaryNode {
T value;
BinaryNode left;
BinaryNode right;
public int getChildCount() {
if (left == null && right == null)
return 0;
if (left != null && right != null)
return 2;
return 1;
}
@Override
public String toString() {
return String.valueOf(value);
}
}
import java.util.LinkedList;
import java.util.List;
public class BinarySearchTree {
BinaryNode root;
public boolean Empty() {
return root == null;
}
public void Clear() {
root = null;
}
//插入数据
public void Insert(T value) {
//树为空，直接创建根节点
if (root == null) {
BinaryNode node = new BinaryNode();
node.value = value;
root = node;
return;
}
//递归遍历所有节点，寻找插入位置
Insert(root, value);
}
//递归遍历所有节点，寻找插入位置
protected void Insert(BinaryNode node, T value) {
//值等于当前节点，已存在，直接结束
if (value.compareTo(node.value) == 0)
return;
//值小于当前节点，插入到左子树
if (value.compareTo(node.value) 0) {
if (node.right == null) {
BinaryNode newNode = new BinaryNode();
newNode.value = value;
node.right = newNode;
return;
}
Insert(node.right, value);
}
}
//移除数据
public void Delete(T value) {
//树为空，什么都不做
if (root == null)
return;
//被删节点正好是根节点，直接将根节点指针置空
if (value.compareTo(root.value) == 0) {
root = null;
return;
}
//递归移除数据
FindAndDelete(value, root);
}
//递归移除数据
//该方法主要负责找到删除节点
protected void FindAndDelete(T value, BinaryNode parent) {
//查到叶节点仍然无数据，结束
if (parent.getChildCount() == 0)
return;
//值在左子树上
if (parent.left != null && value.compareTo(parent.value) 0) {
//不在右子树根节点上，继续递归查找
if (value.compareTo(parent.right.value) != 0) {
FindAndDelete(value, parent.right);
return;
}
//找到要删除的节点，删除之
DeleteNode(parent.right, parent, false);
return;
}
}
//递归移除数据
//该方法负责找到节点后，执行真正的删除操作，具体规则如下
//1. 如果被删节点无子树，则直接将其从父节点移除，删除结束
//2. 如果被删节点只有一颗子树，则将被删节点父节点的指针，直接指向该子树的根节点
//3. 如果被删节点有两颗子树，则将右子树根节点的值移动到被删节点上，再以同样的方式，递归删除右子树根节点
protected void DeleteNode(BinaryNode node, BinaryNode parent, boolean isLeft) {
//无子树，直接将其从父节点移除
if (node.getChildCount() == 0) {
if (isLeft)
parent.left = null;
else
parent.right = null;
return;
}
//只有一颗子树，将被删节点父节点的指针，直接指向该子树的根节点
if (node.getChildCount() == 1) {
BinaryNode newNode = node.left != null ? node.left : node.right;
if (isLeft)
parent.left = newNode;
else
parent.right = newNode;
return;
}
//有两颗子树，将右子树根节点的值移动到被删节点上，再以同样的方式，递归删除右子树根节点
node.value = node.right.value;
DeleteNode(node.right, node, false);
}
//查找最小值
public T FindMin() {
if (root == null)
return null;
return FindMin(root);
}
//递归查找最小值
protected T FindMin(BinaryNode node) {
if (node.left == null)
return node.value;
return FindMin(node.left);
}
//查找最大值
public T FindMax() {
if (root == null)
return null;
return FindMax(root);
}
//递归查找最大值
protected T FindMax(BinaryNode node) {
if (node.right == null)
return node.value;
return FindMax(node.right);
}
//广度遍历，用于打印数据
public List traverse() {
List resultList = new LinkedList();
traverse(root, resultList);
return resultList;
}
//广度遍历，用于打印数据
protected void traverse(BinaryNode parentNode, List resultList) {
if (parentNode == null)
return;
resultList.add(parentNode);
if (parentNode.left != null)
resultList.add(parentNode.left);
if (parentNode.right != null)
resultList.add(parentNode.right);
if (parentNode.left != null) {
traverse(parentNode.left.left, resultList);
traverse(parentNode.left.right, resultList);
}
if (parentNode.right != null) {
traverse(parentNode.right.left, resultList);
traverse(parentNode.right.right, resultList);
}
}
}
import java.util.List;
@SuppressWarnings("all")
public class Demo {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
bst.Insert(90);
bst.Insert(30);
bst.Insert(99);
bst.Insert(20);
bst.Insert(50);
bst.Insert(40);
bst.Insert(70);
bst.Insert(60);
bst.Insert(80);
//查找最大值和最小值
Comparable min = bst.FindMin();
Comparable max = bst.FindMax();
System.out.println("Min：" + min);
System.out.println("Max：" + max);
//删除元素
bst.Delete(30);
//按广度优先算法打印结果
List list = bst.traverse();
for (Object item : list)
System.out.print(item + " ");
}
}
