用 Java 手把手写一个“二叉搜索树”,支持泛型
一、二叉搜索树
先说一下二叉树,二叉树是一种至多只有左右两个子结点的树形结构。
二叉搜索树是二叉树的一种,对于任意一个结点 x,其左子树的任一结点的值都不大于 x 的值,其右子树的任一结点的值都不小于 x 的值。
二叉搜索树上的基本操作有 查询 (search)、最小值 (minimum)、最大值 (maximum)、前驱值 (predecessor)、后继值 (successor)、插入 (insert)、删除 (delete) 等等。其花费时间与树的高度成正比。这些操作对于一个有 n 个结点的完全二叉树而言,最坏运行时间为 O(lg n),而链表结构则需花费 O(n) 时间。
二、查询
这里的数据我们使用泛型 T 来表示。T 需要满足一个条件,即它是可比较的,所以泛型 T 需要实现 Comparable 接口。
1. 查找
给出待查询的数据,返回一个指向该数据的结点的对象,若数据不存在于树中,返回 null。
由于二叉搜索树的性质,我们可以从根结点开始查找,如果数据等于结点处的值,则返回该结点,如果小于结点处的值,则我们继续在其左子树中查找,如果大于结点处的值,则我们继续在其右子树中查找。
代码如下:
/**
* @param data 待查找的数据
* @return 返回指向 data 数据的结点对象,不存在时返回 null
*/
public TreeNode<T> get(T data) {
TreeNode<T> current = root;
while (current != null && data.compareTo(current.getData()) != 0) {
if (data.compareTo(current.getData()) < 0) {
current = current.getLeft();
} else {
current = current.getRight();
}
}
return current;
}
2. 最大值和最小值
最大值和最小值总是出现在二叉搜索树的最左边和最右边,所以我们沿着左边或者右边一直遍历下去,直到碰到 null 时停止即可。
最小值代码如下(最大值类似):
/**
* @return 返回最小数据的结点对象
*/
public TreeNode<T> getMin() {
return getMin(root);
}
private TreeNode<T> getMin(TreeNode<T> treeNode) {
while (treeNode.getLeft() != null) {
treeNode = treeNode.getLeft();
}
return treeNode;
}
3. 前驱值和后继值
前驱值即树中比给定数据小的第一个值,后继值即树中比给定数据大的第一个值。
例如查找后继值,分两种情况:第一种是该结点的右子树存在,则后继者一定是在右子树的最左结点处;第二种是该节点的右子树不存在,则需要沿着父结点往上寻找,当某个结点不再是其父结点的右子结点时,其父结点就是我们需要寻找的后继者。
如果你没听懂,那么可以参考下图:
第一种情况:例如查找 6 的后继者,由于 6 这个结点存在右子树,所以后继者即右子树的最左结点,即 9 这个结点。
第二种情况:例如查找 13 的后继者,由于 13 这个结点不存在右子树,所以我们沿着父结点往上寻找,当某个结点不再是其父结点的右子结点时,其父结点就是我们需要寻找的后继者。比如 13 的父结点 7 是一个右子结点,继续往上,父结点 6 是一个左子结点,停止查找,结点 6 的父结点 15 就是我们需要寻找的后继者。
后继值代码如下(前驱值类似):
/**
* @param data 待查找的数据
* @return 返回指向 data 后继者的结点对象
*/
public TreeNode<T> getSuccessor(T data) {
TreeNode<T> current = get(data);
if (current == null) {
return null;
}
// 如果结点右子树非空,则后继者一定在右子树最左结点
if (current.getRight() != null) {
return getMin(current.getRight());
}
// 否则沿上遍历,当 curent不再是parent的右子结点时,后继者一定出现在parent的父节点
TreeNode<T> parent = current.getParent();
while (parent != null && current.isRightChild()) {
current = parent;
parent = parent.getParent();
}
return parent;
}
三、插入
插入操作和搜索操作比较类似,我们也是从根节点开始寻找要插入的位置,如果数据小于结点处的值,则我们继续在其左子树中寻找要插入的位置,如果大于结点处的值,则我们继续在其右子树中寻找要插入的位置,直到碰到 null 为止,此时 null 的位置即是我们需要插入数据的节点位置。
代码如下:
/**
* @param data 待插入的数据
*/
public void insert(T data) {
TreeNode<T> insertNode = new TreeNode<>(data);
TreeNode<T> parent = null;
TreeNode<T> current = root;
while (current != null) { // 先找到要插入的位置
parent = current;
if (data.compareTo(current.getData()) < 0) {
current = current.getLeft();
} else {
current = current.getRight();
}
}
if (parent == null) {
root = insertNode; // tree is empty
} else if (insertNode.getData().compareTo(parent.getData()) < 0) {
parent.setLeft(insertNode);
} else {
parent.setRight(insertNode);
}
}
四、删除
删除操作要麻烦很多,首先大致有三种情况:
- 待删除的节点没有子结点,那么我们直接删掉这个结点即可。
- 待删除的结点只有一个子结点,那么我们直接将子结点替换掉删除节点即可。
- 待删除的结点有两个子结点,那么我们需要先找到待删除结点的后继者,这个后继者又存在两种情况,即:
待删除结点 z 的后继者为 y,则 y 一定是 z 右子树的最小结点。如果 y 是 z 的右子结点,那么直接使用子结点 y 替换 z 即可;如果 y 不是 z 的右子结点,则先用 y 的右子结点 x 替换 y,再用 y 替换 z 即可。
代码如下:
/**
* @param data 待删除的数据
* @return 删除是否成功。当数据不存在树中时删除失败
*/
public boolean delete(T data) {
TreeNode<T> deleteNode = get(data);
if (deleteNode == null) {
return false; // 不存在的结点
}
if (deleteNode.getLeft() == null) {
transplant(deleteNode, deleteNode.getRight());
} else if (deleteNode.getRight() == null) {
transplant(deleteNode, deleteNode.getLeft());
} else { // 存在两个子结点的情况
// 先找到后继者
TreeNode<T> successor = getMin(deleteNode.getRight());
if (successor.getParent() != deleteNode) {
transplant(successor, successor.getRight());
successor.setRight(deleteNode.getRight());
}
transplant(deleteNode, successor);
successor.setLeft(deleteNode.getLeft());
}
return true;
}
/**
* 使用新结点替换旧结点
* @param oldNode 旧结点
* @param newNode 新结点
*/
private void transplant(TreeNode<T> oldNode, TreeNode<T> newNode) {
if (oldNode.getParent() == null) {
root = newNode; // 旧结点是根节点的情况
} else if (oldNode.isLeftChild()) {
oldNode.getParent().setLeft(newNode);
} else {
oldNode.getParent().setRight(newNode);
}
}
五、完整代码
1. TreeNode 结点类
public class TreeNode<T extends Comparable<T>> {
private T data; // 数据必须是可比较的
private TreeNode<T> parent; // 父结点
private TreeNode<T> left; // 左子结点
private TreeNode<T> right; // 右子结点
TreeNode(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public TreeNode<T> getParent() {
return parent;
}
public void setParent(TreeNode<T> parent) {
this.parent = parent;
}
public TreeNode<T> getLeft() {
return left;
}
public void setLeft(TreeNode<T> left) {
this.left = left;
if (this.left != null) {
this.left.parent = this;
}
}
public TreeNode<T> getRight() {
return right;
}
public void setRight(TreeNode<T> right) {
this.right = right;
if (this.right != null) {
this.right.parent = this;
}
}
public boolean isRoot() {
// 是否是根节点
return parent == null;
}
public boolean isLeaf() {
// 是否是叶子节点,即没有子结点
return left == null && right == null;
}
public boolean isLeftChild() {
// 是否是其父结点的左子结点
if (parent == null) {
return false;
}
return this == parent.left;
}
public boolean isRightChild() {
// 是否是其父结点的右子结点
if (parent == null) {
return false;
}
return this == parent.right;
}
@Override
public String toString() {
return "TreeNode [data=" + data +
", parent=" + (parent == null ? null : parent.data) +
", left=" + (left == null ? null : left.data) +
", right=" + (right == null ? null : right.data) + "]";
}
}
2. BinarySearchTree 二叉搜索树类
public class BinarySearchTree<T extends Comparable<T>> {
private TreeNode<T> root;
/**
* 将数组构建为树
* @param datas 输入数据数组
*/
public void buildTree(T[] datas) {
for (int i = 0; i < datas.length; i++) {
insert(datas[i]);
}
}
/**
* @param data 待查找的数据
* @return 返回指向 data 数据的结点对象,不存在时返回 null
*/
public TreeNode<T> get(T data) {
TreeNode<T> current = root;
while (current != null && data.compareTo(current.getData()) != 0) {
if (data.compareTo(current.getData()) < 0) {
current = current.getLeft();
} else {
current = current.getRight();
}
}
return current;
}
/**
* @return 返回最小数据的结点对象
*/
public TreeNode<T> getMin() {
return getMin(root);
}
private TreeNode<T> getMin(TreeNode<T> treeNode) {
while (treeNode.getLeft() != null) {
treeNode = treeNode.getLeft();
}
return treeNode;
}
/**
* @return 返回最大数据的结点对象
*/
public TreeNode<T> getMax() {
return getMax(root);
}
private TreeNode<T> getMax(TreeNode<T> treeNode) {
while (treeNode.getRight() != null) {
treeNode = treeNode.getRight();
}
return treeNode;
}
/**
* @param data 待查找的数据
* @return 返回指向 data 后继者的结点对象
*/
public TreeNode<T> getSuccessor(T data) {
TreeNode<T> current = get(data);
if (current == null) {
return null;
}
// 如果结点右子树非空,则后继者一定在右子树最左结点
if (current.getRight() != null) {
return getMin(current.getRight());
}
// 否则沿上遍历,当 curent不再是parent的右子结点时,后继者一定出现在parent的父节点
TreeNode<T> parent = current.getParent();
while (parent != null && current.isRightChild()) {
current = parent;
parent = parent.getParent();
}
return parent;
}
/**
* @param data 待查找的数据
* @return 返回指向 data 前驱者的结点对象
*/
public TreeNode<T> getPredecessor(T data) {
TreeNode<T> current = get(data);
if (current == null) {
return null;
}
// 如果结点左子树非空,则前驱者一定在左子树最右结点
if (current.getLeft() != null) {
return getMax(current.getLeft());
}
// 否则沿上遍历,当 curent不再是parent的左子结点时,前驱者一定出现在parent的父节点
TreeNode<T> parent = current.getParent();
while (parent != null && current.isLeftChild()) {
current = parent;
parent = parent.getParent();
}
return parent;
}
/**
* @param data 待插入的数据
*/
public void insert(T data) {
TreeNode<T> insertNode = new TreeNode<>(data);
TreeNode<T> parent = null;
TreeNode<T> current = root;
while (current != null) { // 先找到要插入的位置
parent = current;
if (data.compareTo(current.getData()) < 0) {
current = current.getLeft();
} else {
current = current.getRight();
}
}
if (parent == null) {
root = insertNode; // tree is empty
} else if (insertNode.getData().compareTo(parent.getData()) < 0) {
parent.setLeft(insertNode);
} else {
parent.setRight(insertNode);
}
}
/**
* @param data 待删除的数据
* @return 删除是否成功。当数据不存在树中时删除失败
*/
public boolean delete(T data) {
TreeNode<T> deleteNode = get(data);
if (deleteNode == null) {
return false; // 不存在的结点
}
if (deleteNode.getLeft() == null) {
transplant(deleteNode, deleteNode.getRight());
} else if (deleteNode.getRight() == null) {
transplant(deleteNode, deleteNode.getLeft());
} else { // 存在两个子结点的情况
// 先找到后继者
TreeNode<T> successor = getMin(deleteNode.getRight());
if (successor.getParent() != deleteNode) {
transplant(successor, successor.getRight());
successor.setRight(deleteNode.getRight());
}
transplant(deleteNode, successor);
successor.setLeft(deleteNode.getLeft());
}
return true;
}
/**
* 使用新结点替换旧结点
* @param oldNode 旧结点
* @param newNode 新结点
*/
private void transplant(TreeNode<T> oldNode, TreeNode<T> newNode) {
if (oldNode.getParent() == null) {
root = newNode; // 旧结点是根节点的情况
} else if (oldNode.isLeftChild()) {
oldNode.getParent().setLeft(newNode);
} else {
oldNode.getParent().setRight(newNode);
}
}
public void printTree() {
inorderTraversal(root); // 二叉搜索树的中序遍历将会从小到大输出
}
/**
* 中序遍历
* @param root 根结点
*/
public void inorderTraversal(TreeNode<T> root) {
if (root == null) return;
inorderTraversal(root.getLeft());
System.out.print(root.getData() + " ");
inorderTraversal(root.getRight());
}
}
3. 调用场景
public class Main {
public static void main(String[] args) {
BinarySearchTree<Integer> tree = new BinarySearchTree<>();
Integer[] arr = new Integer[] { 15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9 };
tree.buildTree(arr);
System.out.print("二叉搜索数当前状态为:");
tree.printTree();
System.out.println("\n最大值为: " + tree.getMax().getData());
System.out.println("最小值为: " + tree.getMin().getData());
System.out.println("元素 7 的信息为:" + tree.get(7));
System.out.println("树中比 6 小的数为: " + tree.getPredecessor(6).getData());
System.out.println("树中比 13 大的数为: " + tree.getSuccessor(13).getData());
System.out.println("删除 6 元素:" + tree.delete(6));
System.out.print("二叉搜索数当前状态为:");
tree.printTree();
}
}
执行结果:
二叉搜索数当前状态为:2 3 4 6 7 9 13 15 17 18 20
最大值为: 20
最小值为: 2
元素 7 的信息为:TreeNode [data=7, parent=6, left=null, right=13]
树中比 6 小的数为: 4
树中比 13 大的数为: 15
删除 6 元素:true
二叉搜索数当前状态为:2 3 4 7 9 13 15 17 18 20
六、总结
以上,我们已经完成了一个二叉搜索树的基本功能了。但是细心的同学可能已经发现了,我们的二叉搜索树的构建部分极其依赖于插入元素的顺序,虽然大多数情况下树的高度都是接近 lg n 的,但是当插入数据的顺序不理想时,该树将严重失衡。例如依次插入 1,2,3,4,5,6,7,8,9 … 这样依次增大的数据,将导致构建的树高度 h 和结点数 n 相同。而二叉搜索树的操作耗时均和树的高度成正比。
所以,我们可以增加一些机制,使得二叉搜索树是一个平衡二叉树,这样将大大增强二叉搜索树的性能。