数据结构与算法笔记目录： 《恋上数据结构》 笔记目录想加深 Java 基础推荐看这个： Java 强化笔记目录
我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note
思考：在 n 个动态的整数中搜索某个整数？（查看其是否存在）
- 假设使用动态数组存放元素，从第 0 个位置开始遍历搜索；
平均时间复杂度: $o(n)$
- 如果维护一个有序的动态数组，使用二分搜索；
最坏时间复杂度:$o(logn)$、但是添加、删除的平均时间复杂度是$o(n)$
- 使用二叉搜索树；
添加、删除、搜索的最坏时间复杂度均可优化至:$o(logn)$
二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST
- 又被称为：二叉查找树、二叉排序树
- 任意一个节点的值都大于其左子树所有节点的值
- 任意一个节点的值都小于其右子树所有节点的值
- 它的左右子树也是一棵二又搜索树
二叉搜索树可以大大提高搜索数据的效率；
二叉搜索树存储的元素必须具备可比较性：
- 比如
int、double等 - 如果是自定义类型，需要指定比较方式
- 不允许为
null
注意：对于我们现在使用的二叉树来说，它的元素没有索引的概念
BST 接口设计
我们实现的 二叉搜索树 需要继承前面实现的 通用二叉树；
具体可以查看：《恋上数据结构第1季》二叉树代码实现
由于 BST 继承 BinaryTree，有的方法已经在 BinaryTree 中实现了，无需再次实现。
int size() // 元素的数量
boolean isEmpty() // 是否为空
void clear() // 清空所有元素
void add (E element) // 添加元素
void remove (E element) // 删除元素
boolean contains (E element) // 是否包含某元素BST 基础
由于二叉搜索树的节点必须具有可比较性，元素的比较方案设计：
- 允许外界传入一个
Comparator自定义比较方案 - 如果没有传入
Comparator，强制认定元素实现了Comparable接口
import java.util.Comparator;
/**
* 二叉搜索树
*/
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {
// 比较器，根据传入的比较器实现 compareTo() 方法
private Comparator<E> comparator;
public BST(Comparator<E> comparator){ // 可以传一个比较器
this.comparator = comparator;
}
public BST(){ // 不传比较器，相当于传入一个 null
this(null); //
}
// 根据元素值获取节点元素
private Node<E> node(E element){
elementNotNullCheck(element);
Node<E> node = root;
while(node != null){
int cmp = compareTo(element, node.element);
if(cmp < 0){
node = node.left;
}else if (cmp > 0){
node = node.right;
}else{ // cmp == 0
return node;
}
}
return null;
}
/**
* 是否包含某元素
*/
public boolean contains(E element) {
return node(element) != null;
}
// 节点元素比较
private int compareTo(E e1, E e2) {
if (comparator != null) { // 传入比较器则通过比较器比较
return comparator.compare(e1, e2);
}
// 没传比较器，元素内部必须自行实现了 Comparable 接口
return ((Comparable<E>)e1).compareTo(e2);
}
// 检测传入的节点是否为空
private void elementNotNullCheck(E element) {
if (element == null) { // 不能传入空节点
throw new IllegalArgumentException("element must not null");
}
}
}添加元素: add()
/**
* 添加元素
*/
public void add(E element) {
elementNotNullCheck(element); // 不能传入空节点
// 传入第一个节点, 若根节点为null, 则该节点为根节点
if (root == null) {
root = new Node<>(element, null);
size++;
return;
}
// 添加的不是第一个节点, 找到父节点
Node<E> node = root;
Node<E> parent = root;
int cmp = 0;
while (node != null) {
parent = node; // 父节点
// 比较【传入节点的元素值】与【父节点的元素值】
cmp = compareTo(element, node.element);
if (cmp > 0) { // 传入节点比父节点要大, 往右
node = node.right;
} else if (cmp < 0) { // 传入节点比父节点要小, 往左
node = node.left;
} else { // 相等, 最好是覆盖掉, 也可以采取其他操作, 看业务需求
node.element = element;
return;
}
}
// 上面只是找到了要添加位置的父节点, 下面要将元素添加进去
Node<E> newNode = new Node<>(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
}删除元素: remove()
删除节点 – 叶子节点
叶子节点直接删除即可；
删除节点 – 度为1的节点
删除度为1的节点：用子节点替代原节点的位置；
- 如果要删除的节点不是根节点：
- 如果要删除的节点是根节点：
删除节点 – 度为2的节点
/**
* 根据传入的值删除元素
*/
public void remove(E element) {
remove(node(element));
}
// 根据节点删除元素
private void remove(Node<E> node) {
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<E> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
}
}
// 根据元素值获取节点元素
private Node<E> node(E element){
elementNotNullCheck(element);
Node<E> node = root;
while(node != null){
int cmp = compareTo(element, node.element);
if(cmp < 0){
node = node.left;
}else if (cmp > 0){
node = node.right;
}else{ // cmp == 0
return node;
}
}
return null;
}BST 完整源码
package com.mj.tree;
import java.util.Comparator;
/**
* 二叉搜索树
*/
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> { // 继承通用二叉树类
// 比较器，根据传入的比较器实现 compareTo() 方法
private Comparator<E> comparator;
public BST(Comparator<E> comparator) { // 可以传一个比较器
this.comparator = comparator;
}
public BST() { // 不传比较器，相当于传入一个 null
this(null); //
}
/**
* 是否包含某元素
*/
public boolean contains(E element) {
return node(element) != null;
}
/**
* 添加元素
*/
public void add(E element) {
elementNotNullCheck(element); // 不能传入空节点
// 传入第一个节点, 若根节点为null, 则该节点为根节点
if (root == null) {
root = new Node<>(element, null);
size++;
return;
}
// 添加的不是第一个节点, 找到父节点
Node<E> node = root;
Node<E> parent = root;
int cmp = 0;
while (node != null) {
parent = node; // 父节点
// 比较【传入节点的元素值】与【父节点的元素值】
cmp = compareTo(element, node.element);
if (cmp > 0) { // 传入节点比父节点要大, 往右
node = node.right;
} else if (cmp < 0) { // 传入节点比父节点要小, 往左
node = node.left;
} else { // 相等, 最好是覆盖掉, 也可以采取其他操作, 看业务需求
node.element = element;
return;
}
}
// 上面只是找到了要添加位置的父节点, 下面要将元素添加进去
Node<E> newNode = new Node<>(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
}
/**
* 根据传入的值删除元素
*/
public void remove(E element) {
remove(node(element));
}
// 根据节点删除元素
private void remove(Node<E> node) {
if (node == null) return;
size--;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<E> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.element = s.element;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<E> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
}
}
// 根据元素值获取节点元素
private Node<E> node(E element) {
elementNotNullCheck(element);
Node<E> node = root;
while (node != null) {
int cmp = compareTo(element, node.element);
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else { // cmp == 0
return node;
}
}
return null;
}
// 节点元素比较
private int compareTo(E e1, E e2) {
if (comparator != null) { // 传入比较器则通过比较器比较
return comparator.compare(e1, e2);
}
// 没传比较器，元素内部必须自行实现了 Comparable 接口
return ((Comparable<E>) e1).compareTo(e2);
}
// 检测传入的节点是否为空
private void elementNotNullCheck(E element) {
if (element == null) { // 不能传入空节点
throw new IllegalArgumentException("element must not null");
}
}
}运行测试
import java.util.Comparator;
import com.mj.BinarySearchTree.Visitor;
import com.mj.file.Files;
import com.mj.printer.BinaryTrees;
public class Main {
public static class PersonComparator implements Comparator<Person> { // 比较器
@Override
public int compare(Person e1, Person e2) {
return e1.getAge() - e2.getAge();
}
}
public static class PersonComparator2 implements Comparator<Person> {
@Override
public int compare(Person e1, Person e2) {
return e2.getAge() - e1.getAge();
}
}
// Integer类型的数据
public static void test1(){
Integer date[] = new Integer[] { 7, 4, 9, 2, 5, 8, 11, 3, 12, 1};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < date.length; i++) {
bst.add(date[i]);
}
BinaryTrees.println(bst);
}
// Person类型的数据
public static void test2(){
// Java，匿名类
BinarySearchTree<Person> bst = new BinarySearchTree<>(new Comparator<Person>() {
@Override
public int compare(Person e1, Person e2) {
return e1.getAge() - e2.getAge();
}
});
Integer date[] = new Integer[] { 7, 4, 9, 2, 5, 8, 11, 3, 12, 1};
for (int i = 0; i < date.length; i++) {
bst.add(new Person(date[i]));
}
BinaryTrees.println(bst);
}
// 保存打印结果
public static void test3(){
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for(int i = 0; i < 40; i++){
bst.add((int)(Math.random()*100));
}
String string = BinaryTrees.printString(bst);
string += "\n";
Files.writeToFile("F:/1.txt", string);
}
// add() 时值相等的处理
public static void test4(){
BinarySearchTree<Person> bst = new BinarySearchTree<>(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() - o2.getAge();
}
});
bst.add(new Person(15, "jack"));
bst.add(new Person(16, "rose"));
bst.add(new Person(10, "jerry"));
bst.add(new Person(10, "kali")); // add()时值相等最好覆盖，否则则不会替换
BinaryTrees.println(bst);
}
// 遍历
public static void test5(){
Integer date[] = new Integer[] { 7, 4, 9, 2, 5, 8, 11, 3, 12, 1};
Person persons[] = new Person[10];
BinarySearchTree<Person> bst = new BinarySearchTree<>(new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o2.getAge() - o1.getAge();
}
});
for(int i = 0; i < persons.length; i++){
persons[i] = new Person(date[i]);
bst.add(persons[i]);
}
BinaryTrees.println(bst);
System.out.print("层次遍历:");
bst.levelOrder(new Visitor<Person>() {
@Override
public boolean visit(Person element) {
System.out.print(element + " ");
return false;
}
});
}
// 访问器遍历
public static void test6(){
Integer date[] = new Integer[] { 7, 4, 9, 2, 5, 8, 11, 3, 12, 1};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < date.length; i++) {
bst.add(date[i]);
}
BinaryTrees.print(bst);
System.out.print("层次遍历：");
bst.levelOrder(new Visitor<Integer>() {
@Override
public boolean visit(Integer element) {
System.out.print(element + " ");
return false;
}
});
System.out.println();
System.out.print("前序遍历：");
bst.preorder(new Visitor<Integer>() {
public boolean visit(Integer element) {
System.out.print(element + " ");
// return element == 2 ? true : false;
return false;
}
});
System.out.println();
System.out.print("中序遍历：");
bst.inorder(new Visitor<Integer>() {
@Override
public boolean visit(Integer element) {
System.out.print(element + " ");
return false;
}
});
System.out.println();
System.out.print("后序遍历：");
bst.postorder(null);
bst.postorder(new Visitor<Integer>() {
@Override
public boolean visit(Integer element) {
System.out.print(element + " ");
return false;
}
});
}
// 高度
public static void test7(){
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for(int i = 0; i < 20; i++){
bst.add((int)(Math.random()*100));
}
BinaryTrees.print(bst);
System.out.println();
// System.out.println(bst.height()1);//递归求高度
System.out.println(bst.height());
}
// 是否是完全二叉树
public static void test8(){
/*
* 7
* 4 8
*1 5
*
*/
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
Integer date[] = new Integer[] { 7, 4, 8, 1, 5};
for (int i = 0; i < date.length; i++) {
bst.add(date[i]);
}
BinaryTrees.println(bst);
System.out.println(bst.isComplete());
}
// 是否包含某个结点
public static void test9(){
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
Integer date[] = new Integer[] { 7, 4, 8, 1, 5};
for (int i = 0; i < date.length; i++) {
bst.add(date[i]);
}
BinaryTrees.println(bst);
System.out.println(bst.contains(6));
}
// 删除节点
public static void test10(){
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
Integer date[] = new Integer[] { 7, 4, 8, 1, 5};
for (int i = 0; i < date.length; i++) {
bst.add(date[i]);
}
BinaryTrees.println(bst);
bst.remove(8);
BinaryTrees.println(bst);
}
public static void main(String[] args) {
// test1();
// test2();
// test3();
// test4();
// test5();
// test6();
// test7();
// test8();
// test9();
// test10();
}
}
