基本操作的动画演示
插入（略）
搜索（略）
删除节点
代码
package com.yunche.datastructure;
import java.util.LinkedList;
import java.util.Queue;
/**
* @ClassName: BST
* @Description: 二叉搜索树：每个节点的左子树的值都小于节点的值，每个节点的右子树的值都大于节点的值
* 注：二叉搜索树不一定是完全二叉树
* @author: yunche
* @date: 2018/12/27
*/
public class BST<K extends Comparable<K>, V> {
/**
* 内部私有节点类
*/
private class Node {
private K key;
private V value;
private Node left;
private Node right;
public Node(K key, V value) {
this.key = key;
this.value = value;
left = right = null;
}
}
/**
* 根节点
*/
private Node root;
/**
* 节点个数
*/
private int count;
/**
* 返回节点的个数
*
* @return
*/
public int size() {
return count;
}
/**
* 返回二叉搜索树是否为空
*
* @return
*/
public boolean isEmpty() {
return count == 0;
}
/**
* 构造函数默认构造一棵空的二叉搜索树
*/
public BST() {
root = null;
count = 0;
}
/**
* 向二叉搜索树中插入一个新的(key, value)数据对
*
* @param key
* @param value
*/
public void insert(K key, V value) {
root = insert(root, key, value);
}
/**
* 判断二叉搜索树中是否包含该键
*
* @param key
* @return
*/
public boolean contain(K key) {
return contain(root, key);
}
/**
* 在二叉搜索树中，搜索该键对应的值，并返回，若盖建不存在，返回null
*
* @param key
* @return
*/
public V search(K key) {
return search(root, key);
}
/**
* 二叉搜索树的前序遍历
*/
public void preOrder() {
preOrder(root);
}
/**
* 二分搜索树的中序遍历
*/
public void inOrder() {
inOrder(root);
}
/**
* 二分搜索树的后序遍历
*/
public void postOrder() {
postOrder(root);
}
/**
* 二分搜索树的层序遍历
*/
public void levelOrder() {
//使用LinkedList作为队列
Queue<Node> queue = new LinkedList<Node>();
if (root != null) {
queue.add(root);
}
while (!queue.isEmpty()) {
Node node = queue.remove();
System.out.println(node.key);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
/**
* 返回二分搜索树中最小的键值
*
* @return
*/
public K min() {
if (root != null) {
return min(root).key;
}
return null;
}
/**
* 返回二分搜索树中最大的键值
*
* @return
*/
public K max() {
if (root != null) {
return max(root).key;
}
return null;
}
/**
* 从二分搜索树中删除最小的键值
*/
public void removeMin() {
if (root != null) {
root = removeMin(root);
}
}
/**
* 从二分搜索树中删除最大的键值
*/
public void removeMax() {
if (root != null) {
root = removeMax(root);
}
}
/**
* 删除指定键的节点
*
* @param key
*/
public void remove(K key) {
root = remove(key, root);
}
/**
* @param node 该插入的节点位置
* @param key
* @param value
* @return 返回插入后的新节点
*/
private Node insert(Node node, K key, V value) {
//递归边界
if (node == null) {
count++;
return new Node(key, value);
}
if (node.key.compareTo(key) == 0) {
node.value = value;
} else if (key.compareTo(node.key) < 0) {
node.left = insert(node.left, key, value);
} else {
node.right = insert(node.right, key, value);
}
return node;
}
/**
* 递归contain算法，返回在以node为根节点的树中是否存在该键
*
* @param node
* @param key
* @return
*/
private boolean contain(Node node, K key) {
//递归边界
if (node == null) {
return false;
}
if (key.compareTo(node.key) == 0) {
return true;
} else if (key.compareTo(node.key) < 0) {
return contain(node.left, key);
} else {
return contain(node.right, key);
}
}
/**
* 递归search算法
*
* @param node 待搜索树的根节点
* @param key 待搜索的键
* @return
*/
private V search(Node node, K key) {
//递归边界
if (node == null) {
return null;
}
if (key.compareTo(node.key) == 0) {
return node.value;
} else if (key.compareTo(node.key) < 0) {
return search(node.left, key);
} else {
return search(node.right, key);
}
}
/**
* 将以node为根节点的树进行先序遍历,递归算法
*
* @param node
*/
private void preOrder(Node node) {
//递归边界
if (node == null) {
return;
}
System.out.println(node.key);
preOrder(node.left);
preOrder(node.right);
}
/**
* 将以node为根节点的树进行中序遍历,递归算法
*
* @param node
*/
private void inOrder(Node node) {
//递归边界
if (node == null) {
return;
}
inOrder(node.left);
System.out.println(node.key);
inOrder(node.right);
}
/**
* 将以node为根节点的树进行后序遍历,递归算法
*
* @param node
*/
private void postOrder(Node node) {
//递归边界
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.key);
}
/**
* 返回最小键值的节点，递归算法
*
* @param node 待搜索树的根节点
* @return
*/
private Node min(Node node) {
//递归边界
if (node.left == null) {
return node;
}
return min(node.left);
}
/**
* 返回最大键值的节点，递归算法
*
* @param node 待搜索树的根节点
* @return
*/
private Node max(Node node) {
//递归边界
if (node.right == null) {
return node;
}
return max(node.right);
}
/**
* 删除最小键值节点 递归算法
*
* @param node 最小键值所在树的根节点
* @return 返回删除节点后新的二分搜索树的根
*/
private Node removeMin(Node node) {
//递归边界
if (node.left == null) {
Node childRight = node.right;
node.right = null;
count--;
return childRight;
}
node.left = removeMin(node.left);
return node;
}
/**
* 删除最大键值节点 递归算法
*
* @param node 最大键值所在树的根节点
* @return 返回删除节点后新的二分搜索树的根
*/
private Node removeMax(Node node) {
//递归边界
if (node.right == null) {
Node childLeft = node.left;
node.left = null;
count--;
return childLeft;
}
node.right = removeMax(node.right);
return node;
}
/**
* 删除指定键值对应的节点，并返回删除后新的根节点. 递归算法
*
* @param key 要删除的键值
* @param node 删除键值的节点位于以该节点为根的树里
* @return 删除后子树新的根节点.
*/
private Node remove(K key, Node node) {
//递归边界
if (node == null) {
return null;
}
if (key.compareTo(node.key) == 0) {
//将该节点右子树中的最小键值的节点放在现在节点的位置
//并使该位置（删除节点的位置）上的新节点的左孩子指向原该位置上原来节点的左孩子
//并使该位置（删除节点的位置）上的新节点的右孩子指向原该位置上原来节点的右孩子
if (node.right == null) {
Node leftNode = node.left;
node = null;
count--;
return leftNode;
}
Node successor = min(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node = null;
return successor;
} else if (key.compareTo(node.key) < 0) {
node.left = remove(key, node.left);
} else {
node.right = remove(key, node.right);
}
return node;
}
public static void main(String[] args) {
BST<Integer, Integer> bst = new BST<Integer, Integer>();
// 取n个取值范围在[0...m)的随机整数放进二分搜索树中
int N = 10;
int M = 100;
for (int i = 0; i < N; i++) {
Integer key = new Integer((int) (Math.random() * M));
// 为了后续测试方便,这里value值取和key值一样
bst.insert(key, key);
System.out.print(key + " ");
}
System.out.println();
// 测试二分搜索树的size()
System.out.println("size: " + bst.size());
System.out.println();
// //若要测试，取消该代码片段注释即可
// //********测试遍历(前中后) 和层序遍历开始********//
// // 测试二分搜索树的前序遍历 preOrder
// System.out.println("preOrder: ");
// bst.preOrder();
// System.out.println();
//
// // 测试二分搜索树的中序遍历 inOrder
// System.out.println("inOrder: ");
// bst.inOrder();
// System.out.println();
//
// // 测试二分搜索树的后序遍历 postOrder
// System.out.println("postOrder: ");
// bst.postOrder();
// System.out.println();
// //********测试插入、遍历(前中后)和层序遍历 结束**********//
//
//
// // 测试二分搜索树的层序遍历 levelOrder
// System.out.println("levelOrder: ");
// bst.levelOrder();
// System.out.println();
//********测试遍历(前中后) 和层序遍历结束*******//
// //*****测试搜索最小、最大键值 开始**********
// System.out.println("min: " + bst.min());
// System.out.println("max: " + bst.max());
// //*****测试搜索最小、最大键值 结束**********
// //******* 测试 removeMin 和 removeMax开始
// // 输出的元素应该是从小到大排列的
// System.out.println("Test removeMin: ");
// while( !bst.isEmpty() ){
// System.out.print("min: " + bst.min() + " , ");
// bst.removeMin();
// System.out.println("After removeMin, size = " + bst.size() );
// }
// System.out.println();
//
//
// for(int i = 0 ; i < N ; i ++){
// Integer key = new Integer((int)(Math.random()*M));
// // 为了后续测试方便,这里value值取和key值一样
// bst.insert(key, key);
// }
// // 注意, 由于随机生成的数据有重复, 所以bst中的数据数量大概率是小于n的
//
// // 测试 removeMax
// // 输出的元素应该是从大到小排列的
// System.out.println("Test removeMax: ");
// while( !bst.isEmpty() ){
// System.out.print("max: " + bst.max() + " , ");
// bst.removeMax();
// System.out.println("After removeMax, size = " + bst.size() );
// }
// //******* 测试 removeMin 和 removeMax结束
// //******测试 remove 开始
// BST<Integer, Integer> bstDelete = new BST<Integer, Integer>();
// bstDelete.insert(2, 2);
// bstDelete.insert(1, 1);
// bstDelete.insert(3, 3);
// bstDelete.insert(4, 4);
// bstDelete.insert(0, 0);
// bstDelete.remove(1);
// System.out.println("levelOrder: ");
// bstDelete.levelOrder();
// System.out.println("inOrder: ");
// bstDelete.inOrder();
// System.out.println();
// //***测试remove 结束
}
}