二叉排序树又称为二叉查找树，具备以下性质：
①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
③它的左、右子树也分别为二叉排序树；
二叉排序树使用链式存储，插入和删除的效率较好，又可以较高效的实现查找某个元素的功能。
中序遍历二叉排序树时能够得到一个有序序列。
测试二叉排序树.png
二叉排序树结点类
/**
* @author Shaw
* @version 创建时间：2018年12月9日 下午3:33:43
* 类说明:二叉排序树结点类
*/
class BiTNode {
//数据域
private int data;
//左右结点域
private BiTNode lchild, rchild;
public BiTNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public BiTNode getLchild() {
return lchild;
}
public void setLchild(BiTNode lchild) {
this.lchild = lchild;
}
public BiTNode getRchild() {
return rchild;
}
public void setRchild(BiTNode rchild) {
this.rchild = rchild;
}
@Override
public String toString() {
return "BiTNode [data=" + data + ", lchild=" + lchild + ", rchild=" + rchild + "]";
}
}
二叉排序树核心类
二叉排序树的建立就是不断执行插入操作的过程。
二叉排序树的删除分为三种情况讨论：
①当删除结点仅有左子树时，只需将此结点的左孩子替换它自己，就相当于删除了该结点。
②当删除结点仅有右子树时，只需将此结点的右孩子替换它自己即可。
③当删除结点左右子树都不为空时，可以在左子树中找到小于但最接近该值的结点替换它，即找到中序遍历中的前驱；也可以在右子树中找到大于但最接近该值的结点替换，即中序遍历中的后驱。
本例中采用的是前驱替换。
/**
*
* @author Shaw
* @version 创建时间：2018年12月9日 下午3:34:11
* 类说明:二叉排序树类
*/
class BinarySortTree {
public BiTNode root;
public BinarySortTree() {
root = null;
}
// 中序遍历
public void InOrderTraverse(BiTNode node) {
if (node == null) {
return;
}
InOrderTraverse(node.getLchild());
System.out.print(node.getData() + " ");
InOrderTraverse(node.getRchild());
}
// 二叉排序树查找
public BiTNode search_BST(int key) {
BiTNode current = root;
while (current != null) {
// 查找成功返回对应结点
if (key == current.getData()) {
return current;
} else if (key < current.getData()) {
current = current.getLchild();
} else {
current = current.getRchild();
}
}
return null;
}
// 二叉排序树插入
public void insert_BST(int key) {
// 空树情况
if (root == null) {
root = new BiTNode(key);
return;
}
// 结点已在树中存在时
if (search_BST(key) != null) {
return;
}
BiTNode node = new BiTNode(key);
BiTNode current = root;
BiTNode parent = null;
// 循环获取待插入结点的父结点位置
while (current != null) {
parent = current;
if (key < current.getData()) {
current = current.getLchild();
} else if (key > current.getData()) {
current = current.getRchild();
} else {
break;
}
}
// 判断插入的是左结点还是右结点
if (key < parent.getData()) {
parent.setLchild(node);
} else {
parent.setRchild(node);
}
}
// 二叉排序树删除
public boolean delete_BST(int key) {
// current结点指向待删除的结点
BiTNode current = root;
// parent结点指向待删除结点的父节点
BiTNode parent = null;
// 通过循环查找确定current和parent结点
while (current != null) {
// 待删除的结点的值小于根结点的值，查找左子树
if (key < current.getData()) {
parent = current;
current = current.getLchild();
}
// 待删除的结点的值小于根结点的值，查找右子树
else if (key > current.getData()) {
parent = current;
current = current.getRchild();
}
// 查找到结点后退出
else {
break;
}
}
// 空树的情况
if (current == null) {
return false;
}
// 右子树为空的情况
// 待删除结点的左结点"继承"该结点的位置
if (current.getRchild() == null) {
// 不是空树的情况
if (parent != null) {
// 待删除的结点是父节点的左结点
if (parent.getLchild() == current) {
// 将待删除结点的左结点设置为父结点的左结点
parent.setLchild(current.getLchild());
} else {
// 待删除的结点是父结点的右结点时将该结点的左结点设置为父结点的右结点
parent.setRchild(current.getLchild());
}
} else {
// 空树时将左结点赋值给根结点
root = current.getLchild();
}
}
// 左子树为空的情况
// 待删除结点的右结点"继承"该结点的位置
else if (current.getLchild() == null) {
if (parent != null) {
if (parent.getLchild() == current) {
parent.setLchild(current.getLchild());
} else {
parent.setRchild(current.getRchild());
}
} else {
root = current.getRchild();
}
}
// 左右子树均不为空的情况
// 在二叉排序树中序中选择该结点的前驱或者后继替换该结点，
// 也就是选择比该结点小或者比它大的最接近的两个数中的一个，本例选择的是比该结点小的结点
else {
// 用于替换的结点
BiTNode replaceNode = current.getLchild();
// 替换结点的父节点,初始化为待删除的结点
BiTNode replaceParentNode = current;
// 用于替换的结点存在右子结点时，因为右结点大于根结点的值，所以右子结点更接近被删除的结点
while (replaceNode.getRchild() != null) {
replaceParentNode = replaceNode;
replaceNode = replaceNode.getRchild();
}
// 替换结点不存在右子结点时
// 相等时由于使用的是前驱值代替，所以需要补充的是左子结点的值
if (replaceParentNode == current) {
replaceParentNode.setLchild(replaceNode.getLchild());
}
// replaceParentNode与current不相等时
// replaceNode肯定是大于replaceParentNode的值的,所以需要补充的是右子结点的值
else {
replaceParentNode.setRchild(replaceNode.getLchild());
}
// 替换对应的值
current.setData(replaceNode.getData());
}
return true;
}
}
测试程序：
public class BinarySortTreeMain {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93, 36, 39, 42, 62 };
BinarySortTree binarySortTree = new BinarySortTree();
System.out.println("原始序列：");
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
binarySortTree.insert_BST(a[i]);
}
System.out.println("\n二叉排序后的序列：");
binarySortTree.InOrderTraverse(binarySortTree.root);
System.out.print("\n查找37：");
BiTNode node = binarySortTree.search_BST(37);
if (node != null) {
System.out.println(true);
} else {
System.out.println(false);
}
System.out.print("查找22：");
node = binarySortTree.search_BST(22);
if (node != null) {
System.out.println(true);
} else {
System.out.println(false);
}
System.out.print("删除47：");
System.out.println(binarySortTree.delete_BST(47));
System.out.println("删除47后的序列：");
binarySortTree.InOrderTraverse(binarySortTree.root);
System.out.print("\n删除22：");
System.out.println(binarySortTree.delete_BST(22));
}
}
测试结果：
二叉排序树测试结果图.png
总结
二叉排序树以链接方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，插入删除的时间性能较好。对于二叉排序树的查找，比较次数等于给定值的结点在二叉排序树的层数。最少为1次，最多也不会超过树的深度。
缺点：当本例中的数组是{35,36,37,39,42,47,51,58,73,88,93,99}时，即数组元素从小到大有序时，此时的二叉排序树如图所示是一棵右斜树。当同样查找99结点时，测试例子需要2次比较，本例却需要12次比较，二者差异很大。也就是说，二叉排序树的查找性能主要取决于二叉排序树的形状，但本例中的二叉排序树的形状是由给定数组来构造的，即形状是不确定的。为此，我们需要构造平衡二叉树来解决这个问题。
右斜树.png
