思考
◼在 n 个动态的整数中搜索某个整数?(查看其是否存在)
◼假设使用动态数组存放元素，从第 0 个位置开始遍历搜索，平均时间复杂度:O(n)
◼ 如果维护一个有序的动态数组，使用二分搜索，最坏时间复杂度:O(logn)
但是添加、删除的平均时间复杂度是 O(n)
◼ 针对这个需求，有没有更好的方案？
使用二叉搜索树，添加、删除、搜索的最坏时间复杂度均可优化至:O(logn)
二叉搜索树(Binary Search Tree)
◼二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为 BST
又被称为:二叉查找树、二叉排序树
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一棵二叉搜索树
◼ 二叉搜索树可以大大提高搜索数据的效率
◼ 二叉搜索树存储的元素必须具备可比较性
比如 int、double 等
如果是自定义类型，需要指定比较方式
不允许为 null
二叉搜索树的接口设计
◼int size() // 元素的数量
◼boolean isEmpty() // 是否为空
◼void clear() // 清空所有元素
◼void add(E element) // 添加元素
◼void remove(E element) // 删除元素
◼boolean contains(E element)// 是否包含某元素
◼ 需要注意的是
对于我们现在使用的二叉树来说，它的元素没有索引的概念
为什么？
添加节点
◼ 比如添加12、1
◼ 添加步骤
找到父节点 parent
创建新节点 node
parent.left = node 或者 parent.right = node
◼ 遇到值相等的元素该如何处理?
建议覆盖旧的值
元素的比较方案设计
- 允许外界传入一个Comparator自定义比较方案
- 如果没有传入Comparator，强制认定元素实现了Comparable接口
打印二叉树
◼ 工具:https://github.com/CoderMJLee/BinaryTrees
◼ 使用步骤
实现 BinaryTreeInfo 接口
调用打印API
✓ BinaryTrees.println(bst);
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;
do {
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;
}
} while (node != null);
// 看看插入到父节点的哪个位置
Node<E> newNode = new Node<>(element, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
}
// 判空
private void elementNotNullCheck(E element) {
if (element == null) {
throw new IllegalArgumentException("element must not be null");
}
}
/**
* @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);
}
// 添加节点
static void test1() {
Integer data[] = new Integer[] {
7, 4, 9, 2, 5, 8, 11, 3, 12, 1
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
}
static void test2() {
Integer data[] = new Integer[] {
7, 4, 9, 2, 5, 8, 11, 3, 12, 1
};
BinarySearchTree<Person> bst1 = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst1.add(new Person(data[i]));
}
BinaryTrees.println(bst1);
BinarySearchTree<Person> bst2 = new BinarySearchTree<>(new Comparator<Person>() {
public int compare(Person o1, Person o2) {
return o2.getAge() - o1.getAge();
}
});
for (int i = 0; i < data.length; i++) {
bst2.add(new Person(data[i]));
}
BinaryTrees.println(bst2);
}
// 打印器-更多用法
static void test3() {
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < 40; i++) {
bst.add((int)(Math.random() * 100));
}
String str = BinaryTrees.printString(bst);
str += "\n";
Files.writeToFile("F:/1.txt", str, true);
BinaryTrees.println(bst);
}
// 值相等的处理
static void test5() {
BinarySearchTree<Person> bst = new BinarySearchTree<>();
bst.add(new Person(10, "jack"));
bst.add(new Person(12, "rose"));
bst.add(new Person(6, "jim"));
bst.add(new Person(10, "michael"));
BinaryTrees.println(bst);
}
推荐一些神奇的网站
◼ http://520it.com/binarytrees/
◼ http://btv.melezinek.cz/binary-search-tree.html
◼ https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
◼ https://yangez.github.io/btree-js
◼ https://www.codelike.in
二叉树的遍历
◼ 遍历是数据结构中的常见操作
把所有元素都访问一遍
◼ 线性数据结构的遍历比较简单
正序遍历
逆序遍历
◼ 根据节点访问顺序的不同，二叉树的常见遍历方式有4种
前序遍历(Preorder Traversal)
中序遍历(Inorder Traversal)
后序遍历(Postorder Traversal)
层序遍历(Level Order Traversal)
前序遍历(Preorder Traversal) -- 递归
◼ 访问顺序
根节点、前序遍历左子树、前序遍历右子树
7、4、2、1、3、5、9、8、11、10、12
/**
* 前序遍历 -- 递归
*/
public void preorderTraversal() {
preorderTraversal(root);
}
private void preorderTraversal(Node<E> node) {
if (node == null) return;
System.out.println(node.element);
preorderTraversal(node.left);
preorderTraversal(node.right);
}
// 前序遍历(Preorder Traversal) -- 递归
static void test6() {
System.out.println("--------------------------------- 前序遍历(Preorder Traversal) -- 递归");
Integer data[] = new Integer[] {
7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
bst.preorderTraversal();
}
前序遍历 – 非递归
◼ 利用栈实现
- 设置node=root
- 循环执行以下操作
如果 node != null
✓对node 进行访问
✓将node.right 入栈
✓ 设置 node = node.left
如果 node == null
✓ 如果栈为空，结束遍历
✓ 如果栈不为空，弹出栈顶元素并赋值给 node
◼ 利用栈实现
- 将root入栈
- 循环执行以下操作，直到栈为空
弹出栈顶节点 top，进行访问
将 top.right 入栈
将 top.left 入栈
中序遍历(Inorder Traversal)
◼ 访问顺序
中序遍历左子树、根节点、中序遍历右子树
1、2、3、4、5、7、8、9、10、11、12
◼ 如果访问顺序是下面这样呢?
中序遍历右子树、根节点、中序遍历左子树
12、11、10、9、8 、7、5、4、3、2、1
◼ 二叉搜索树的中序遍历结果是升序或者降序的
/**
* 中序遍历
*/
public void inorderTraversal() {
inorderTraversal(root);
}
private void inorderTraversal(Node<E> node) {
if (node == null) return;
// 升序
inorderTraversal(node.left);
System.out.println(node.element);
inorderTraversal(node.right);
// 降序
// inorderTraversal(node.right);
// System.out.println(node.element);
// inorderTraversal(node.left);
}
// 中序遍历(Inorder Traversal)
static void test7() {
Integer data[] = new Integer[] {
7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
bst.inorderTraversal();
}
中序遍历 – 非递归
◼ 利用栈实现
- 设置node=root
- 循环执行以下操作
如果 node != null
✓将node 入栈
✓ 设置 node = node.left
如果 node == null
✓ 如果栈为空，结束遍历
✓ 如果栈不为空，弹出栈顶元素并赋值给 node ➢对node 进行访问
➢设置 node = node.right
后序遍历(Postorder Traversal)
◼ 访问顺序
后序遍历左子树、后序遍历右子树、根节点
1、3、2、5、4、8、10、12、11、9、7
/**
* 后序遍历
*/
public void postorderTraversal() {
postorderTraversal(root);
}
private void postorderTraversal(Node<E> node) {
if (node == null) return;
postorderTraversal(node.left);
postorderTraversal(node.right);
System.out.println(node.element);
}
// 后序遍历(Postorder Traversal)
static void test8() {
System.out.println("--------------------------------- 后序遍历(Postorder Traversal)");
Integer data[] = new Integer[] {
7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
bst.postorderTraversal();
}
后序遍历 – 非递归
◼ 利用栈实现
- 将 root 入栈
- 循环执行以下操作，直到栈为空
如果栈顶节点是叶子节点 或者 上一次访问的节点是栈顶节点的子节点 ✓ 弹出栈顶节点，进行访问
否则
✓ 将栈顶节点的right、left按顺序入栈
层序遍历(Level Order Traversal)
◼ 访问顺序
从上到下、从左到右依次访问每一个节点
7、4、9、2、5、8、11、1、3、10、12
◼ 实现思路:使用队列
- 将根节点入队
- 循环执行以下操作，直到队列为空
将队头节点 A 出队，进行访问
将 A 的左子节点入队
将 A 的右子节点入队
/**
* 层序遍历
*/
public void levelOrderTraversal() {
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);
}
}
}
// 层序遍历(Level Order Traversal)
static void test9() {
System.out.println("--------------------------------- 层序遍历(Level Order Traversal)");
Integer data[] = new Integer[] {
7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
bst.levelOrderTraversal();// 层序遍历
}
思考
◼ 如果允许外界遍历二叉树的元素?你会如何设计接口？
遍历的应用
◼ 前序遍历
树状结构展示(注意左右子树的顺序)
◼ 中序遍历
二叉搜索树的中序遍历按升序或者降序处理节点
◼ 后序遍历
适用于一些先子后父的操作
◼ 层序遍历
计算二叉树的高度
判断一棵树是否为完全二叉树
练习 – 利用前序遍历树状打印二叉树
public String toString() {
StringBuilder sb = new StringBuilder();
toString(root, sb, "");
return sb.toString();
}
private void toString(Node<E> node, StringBuilder sb, String prefix) {
if (node == null) return;
// 前序打印
sb.append(prefix).append(node.element).append("\n");
toString(node.left, sb, prefix + "L---");
toString(node.right, sb, prefix + "R---");
}
// 利用前序遍历树状打印二叉树
static void test() {
Integer data[] = new Integer[] {
7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
System.out.println(bst);
}
练习 – 计算二叉树的高度
◼递归
// 计算二叉树的高度 -- 递归
public int height2() {
return height(root);
}
// 获取某个节点的高度
private int height(Node<E> node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}
// 计算二叉树的高度
static void test13() {
System.out.println("--------------------------------- 计算二叉树的高度");
Integer data[] = new Integer[] {
7, 4, 2, 1, 3, 5, 9, 8, 11, 10, 12
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
System.out.println(bst.height2());// 递归
}
◼迭代
// 计算二叉树的高度 -- 迭代 -- 层序遍历
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();
height++;
}
}
return height;
}
// 计算二叉树的高度 -- 迭代 -- 层序遍历
static void test14() {
System.out.println("--------------------------------- 计算二叉树的高度 -- 迭代 -- 层序遍历");
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < 15; i++) {
bst.add((int)(Math.random() * 100));
}
BinaryTrees.println(bst);// 打印器
System.out.println(bst.height());// 计算二叉树的高度 -- 迭代 -- 层序遍历
}
练习 – 判断一棵树是否为完全二叉树
◼ 如果树为空，返回 false
◼ 如果树不为空，开始层序遍历二叉树(用队列)
如果 node.left!=null，将 node.left 入队
如果 node.left==null && node.right!=null，返回 false
如果 node.right!=null，将 node.right 入队
如果 node.right==null
✓ 那么后面遍历的节点应该都为叶子节点，才是完全二叉树
✓ 否则返回 false
遍历结束，返回 true
// 判断一棵树是否为完全二叉树
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 (node.left != null) {
queue.offer(node.left);
} else if (node.right != null) { // node.left == null && node.right != null
return false;
}
if (node.right != null) {
queue.offer(node.right);
} else { // node.right == null
leaf = true;
}
}
return true;
}
// 判断一棵树是否为完全二叉树
static void test() {
BinarySearchTree<Integer> bst1 = new BinarySearchTree<>();
for (int i = 0; i < 5; i++) {
bst1.add((int)(Math.random() * 100));
}
BinaryTrees.println(bst1);
System.out.println(bst1.isComplete());// 判断一棵树是否为完全二叉树
Integer data[] = new Integer[] {
7, 4, 9, 2, 5
};
BinarySearchTree<Integer> bst2 = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst2.add(data[i]);
}
BinaryTrees.println(bst2);
System.out.println(bst2.isComplete());// 判断一棵树是否为完全二叉树
}
练习 - 翻转二叉树
◼ https://leetcode-cn.com/problems/invert-binary-tree/
◼ 请分别用递归、迭代(非递归)方式实现
TreeNode:
package 二叉树;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
this.val = x;
}
}
package 二叉树;
/*
* 练习 - 翻转二叉树
* ◼ https://leetcode-cn.com/problems/invert-binary-tree/
*/
import java.util.LinkedList;
import java.util.Queue;
public class L_226_翻转二叉树 {
public L_226_翻转二叉树() {
}
// 方法一：
public TreeNode invertTree1(TreeNode root) {
if (root == null) return root;
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree1(root.left);
invertTree1(root.right);
return root;
}
// 方法二：后序遍历
public TreeNode invertTree2(TreeNode root) {
if (root == null) return root;
invertTree2(root.left);
invertTree2(root.right);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
return root;
}
// 方法三：中序遍历
public TreeNode invertTree3(TreeNode root) {
if (root == null) return root;
invertTree3(root.left);
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
invertTree3(root.left);// 上面已经交换了，所以，要取left
return root;
}
// 方法四：层序遍历
public TreeNode invertTree4(TreeNode root) {
if (root == null) {
return root;
} else {
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode node = (TreeNode)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;
}
}
}
前驱节点(predecessor)
◼ 前驱节点:中序遍历时的前一个节点
如果是二叉搜索树，前驱节点就是前一个比它小的节点
◼ node.left != null
举例:6、13、8
predecessor = node.left.right.right.right...
✓ 终止条件:right 为 null
◼ node.left == null && node.parent != null
举例:7、11、9、1
predecessor = node.parent.parent.parent...
✓ 终止条件:node 在 parent 的右子树中
◼ node.left == null && node.parent == null
那就没有前驱节点
举例:没有左子树的根节点
// 前驱节点(predecessor)
@SuppressWarnings("unused")
private 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;
}
后继节点(successor)
◼ 后继节点:中序遍历时的后一个节点
如果是二叉搜索树，后继节点就是后一个比它大的节点
◼ node.right != null
举例:1、8、4
successor = node.right.left.left.left...
✓ 终止条件:left 为 null
◼ node.right == null && node.parent != null
举例:7、6、3、11
successor = node.parent.parent.parent...
✓ 终止条件:node 在 parent 的左子树中
◼ node.right == null && node.parent == null
那就没有前驱节点
举例:没有右子树的根节点
根据元素内容获取节点
删除节点 – 叶子节点
◼ 直接删除
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
➢child.parent = null
删除节点 – 度为2的节点
◼举例:先删除 5、再删除 4
◼ 先用前驱或者后继节点的值覆盖原节点的值
◼ 然后删除相应的前驱或者后继节点
◼如果一个节点的度为 2，那么
它的前驱、后继节点的度只可能是 1 和 0
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) {
Node<E> node = root;
while (node != null) {
int cmp = compare(element, node.element);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else { // cmp < 0
node = node.left;
}
}
return null;
}
public boolean hasTwoChildren() {
return left != null && right != null;
}
// 删除节点
static void test16() {
System.out.println("--------------------------------- 删除节点");
Integer data[] = new Integer[] {
7, 4, 9, 2, 5, 8, 11, 3, 12, 1
};
BinarySearchTree<Integer> bst = new BinarySearchTree<>();
for (int i = 0; i < data.length; i++) {
bst.add(data[i]);
}
BinaryTrees.println(bst);
// bst.remove(1);
// bst.remove(3);
// bst.remove(12);
// 删除叶子节点
// bst.remove(5);
// 删除度为1的节点
// bst.remove(11);
// 删除度为1的节点
// bst.remove(11);
// 删除根节点
bst.remove(7);
BinaryTrees.println(bst);
}
简单的继承结构
作业
◼ 删除二叉搜索树中的节点:https://leetcode-cn.com/problems/delete-node-in-a-bst/
◼ 二叉搜索树中的搜索:https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
◼ 二叉搜索树中的插入操作:https://leetcode-cn.com/problems/insert-into-a-binary-search-tree/
◼ 验证二叉搜索树:https://leetcode-cn.com/problems/validate-binary-search-tree/comments/
◼ 二叉搜索树的最小绝对差:https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/comments/
◼ 二叉搜索树结点最小距离:https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/comments/
◼ 将有序数组转换为二叉搜索树:https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
◼ 二叉搜索树的范围和:https://leetcode-cn.com/problems/range-sum-of-bst/
◼ 二叉搜索树的最近公共祖先:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
◼ 二叉搜索树中第K小的元素:https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/
◼ 二叉搜索树迭代器:https://leetcode-cn.com/problems/binary-search-tree-iterator/
◼ 恢复二叉搜索树:https://leetcode-cn.com/problems/recover-binary-search-tree/
