一、二叉搜索树(Binary Search Tree)
- 任意一个节点的值都
大于
其左子树
所有节点的值。 - 任意一个节点的值都
小于
其右子树
所有节点的值。 - 它的
左右子树
也是一颗二叉搜索树。 - 二叉搜索树存储的元素必须具备
可比较性
。- 比如
int
,double
等。 - 如果是自定义类型,需要指定比较方式。
- 不允许为
null
。
- 比如
二、二叉搜索树接口设计
public class BinarySearchTree<E>{
private int size; // 元素的个数
private Node<E> root; // 根节点
private Comparator<E> comparator; // 比较器
// 元素的数量
public int size()
// 是否为空
public boolean isEmpty()
// 清空所有元素
public void clear()
// 添加元素
public void add(E element)
// 删除元素
public void remove(E element)
// 是否包含某元素
public boolean contains(E element)
}
三、二叉搜索树的实现
1、构造函数
- 如果二叉树存储的是
自定义类型
,需要传入一个比较器
,负责两个节点的大小。 - 在
添加元素
操作时,会调用compare
私有函数。
public class BinarySearchTree<E> {
// 比较器
private Comparator<E> comparator;
// 便利构造器
public BinarySearchTree() {
this(null);
}
// 构造函数
public BinarySearchTree(Comparator<E> comparator) {
this.comparator = comparator;
}
/**
* @return 返回值等于0,代表e1和e2相等;返回值大于0,代表e1大于e2;返回值小于于0,代表e1小于e2
*/
private int compare(E e1, E e2) {
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<E>)e1).compareTo(e2);
}
}
2、节点
- 二叉树的元素是存放在
节点
中的,所以需要创建私有节点
类。 - 节点还需记录自己的
左节点
,右节点
,父节点
。
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;
}
}
3、添加元素
- 首先找到父节点
parent
,然后创建新节点node
,最后比较parent
和node
的大小。 - 如果
node
小于parent
,将parent.left
赋值给parent
。 - 如果
node
大于parent
,将parent.right
赋值给parent
。 - 循环比较操作,直到
parent.left
或parent.right
为空,将node
赋值给parent.left
或parent.right
即可。 - 添加元素前,首先需要检查
节点
的值是否为空
。
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
- 另外,还需要特殊处理添加元素到
首节点
。
public void add(E element) {
// 判断节点的值是否为空。
elementNotNullCheck(element);
// 添加第一个节点
if (root == null) {
root = new Node<>(element, null);
size++;
return;
}
// 添加的不是第一个节点
Node<E> parent = root;
Node<E> node = root;
// 比较结果
int cmp = 0;
while (node != null) {
// 在之前定义的比较函数
cmp = compare(element, node.element);
//保存node的父节点
parent = node;
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++;
}
4、删除元素
- tips:删除元素会使用
前驱
,后继
的知识,可以先阅读:五、二叉搜索树(Binary Search Tree)的前驱和后继
- 删除节点分为
删除叶子节点
,删除度为1的节点
,删除度为2的节点
。 删除叶子节点
,直接删除
即可。- 如果
node == node.parent.left
node.parent.left = null
- 如果
node == node.parent.right
node.parent.right = null
- 如果
node.parent == null
root = null
- 如果
删除度为1的节点
,用子节点替代
原节点的位置。child = node.left
或者child = node.right
- 用
child
替代node
的位置。 - 如果node是左子节点:
child.parent = node.parent
node.parent.left = child
- 如果node是右子节点:
child.parent = node.parent
node.parent.right = child
- 如果node是根节点:
root = child
- 用
删除度为2的节点
,先用前驱或后继节点的值覆盖
原节点的值,然后删除
相应的前驱或者后继节点。(如果这个节点的度为2,那么它的前驱,后继节点的度只能是1和0)
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;
}
}
}
四、二叉搜索树的遍历
- 根据节点访问顺序的不同,二叉树的常见遍历方法有4种。
- 所谓前中后序遍历,指的是
根节点
遍历顺序。
1、前序遍历
- 访问顺序:
根节点
->前序遍历左子树
->前序遍历右子树
// 递归实现前序遍历
private void preorderTraversal(Node<E> node) {
// 退出条件
if (node == null) return;
// 打印节点值
System.out.println(node.element);
// 前序遍历左子树
reorderTraversal(node.left);
// 前序遍历右子树
preorderTraversal(node.right);
}
2、中序遍历
- 当需要按
升序
或降序
获取节点时,使用中序遍历
。 - 访问顺序:
中序遍历左子树
->根节点
->中序遍历右子树
- 遍历结果:
1、2、3、4、5、7、8、9、10、11、12
- 如果是一颗
二叉搜索树
,遍历的结果按从小到大
排序。 - 另一种访问顺序:
中序遍右左子树
->根节点
->中序遍历左子树
- 遍历结果:
12、11、10、9、8、7、5、4、3、2、1
- 二叉搜索树的
中序遍历
结果是升序
或降序
的。
// 递归实现中序遍历
private void inorderTraversal(Node<E> node) {
// 退出条件
if (node == null) return;
// 中序遍历左子树
inorderTraversal(node.left);
// 打印节点值
System.out.println(node.element);
// 中序遍历右子树
inorderTraversal(node.right);
}
3、后序遍历
- 当需要
先子后父
操作时,可以使用后序遍历
。 - 访问顺序:
后序遍历左子树
->后序遍历右子树
->根节点
// 递归实现后序遍历
private void postorderTraversal(Node<E> node) {
// 退出条件
if (node == null) return;
// 后序遍历左子树
postorderTraversal(node.left);
// 后序遍历右子树
postorderTraversal(node.right);
// 打印节点值
System.out.println(node.element);
}
4、层序遍历
-
需要
计算二叉树高度
或判断是否为完全二叉树
时,可使用层序遍历
。 -
访问顺序:
从上到下
,从左到右
依次访问节点。 -
遍历思路:
- 使用
队列
存储节点。 - 将
根节点
入队列。 - 将队列
头节点
A出队列,进行访问。 - 将节点A的
左子节点
入队列。 - 将节点A的
右子节点
入队列。 - 循环执行
2-4
步骤。
- 使用
public void levelOrderTranversal() {
// 如果根节点为空,直接返回
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);
}
}
}
五、二叉搜索的前驱和后继
1、前驱节点(predecessor)
- 中序遍历时的前一个节点。
- 如果是二叉搜索树,前驱节点就是前一个比它小的节点。
- 寻找前驱节点分三种情况:
- 左子树不为空
- 举例:
6,13,8
predecessor = node.left.right.right.right...
- 终结条件:
right = null
- 举例:
- 左子树为空,父节点不为空
- 举例:
7,11,9,1
predecessor = node.parent.parent.parent...
- 终结条件:
node
在parent
的右子树
中。
- 举例:
- 左子树为空且父节点为空
- 那就没有前驱节点
- 举例:没有
左子树
的根节点。
protected Node<E> predecessor(Node<E> node) {
if (node == null) return null;
// 前驱节点在左子树当中(left.right.right.right....)
Node<E> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// node.parent == null
// node == node.parent.right
return node.parent;
}
2、后继节点(successor)
- 中序遍历时的后一个节点。
- 如果是二叉搜索树,后继节点就是前一个比它大的节点。
- 寻找后继节点分三种情况:
- 右子树不为空
- 举例:
1,4,4
successor = node.right.left.left.left...
- 终结条件:
left = null
- 举例:
- 右子树为空,父节点不为空
- 举例:
7,6,3,11
successor = node.parent.parent.parent...
- 终结条件:
node
在parent
的左子树
中。
- 举例:
- 右子树为空且父节点为空
- 那就没有前驱节点
- 举例:没有
右子树
的根节点。
protected Node<E> successor(Node<E> node) {
if (node == null) return null;
// 前驱节点在左子树当中(right.left.left.left....)
Node<E> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
六、leetcode算法题
1、二叉树的最大深度
- 树的高度 = 子节点高度 + 1
- 子节点高度 = Max(左子树,右子树)
// 递归实现
private int height(Node<E> node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
- 也可以通过
层序遍历
求得最大深度:
public int height() {
if (root == null) return 0;
// 树的高度
int height = 0;
// 存储着每一层的元素数量
int levelSize = 1;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
levelSize--;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
// 意味着即将要访问下一层。
if (levelSize == 0) {
// 此时队列的元素个数即为下一层元素总数。
levelSize = queue.size();
//即将访问下一层,树的高度+1
height++;
}
}
return height;
}
2、二叉树的完全性检验
public boolean isComplete() {
if (root == null) return false;
Queue<Node<E>> queue = new LinkedList<>();
queue.offer(root);
boolean leaf = false;
while (!queue.isEmpty()) {
Node<E> node = queue.poll();
if (leaf && !node.isLeaf()) return false;
if (left != null && right != null) {
queue.offer(node.left);
queue.offer(node.right);
} else if (node.left == null && node.right != null) {
return false;
} else { // 后面遍历的节点都必须是叶子节点
leaf = true;
if (node.left != nill){
queue.offer(node.left)
}
}
}
return true;
}
3、翻转二叉树
- 只要能够遍历二叉树,就可以完成二叉树的翻转。
//前序遍历
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
//翻转
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
//后序遍历
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
invertTree(root.left);
invertTree(root.right);
//翻转
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
//中序遍历
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
invertTree(root.left);
//翻转
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 这里放入的left其实是之前的right
invertTree(root.left);
return root;
}
//层序遍历
public TreeNode invertTree(TreeNode root) {
if (root == null) return root;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
//翻转
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return root;
}
4、根据遍历结果重构二叉树
- 以下结果可以保证重构出
唯一
的一颗二叉树
:- 前序遍历 +
中序
遍历 - 后序遍历 +
中序
遍历
- 前序遍历 +
- 如果是
前序遍历
+后序遍历
:- 如果它是一颗
真二叉树
,结果是唯一的。 - 否则结果不唯一。
- 如果它是一颗
5、删除二叉搜索树中的节点
6、二叉搜索树中的搜索
7、二叉搜索树中的插入操作
8、验证二叉搜索树
9、二叉搜索树的最小绝对差
10、二叉搜索树结点最小距离
11、将有序数组转换为二叉搜索树
12、二叉搜索树的范围和
13、二叉搜索树的最近公共祖先
14、二叉搜索树中第K小的元素
15、二叉搜索树迭代器
16、恢复二叉搜索树
六、二叉搜索树的复杂度
- 如果是按照
7,4,9,2,5,8,11
的顺序添加节点。- 搜索元素复杂度:
O(h) == O(logn)
- 搜索元素复杂度:
- 如果是从小到大添加节点。
- 搜索元素复杂度:
O(h) == O(n)
- 搜索元素复杂度:
- 总结:
- 当n比较大时,两者的性能差异比较大。
- 比如n = 1000000时,二叉搜索树的最低高度是
20
,即最多搜索20
次,而退化成链表的二叉搜索树,最多搜索1000000
次。