1、思考
- 在n个动态的整数中搜索某个整数？即查看是否存在。
如果使用动态数组存储元素，从第0个元素开始遍历搜索，那么平均时间复杂度为O(n)。
如果动态数组中存储的是有序元素，那么使用二分法查找，最坏时间复杂度为O(logn)。但是添加、删除的平均时间复杂度为O(n)。
- 针对这个需求有没有更好的方案呢？
使用二叉搜索树，添加、删除、搜索的最坏时间复杂度可以优化至O(logn)。
2、二叉搜索树（Binary Search Tree）
二叉搜索树是二叉树的一种，应用比较广泛，又被称为二叉查找树、二叉排序树。
二叉搜索树的特点：
1、任意一个节点的值都大于其左子树所有节点的值。
2、任意一个节点的值都小于其右子树所有节点的值。
3、它的左右子树同样是一个二叉搜索树。
4、二叉搜索树中存储的元素必须具有可比较性。
- a、比如int、double类型数据（其包装类内部已经实现了Comparable接口使其具有可比较性）。如果是自定义的类型，需要自己指定比较方式。
- b、元素不能为null。null不能进行比较。
5、二叉搜索树可以大大提高搜索的效率。
下图中表示的就是一个二叉搜索树：
image.png
2.1、接口设计
//元素的数量
public int size() {}
//元素是否为空
public boolean isEmpty() {}
//清空元素
public void clear() {}
//添加元素
public void add(E element) {}
//删除元素
public void remove(E element) {}
//是否包含某个元素
public boolean contains(E element) {}
注意：对于我们现在使用的二叉树中，并不存在索引的概念。这又是为什么呢？
比如将如下数据添加到二叉搜索树中
8,3,10，1,6,14，4,7,13
效果如下图
image.png
然后我们再添加一个9，此时二叉搜索树如下图
image.png
新添加的元素在第三层，而正常来说应该在最后添加元素的后面，即在最后一层节点13的右边，所以索引对二叉树来说并没有什么意义。
2.2、添加元素add(E element)
添加的步骤：
- 1、找到parent节点。
- 2、新建node节点。
- 3、新建的节点可能在parent的左边，也可能在parent的右边。代码表示为parent.left=node或parent.right=node。
从上可知：一个节点需要包含元素的值、left节点、right节点、parent节点。增加一个内部类：
private static class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
public Node(Node<E> left, E element, Node<E> right) {
this.element = element;
this.left = left;
this.right = right;
}
}
- 1、由于二叉搜索树中的元素不能为null，在添加前需要进行判断。
- 2、添加的第一个节点为根节点root。
- 3、如果添加的不是第一个节点，则需要找到要添加节点的父节点。从根节点开始查找，根据二叉搜索树的特性，如果要添加的节点元素的值大于根节点的值，则在根节点的右子树中去查找。然后再和右子树的根节点进行判断，在右子树的左子树或右子树中去查找，直到节点的left或者right等于null。具体实现如下：
// 添加元素
public void add(E element) {
// 由于二叉搜索树中不能添加null元素，需要进行判断
elementNotNullCheck(element);
// 添加第一个节点
if (root == null) {
root = new Node<>(element, null);
size++;
return;
}
// 不是第一个节点
// 找到parent节点
Node<E> node = root;
Node<E> parent = root;
int cmp = 0;
while (node != null) {
cmp = compare(element, node.element);
parent = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else {
node.element=element;
return;
}
}
// 创建node节点
Node<E> newNode = new Node<>(element, parent);
if (cmp > 0) {
parent.right=newNode;
}else if(cmp<0) {
parent.left=newNode;
}
// paent.left=node或parent.right=node
size++;
}
其中compare()方法我们还没有去实现，下面看下如何实现。
二叉搜索树中可以存入任何类型的元素，比如int，其包装类的内部已经实现了Comparable接口，它是可比较的。如果元素类型为自定义的，比如Person类型的，此时就需要让Person类实现Comparable接口。
public class Person implements Comparable<Person> {
private int age;
public Person(int age) {
this.age = age;
}
public int getAge() {
return age;
}
@Override
public int compareTo(Person person) {
return this.age - person.age;
}
}
但是这样的话，如果我们想修改比较方式，就需要修改Person中compareTo()的具体实现，可是其他地方还想使用Person的原有的比较方式呢？我们可以让外部决定比较方式，具体实现如下：
public BinarySearchTree() {
this(null);
}
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
private int compare(E e1, E e2) {
if (comparator != null)
return comparator.compare(e1, e2);
return ((Comparable<E>) e1).compareTo(e2);
}
注意：如果遇到相同的值，我们这里直接将值进行了覆盖，如果二叉搜索树中传入的基本类型的值，覆盖和不覆盖并没有什么意义，但是如果传入的是自定义类型的话，比如Person，如果传入的两个Person年龄相同，但是其他属性不同的话，建议进行覆盖。
2.3、打印二叉树
工具：打印二叉树
将BinarySearchTree实现接口BinaryTreeInfo，并实现方法
@Override
public Object root() {
return root;
}
@Override
public Object left(Object node) {
return ((Node<E>) node).left;
}
@Override
public Object right(Object node) {
return ((Node<E>) node).right;
}
然后调用BinaryTrees.println(bst)
BinarySearchTree<Person> bst = new BinarySearchTree<Person>();
int[] array = { 8, 3, 10, 1, 6, 14, 4, 7, 13, 9 };
String[] nameArray = { "A", "B", "C", "D", "E", "F", "G", "H", "I", "J" };
for (int i = 0; i < array.length; i++) {
bst.add(new Person(array[i], nameArray[i]));
}
BinaryTrees.println(bst);
效果如下图
image.png
2.4、删除节点
2.4.1、删除叶子节点
删除叶子节点，直接删除即可。
下图中的节点3 5 8 10以及节点7都是叶子节点。
image.png
下面看下如何删除叶子节点：
- 1、node.parent ! = null
如果node==node.parent.left，则node.parent.left==null;
如果node==node.parent.right，则node.parent.right.right=null; - 2、node.parent==null，node是根节点
root=null;
2.4.2、删除度为1的节点
用子节点代替原节点的位置
下图中的**4、9、9 **都是要删除的度为1的节点
image.png
- 1、child是node.left或者child是node.right。
- 2、用child来替代node的位置。
- 3、如果node.parent != null
- 1、如果node是node.parent左子节点
- a、child.parent=node.parent;
- b、node.parent.left = child;
-2 、如果node是node.parent的右子节点
- a、child.parent=node.parent;
- b、node.parent.right=child; - 4、如果node.parent==null，node是根节点
- a、child.parent=null;
- b、root=child;
2.4.3、删除度为2的节点
比如删除下图中节点5
image.png
- 1、先用前驱或者后继节点的值，覆盖要删除的节点的值
- 2、然后再删除相应的前驱或后继节点。
- 3、如果要删除的节点度为2，那么它的前驱或后继节点的度只能为1或0。
所以删除度为2的节点，其实最终删除的是度为1或0的节点。
2.4.4、删除的具体实现
我们知道删除度为2的节点，其实最终会转化成删除度为1的节点或者删除叶子节点，所以为了避免重复判断，可以将删除度为2的节点逻辑写在最前面。
private void remove(Node<E> node) {
if (node == null)
return;
// 删除度为2的节点
if (node.hasTwoChildren()) {
// 找到前驱节点
Node<E> precurNode = precursor(node);
// 用前驱节点的值覆盖要删除节点的值
node.element = precurNode.element;
// 删除前驱节点
node = precurNode;
}
// 删除的node节点的度为1或0
Node<E> child = node.left != null ? node.left : node.right;
if (child != null) { // 度为1的节点
// 使用子节点替代要删除节点的位置
child.parent = node.parent;
if (node.parent == null)
root = child;
else if (node == node.parent.left)
node.parent.left = child;
else if (node == node.parent.right)
node.parent.right = child;
} // 删除叶子节点
else if (node.parent == null)
root = null;
else if (node == node.parent.left)
node.parent.left = null;
else if (node == node.parent.right)
node.parent.right = null;
size--;
}
完整代码如下
public class BinarySearchTree<E> implements BinaryTreeInfo {
private int size;
// 根节点
private Node<E> root;
private Comparator<E> comparator;
public static abstract class Visitor<E> {
public boolean stop;
public abstract boolean visit(E e);
}
public BinarySearchTree() {
this(null);
}
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
// 元素的数量
public int size() {
return size;
}
// 元素是否为空
public boolean isEmpty() {
return size == 0;
}
// 清空元素
public void clear() {
size = 0;
root = null;
}
public void levelorderTraserval() {
if (root == null)
return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
System.out.println(node.element);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
// 添加元素
public void add(E element) {
// 由于二叉搜索树添加的元素不能为null
elementNotNullCheck(element);
// root等于null 第一次添加
if (root == null) {
root = new Node<>(element, null);
size++;
return;
}
// 非第一次添加 元素添加的步骤
// 1、找到要添加节点的parent节点
Node<E> node = root;
Node<E> parent = root;
int cmp = 0;
while (node != null) {
cmp = compare(element, node.element);
parent = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else {
// 当元素的值相等时进行覆盖
node.element = element;
return;
}
}
// 2、创建新的节点
Node<E> newNode = new Node<>(element, parent);
// 3、该节点是parent的左子节点还是右子节点
if (cmp > 0) {
parent.right = newNode;
} else if (cmp < 0) {
parent.left = newNode;
}
size++;
}
public void preorder(Visitor<E> visitor) {
if (visitor == null)
return;
preorder(root, visitor);
// preorder2();
}
// 前序遍历---递归方式
private void preorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop)
return;
visitor.stop = visitor.visit(node.element);
preorder(node.left, visitor);
preorder(node.right, visitor);
}
// 前序遍历---迭代方式：使用栈来实现
/**
* 1、将root入栈 2、弹出栈顶元素 3、将栈顶元素的右子节点入栈 4、将栈顶元素的左子节点入栈 5、栈为空则结束遍历
*/
private void preorder2() {
if (root == null)
return;
Stack<Node<E>> stack = new Stack<>();
Node<E> node = root;
stack.add(node);
while (!stack.isEmpty()) {
node = stack.pop();
System.out.println(node.element);
if (node.right != null)
stack.add(node.right);
if (node.left != null)
stack.add(node.left);
}
}
public void inorder(Visitor<E> visitor) {
if (visitor == null)
return;
inorder(root, visitor);
// inorder2();
}
// 中序遍历--递归方式实现
private void inorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop)
return;
inorder(node.left, visitor);
// 在遍历左子树时visitor.stop可能已经为true，所以需要在此处加上判断
if (visitor.stop)
return;
visitor.stop = visitor.visit(node.element);
inorder(node.right, visitor);
}
/**
* 中序遍历--使用迭代方式实现--使用栈来实现 1、设置node=root 2、进行如下循环操作： 1、如果node！=null a、将node入栈
* b、设置node=node.left 2、如果node==null a、如果栈为空则结束循环 b、将栈顶元素出栈，并赋值给node c、对node进行访问
* d、设置node=node.right
*/
private void inorder2() {
if (root == null)
return;
Stack<Node<E>> stack = new Stack<>();
// 设置node=root
Node<E> node = root;
while (true) {
/**
* 如果node不为空，将node加入到栈中 设置node=node.left
*/
if (node != null) {
stack.add(node);
node = node.left;
} else {
/**
* 如果node==null 此时如果栈为空，则退出循环 将栈顶元素出栈，并赋值给node 访问node 设置node=node.right
*/
if (stack.isEmpty())
break;
node = stack.pop();
System.out.println(node.element);
node = node.right;
}
}
}
// 后序遍历
public void postorder(Visitor<E> visitor) {
if (visitor == null)
return;
postorder(root, visitor);
}
// 递归方式实现后序遍历
private void postorder(Node<E> node, Visitor<E> visitor) {
if (node == null || visitor.stop)
return;
postorder(node.left, visitor);
postorder(node.right, visitor);
if (visitor.stop)
return;
visitor.stop = visitor.visit(node.element);
}
/**
* 后序遍历---使用迭代方式实现
*
*/
private void postorder2() {
}
// 层序遍历
public void levelorder(Visitor<E> visitor) {
if (root == null || visitor == null)
return;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (visitor.visit(node.element))
break;
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
public int height(E element) {
return height(node(element));
// return height2(node(element));
}
// 通过元素查找节点
public Node<E> node(E element) {
if (root == null)
return null;
Node<E> node = root;
int cmp = 0;
while (node != null) {
cmp = compare(element, node.element);
if (cmp == 0)
return node;
if (cmp > 0)
node = node.right;
else
node = node.left;
}
return null;
}
private int height;// 树的高度
private int levelCount = 1;// 一层的元素数量
// 计算二叉树的高度 使用层序遍历的方式
private int height(Node<E> node) {
if (node == null)
return 0;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
Node<E> newNode = queue.poll();
levelCount--;
if (newNode.left != null)
queue.offer(newNode.left);
if (newNode.right != null)
queue.offer(newNode.right);
if (levelCount == 0) {
levelCount = queue.size();
height++;
}
}
return height;
}
private int height2(Node<E> node) {
if (node == null)
return 0;
return 1 + Math.max(height2(node.left), height2(node.right));
}
public boolean isCompleteTree() {
if (root == null)
return false;
boolean leaf = false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (leaf && !node.isLeaf())
return false;
// 如果node.left!=null就入队
if (node.left != null)
queue.offer(node.left);
else { //
if (node.right != null)
return false;
// 和下面叶子节点判断重复，可去掉
// else if (node.right == null)
// leaf = true;
}
if (node.right != null)
queue.offer(node.right);
else {
// if(node.left!=null) {
// leaf = true;
// }else if(node.left==null) { //重复
// leaf = true;
// }
// 上面判断重复,简化为
leaf = true;
}
}
return true;
}
public E precursor(E element) {
Node<E> node = precursor(node(element));
return node == null ? null : node.element;
}
// 获取指定节点的前驱结点
private Node<E> precursor(Node<E> node) {
if (node == null)
return node;
Node<E> leftNode = node.left;
// node.left.right.right....
if (leftNode != null) {
while (leftNode.right != null) {
leftNode = leftNode.right;
}
return leftNode;
}
// node.parent.parent....
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// 走到这里条件 node.parent===null || node == node.parent.right
// 这两种情况下都会返回node.parent
return node.parent;
}
public E successor(E element) {
Node<E> node = successor(node(element));
return node == null ? null : node.element;
}
// 后继节点
private Node<E> successor(Node<E> node) {
if (node == null)
return null;
Node<E> rightNode = node.right;
// node.right.left.left....
if (rightNode != null) {
while (rightNode.left != null) {
rightNode = rightNode.left;
}
return rightNode;
}
// node.parent.parent...
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
private int compare(E e1, E e2) {
if (comparator != null)
return comparator.compare(e1, e2);
return ((Comparable<E>) e1).compareTo(e2);
}
private void elementNotNullCheck(E element) {
if (element == null)
throw new IllegalArgumentException("element must not be null");
}
// 删除元素
public void remove(E element) {
remove(node(element));
}
private void remove(Node<E> node) {
if (node == null)
return;
// 删除度为2的节点
if (node.hasTwoChildren()) {
// 找到前驱节点
Node<E> precurNode = precursor(node);
// 用前驱节点的值覆盖要删除节点的值
node.element = precurNode.element;
// 删除前驱节点
node = precurNode;
}
// 删除的node节点的度为1或0
Node<E> child = node.left != null ? node.left : node.right;
if (child != null) { // 度为1的节点
// 使用子节点替代要删除节点的位置
child.parent = node.parent;
if (node.parent == null)
root = child;
else if (node == node.parent.left)
node.parent.left = child;
else if (node == node.parent.right)
node.parent.right = child;
} // 删除叶子节点
else if (node.parent == null)
root = null;
else if (node == node.parent.left)
node.parent.left = null;
else if (node == node.parent.right)
node.parent.right = null;
size--;
}
// 是否包含某个元素
public boolean contains(E element) {
return node(element) != null;
}
private static class Node<E> {
E element;
Node<E> left;
Node<E> right;
Node<E> parent;
public Node(E element, Node<E> parent) {
this.element = element;
this.parent = parent;
}
public boolean isLeaf() {
return left == null && right == null;
}
public boolean hasTwoChildren() {
return left != null && right != null;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
toString(sb, root, "");
return sb.toString();
}
// 使用前序遍历方式打印二叉树
private void toString(StringBuilder sb, Node<E> node, String prefix) {
if (node == null)
return;
sb.append(prefix).append("【").append(node.element).append("】").append("\n");
toString(sb, node.left, prefix + "〖L〗");
toString(sb, node.right, prefix + "〖R〗");
}
@Override
public Object root() {
return root;
}
@Override
public Object left(Object node) {
// TODO Auto-generated method stub
return ((Node<E>) node).left;
}
@Override
public Object right(Object node) {
// TODO Auto-generated method stub
return ((Node<E>) node).right;
}
@Override
public Object string(Object node) {
// TODO Auto-generated method stub
Node<E> newNode = (Node<E>) node;
return newNode.element + "_p_" + (newNode.parent == null ? "null" : newNode.parent.element);
}
}
