1 二叉排序树的概述
本文没有介绍一些基础知识。对于常见查找算法，比如顺序查找、二分查找、插入查找、斐波那契查找还不清楚的，可以看这篇文章：常见查找算法详解以及Java代码的实现。
假设查找的数据集是普通的顺序存储，那么插入操作就是将记录放在表的末端，给表记录数加一即可，删除操作可以是删除后，后面的记录向前移，也可以是要删除的元素与最后一个元素互换，表记录数减一，反正整个数据集也没有什么顺序，这样的效率也不错。应该说，插入和删除对于顺序存储结构来说，效率是可以接受的，但这样的表由于无序造成查找的效率很低。
如果查找的数据集是有序线性表，并且是顺序存储的，查找可以用折半、插值、斐波那契等查找算法来实现，可惜，因为有序，在插入和删除操作上，为了维持顺序，需要移动大量元素，就需要耗费大量的时间。
有没有一种即可以使得插入和删除效率不错，又可以比较高效率地实现查找的算法呢？这就是二叉排序树。
二叉排序树（Binary Sort Tree），又称为二叉查找树/二叉搜索树（binary search tree）。它是具有下列性质的二叉树：
- 若它的左子树不空，则左子树上所有节点的值均小于它的根结构的值；
- 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
- 它的左、右子树也分别为二叉排序树；
- 二叉排序树也可以是一个空树。
构造一棵二叉排序树的目的，其主要目的并不是为了排序，而是为了提高查找和插入删除关键字的速度，用以提升数据结构的综合能力。不管怎么说，在一个有序数据集上的查找，速度总是要快于无序的数据集的，而二叉排序树这种非线性的结构，也有利于插入和删除的实现。
2 二叉排序树的构建
2.1 类架构
首先，最简单的节点对象还是需要一个数据域和两个引用域。
另外还需要一个比较器的引用，因为需要对元素进行排序，自然需要比较元素的大小，如果外部传递了比较器，那么就使用用户指定的比较器进行比较，否则，数据类型E必须是Comparable接口的子类，否则因为不能比较而报错。
另外，还需要提供中序遍历的方法，该遍历方法对于二叉排序树的结果将会顺序展示。
public class BinarySearchTree<E> {
private BinaryTreeNode<E> root;
private Comparator<? super E> cmp;
private int size;
public static class BinaryTreeNode<E> {
//数据域
E data;
//左子节点
BinaryTreeNode<E> left;
//右子节点
BinaryTreeNode<E> right;
public BinaryTreeNode(E data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
public BinarySearchTree(Comparator<? super E> cmp) {
this.cmp = cmp;
}
public BinarySearchTree() {
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private int compare(E e1, E e2) {
if (cmp != null) {
return cmp.compare(e1, e2);
} else {
return ((Comparable<E>) e1).compareTo(e2);
}
}
List<BinaryTreeNode<E>> str = new ArrayList<>();
public String toInorderTraversalString() {
//如果是空树,直接返回空
if (isEmpty()) {
return null;
}
//从根节点开始递归
inorderTraversal(root);
//获取遍历结果
String s = str.toString();
str.clear();
return s;
}
private void inorderTraversal(BinaryTreeNode<E> root) {
BinaryTreeNode<E> left = getLeft(root);
if (left != null) {
//如果左子节点不为null,则继续递归遍历该左子节点
inorderTraversal(left);
}
//添加数据节点
str.add(root);
//获取节点的右子节点
BinaryTreeNode<E> right = getRight(root);
if (right != null) {
//如果右子节点不为null,则继续递归遍历该右子节点
inorderTraversal(right);
}
}
public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.left;
}
public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.right;
}
public BinaryTreeNode<E> getRoot() {
return root;
}
}
2.2 查找的方法
查找的方法很简单：
- 若根节点的关键字值等于查找的关键字，成功，返回true；
- 否则，若小于根节点的关键字值，递归查左子树；
- 若大于根节点的关键字值，递归查右子树；
- 最终查找到叶子节点还是没有数据，那么查找失败，则返回false。
public boolean contains(E e) {
return contains(e, root);
}
private boolean contains(E e, BinaryTreeNode<E> root) {
if (root == null) {
return false;
}
int i = compare(e, root.data);
if (i > 0) {
return contains(e, root.right);
} else if (i < 0) {
return contains(e, root.left);
} else {
return true;
}
}
2.3 插入的方法
有了二叉排序树的查找函数，那么所谓的二叉排序树的插入，其实也就是将关键字放到树中的合适位置而已，插入操作就好像在调用查找的操作，如果找到了那么什么都不做，返回false，如果没找到，则将要插入的元素插入到遍历的路径的最后一点上：
- 若二叉树为空。则单独生成根节点，返回true。
- 执行查找算法，找出被插节点的父亲节点。
- 判断被插节点是其父亲节点的左、右儿子。将被插节点作为叶子节点插入，返回true。如果原节点存在那么什么都不做，返回false。注意：新插入的节点总是叶子节点。
public void insert(E e) {
//返回root,但此时新的节点可能已经被插入进去了
root = insert(e, root);
}
public void insert(E[] es) {
//返回root,但此时新的节点可能已经被插入进去了
for (E e : es) {
root = insert(e, root);
}
}
private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {
if (root == null) {
size++;
return new BinaryTreeNode<>(e);
}
int i = compare(e, root.data);
if (i > 0) {
//重新赋值
root.right = insert(e, root.right);
} else if (i < 0) {
//重新赋值
root.left = insert(e, root.left);
} else {
}
//没查询到最底层,则返回该节点
return root;
}
2.3.1 测试
现在我们想要构建如下一颗排序二叉树：
首先要插入根节点47，然后是第二层的节点16、73，然后是第三层的节点1、24、59、88，然后是第四层的节点20、35、62、77。每一层内部节点的顺序可以不一致，但是每一层之间的大顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出，但是树的结构不能保证。
public class BinarySearchTreeTest {
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
@Test
public void insert() {
//首先要插入根节点47，然后是第二层的节点16,73，然后是第三层的节点1,24,59,88，然后是第四层的节点20,35,62,77。
// 每一层内部节点的顺序可以不一致，但是每一层之间的打顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。
Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
binarySearchTree.insert(es);
//中序遍历输出
System.out.println(binarySearchTree.toInorderTraversalString());
//查找某个数据是否存在
System.out.println(binarySearchTree.contains(1));
System.out.println(binarySearchTree.contains(2));
}
}
在System.out处打上断点，Debug，可以看到树结构和我们预想的一致，如果改变层间的大顺序，那么使用Debug会发现树结构不如预期。
2.4 查找最大值和最小值
很简单，最左边的节点一定是最小的，最右边的节点一定是最大的。因此查找最小的节点只需要向左递归查找，查找最大的节点只需要向右递归查找。
private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) {
if (root == null) {
return null;
} else if (root.left == null) {
return root;
}
return findMin(root.left);
}
private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) {
if (root == null) {
return null;
} else if (root.right == null) {
return root;
}
return findMax(root.right);
}
2.5 删除的方法
对于二叉排序树的删除，就不是那么容易，我们不能因为删除了节点，而让这棵树变得不满足二叉排序树的特性，所以删除需要考虑多种情况。一共有三种情况需要考虑：
如果查找到的将要被删除的节点没有子节点，那么很简单，直接删除父节点对于该节点的引用即可，如下图的红色节点：
例如，删除20之后：
如果查找到的将要被删除的节点具有一个子节点，那么也很简单，直接绕过该节点将原本父节点对于该节点的引用指向该节点的子节点即可，如下图的红色节点：
例如，删除59之后：
如果查找到的将要被删除的节点具有两个子节点，那么就比较麻烦了，如下图的红色节点：
比如我们需要删除73，那么我们就必须要找出一个已存在的能够替代73的节点，然后删除该节点。实际上该73节点的左子树的最大节点62和右子树的最小节点77都能够替代73节点，即它们正好是二叉排序树中比它小或比它大的最接近73的两个数。
一般我们选择一种方式即可，我们这次使用右子树的最小节点替代要删除的节点，使用77替代73之后的结构如下：
完整的代码如下：
public void delete(E e) {
//返回root,但此时可能有一个节点已经被删除了
root = delete(e, root);
}
private BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) {
if (root == null) {
return null;
}
int i = compare(e, root.data);
if (i > 0) {
//从新赋值
root.right = delete(e, root.right);
} else if (i < 0) {
//从新赋值
root.left = delete(e, root.left);
} else {
if (root.left != null && root.right != null) {
//root.data = findMin(root.right).data;
//root.right = delete(root.data, root.right);
root.data = findAndDeleteMin(root.right, root);
size--;
} else {
root = (root.left != null) ? root.left : root.right;
size--;
}
}
//没查询到最底层,则返回该节点
return root;
}
private E findAndDeleteMin(BinaryTreeNode<E> root, BinaryTreeNode<E> parent) {
//如果节点为null，返回
if (root == null) {
return null;
} else if (root.left == null) {
//如果该节点是父节点的右子节点,说明还没进行递归或者第一次递归就找到了最小节点.
//那么此时,应该让该节点的父节点的右子节点指向该节点的右子节点,并返回该节点的数据，该节点由于没有了强引用，会被GC删除
if (root == parent.right) {
parent.right = root.right;
} else {
//如果该节点不是父节点的右子节点，说明进行了多次递归。
//那么此时,应该让该节点的父节点的左子节点指向该节点的右子节点,并返回该节点的数据，该节点由于没有了强引用，会被GC删除
parent.left = root.right;
}
//返回最小节点的数据
return root.data;
}
//递归调用,注意此时是往左查找
return findAndDeleteMin(root.left, root);
}
2.5.1 测试
public class BinarySearchTreeTest {
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
@Test
public void test() {
//首先要插入根节点47，然后是第二层的节点16,73，然后是第三层的节点1,24,59,88，然后是第四层的节点20,35,62,77。
// 每一层内部节点的顺序可以不一致，但是每一层之间的打顺序一定要保持一致，否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。
Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
binarySearchTree.insert(es);
//中序遍历输出
System.out.println(binarySearchTree.toInorderTraversalString());
//查找是否存在
System.out.println(binarySearchTree.contains(1));
System.out.println(binarySearchTree.contains(2));
//移除
binarySearchTree.delete(73);
//中序遍历输出
System.out.println(binarySearchTree.toInorderTraversalString());
}
}
3 二叉排序树的总结
总之，二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。
插入删除的时间性能比较好。而对于二叉排序树的查找，走的就是从根节点到要查找的节点的路径，其比较次数等于给定值的节点在二叉排序树的层数。极端情况，最少为1次，即根节点就是要找的节点，最多也不会超过树的深度。也就是说，二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于，二叉排序树的形状是不确定的。
例如{47, 16, 73, 1, 24, 59, 88}这样的数组，我们可以构建下图左的二叉排序树。但如果数组元素的次序是从小到大有序，如{1, 16, 24, 47, 59, 73, 88}，则二叉排序树就成了极端的右斜树，注意它依然是一棵二叉排序树，如下图右。此时，同样是查找节点88，左图只需要3次比较，而右图就需要7次比较才可以得到结果，二者差异很大。
也就是说，我们希望二叉排序树是比较平衡的，即其深度与完全二叉树相同，均为|log2n+1|(|x|表示不大于x的最大整数)，那么查找的时间复杂也就为O(logn)，近似于折半查找，事实上，上图的左图也不够平衡，明显的左重右轻。而极端情况下的右图,则完全退化成为链表，查找的时间复杂度为O(n)，这等同于顺序查找。
因此，如果我们希望对一个集合按二叉排序树查找，最好是把它构建成一棵平衡的二叉排序树，防止极端情况的发生。这样我们就引申出另一个问题，如何让二叉排序树平衡的问题。关于这个问题，在后续的平衡二叉树（AVL树)的部分将会详细解释！
以上就是Java数据结构之二叉排序树的实现的详细内容，更多关于Java二叉排序树的资料请关注编程网其它相关文章！
