代码
public class BinarySearchTree<Data extends Comparable> {
// 根结点
private Node root;
// 树中结点的个数
private int size;
public class Node {
// 数据
public Data data;
// 父结点
public Node parent;
// 左子结点
public Node left;
// 右子结点
public Node right;
public Node(Data data, Node parent, Node left, Node right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", parent=" + (parent != null ? parent.data : null) +
", left=" + (left != null ? left.data : null) +
", right=" + (right != null ? right.data : null) +
'}';
}
}
/**
* 查询结点个数
*
* @return
*/
public int size() {
return size;
}
/**
* 向树中插入新元素
*
* @param data
* @return
*/
public Node insert(Data data) {
if (data == null) {
return null;
}
boolean onLeft = false;
Node node = root, tempNode = null;
while (node != null) {
tempNode = node;
int comp = data.compareTo(node.data);
if (comp == 0) {
// 若data等于结点的数据，则覆盖结点的数据
node.data = data;
return node;
}
// 若data小于结点的数据，则继续遍历左子结点，否则遍历右子结点
node = comp < 0 ? node.left : node.right;
onLeft = comp < 0;
}
Node newNode = new Node(data, tempNode, null, null);
// 为空说明是个空树
if (tempNode == null) {
root = newNode;
} else if (onLeft) {
tempNode.left = newNode;
} else {
tempNode.right = newNode;
}
size++;
return node;
}
/**
* 删除结点
*/
public void delete(Data data) {
// 查找要删除的结点
Node node = search(data);
if (node == null) {
return;
}
// 若node有子结点，需要做下处理
if (node.left == null) {
// 1：若没有左子结点，则直接将右子结点提升到node的位置
transplant(node, node.right);
// 2：若没有右子结点，则直接将左子结点提升到node的位置
} else if (node.right == null) {
transplant(node, node.left);
} else {
// 3：若node的左右子结点都有
// strategy：使用什么策略来补上删掉node后空缺的位置
String strategy = "left";
if (strategy.equals("left")) {
// 用左子节点补
leftPromote(node);
} else {
// 用右子节点补
rightPromote(node);
}
}
size--;
}
/**
* newNode提升到oldNode的位置（建立newNode与oldNode父结点的联系）
*
* @return
*/
private void transplant(Node oldNode, Node newNode) {
if (oldNode.parent == null) {
root = newNode;
} else if (oldNode.parent.left == oldNode) {
oldNode.parent.left = newNode;
} else {
oldNode.parent.right = newNode;
}
if (newNode != null) {
newNode.parent = oldNode.parent;
}
}
private void leftPromote(Node node) {
// 3.1：先查找node的前驱结点predecessor
Node predecessor = maximum(node.left);
// 3.2：若predecessor不是node的子结点
if (predecessor.parent != node) {
// 3.2.1：predecessor的左子结点提升到predecessor的位置
transplant(predecessor, predecessor.left);
// 3.2.2：建立predecessor与node左子结点的联系
predecessor.left = node.left;
predecessor.left.parent = predecessor;
}
// 3.3：predecessor提升到node的位置
transplant(node, predecessor);
// 3.4：建立predecessor与node右子结点的联系
predecessor.right = node.right;
predecessor.right.parent = predecessor;
}
private void rightPromote(Node node) {
// 3.1：先查找node的后继结点successor
Node successor = minimum(node.right);
// 3.2：若successor不是node的子结点
if (successor.parent != node) {
// 3.2.1：successor的右子结点提升到successor的位置
transplant(successor, successor.right);
// 3.2.2：建立successor与node右子结点的联系
successor.right = node.right;
successor.right.parent = successor;
}
// 3.3：successor提升到node的位置
transplant(node, successor);
// 3.4：建立successor与node左子结点的联系
successor.left = node.left;
successor.left.parent = successor;
}
/**
* 查询最小的数据
*
* @return
*/
public Data minimum() {
return root == null ? null : minimum(root).data;
}
private Node minimum(Node node) {
while (node != null && node.left != null) {
node = node.left;
}
return node;
}
/**
* 查询最大的数据
*
* @return
*/
public Data maximum() {
return root == null ? null : maximum(root).data;
}
private Node maximum(Node node) {
while (node != null && node.right != null) {
node = node.right;
}
return node;
}
/**
* 查询指定数据的结点
*
* @return
*/
public Node search(Data data) {
return search(root, data);
}
/**
* 查询指定数据的结点(用迭代实现)
*
* @return
*/
private Node search(Node node, Data data) {
while (node != null && data.compareTo(node.data) != 0) {
if (data.compareTo(node.data) < 0) {
node = node.left;
} else {
node = node.right;
}
}
return node;
}
/**
* 查询指定数据的结点(用递归实现)
*
* @return
*/
private Node search2(Node node, Data data) {
if (node == null || data.compareTo(node.data) == 0) {
return node;
}
if (data.compareTo(node.data) < 0) {
return search2(node.left, data);
} else {
return search2(node.right, data);
}
}
/**
* 先序遍历
*
* @return
*/
public List<Data> preOrderTreeWalk() {
List<Data> list = new ArrayList<>();
preOrderTreeWalk(root, list);
return list;
}
private void preOrderTreeWalk(Node node, List<Data> list) {
if (node == null) {
return;
}
// 记录数据
list.add(node.data);
// 递归左子树
preOrderTreeWalk(node.left, list);
// 递归右子树
preOrderTreeWalk(node.right, list);
}
/**
* 中序遍历
*
* @return
*/
public List<Data> inOrderTreeWalk() {
List<Data> list = new ArrayList<>();
inOrderTreeWalk(root, list);
return list;
}
private void inOrderTreeWalk(Node node, List<Data> list) {
if (node == null) {
return;
}
// 递归左子树
inOrderTreeWalk(node.left, list);
// 记录数据
list.add(node.data);
// 递归右子树
inOrderTreeWalk(node.right, list);
}
/**
* 后序遍历
*
* @return
*/
public List<Data> postOrderTreeWalk() {
List<Data> list = new ArrayList<>();
postOrderTreeWalk(root, list);
return list;
}
private void postOrderTreeWalk(Node node, List<Data> list) {
if (node == null) {
return;
}
// 递归左子树
postOrderTreeWalk(node.left, list);
// 递归右子树
postOrderTreeWalk(node.right, list);
// 记录数据
list.add(node.data);
}
/**
* 层序遍历
*
* @return
*/
public List<Data> layerOrderTreeWalk() {
List<Data> list = new ArrayList<>();
Queue<Node> queue = new ConcurrentLinkedQueue<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
list.add(node.data);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return list;
}
/**
* 最大深度
*
* @return
*/
public int maxDepth() {
return maxDepth(root);
}
private int maxDepth(Node node) {
if (node == null) {
return 0;
}
int max;
int maxL = 0;
int maxR = 0;
if (node.left != null) {
maxL = maxDepth(node.left);
}
if (node.right != null) {
maxR = maxDepth(node.right);
}
max = maxL > maxR ? maxL + 1 : maxR + 1;
return max;
}
}
测试
public static void main(String[] args) {
String[] data = {"H", "E", "C", "G", "F", "B", "A", "D"};
BinarySearchTree<String> tree = new BinarySearchTree<>();
for (String s : data) {
tree.insert(s);
}
System.out.printf("元素数量为：%d\n", tree.size());
System.out.printf("最小值为：%s\n", tree.minimum());
System.out.printf("最大值为：%s\n", tree.maximum());
System.out.printf("最大深度为：%d\n", tree.maxDepth());
System.out.printf("先序遍历结果：%s\n", tree.preOrderTreeWalk());
System.out.printf("中序遍历结果：%s\n", tree.inOrderTreeWalk());
System.out.printf("后序遍历结果：%s\n", tree.postOrderTreeWalk());
System.out.printf("层序遍历结果：%s\n", tree.layerOrderTreeWalk());
String key = "C";
System.out.printf("查询数据 %s：%s\n", key, tree.search(key));
System.out.printf("删除数据 %s\n", key);
tree.delete(key);
System.out.printf("查询数据 %s：%s\n", key, tree.search(key));
System.out.printf("元素数量为：%d\n", tree.size());
System.out.printf("层序遍历结果：%s\n", tree.layerOrderTreeWalk());
}
输出结果：
元素数量为：8
最小值为：A
最大值为：H
最大深度为：5
先序遍历结果：[H, E, C, B, A, D, G, F]
中序遍历结果：[A, B, C, D, E, F, G, H]
后序遍历结果：[A, B, D, C, F, G, E, H]
层序遍历结果：[H, E, C, G, B, D, F, A]
查询数据 C：Node{data=C, parent=E, left=B, right=D}
删除数据 C
查询数据 C：null
元素数量为：7
层序遍历结果：[H, E, B, G, A, D, F]
插入：{"H", "E", "C", "G", "F", "B", "A", "D"}后，结构如下:
删除元素C后，结构如下：
