玩转数据结构——第五章:二分搜索树
内容概要:
- 为什么要研究树结构
- 二分搜索树基础
- 向二分搜索树中添加元素
- 改进添加操作:深入理解递归终止条件
- 二分搜索树的查询操作
- 二手搜索树的前序遍历
- 二分搜索树的中序遍历和后序遍历
- 深入理解二分搜索树的前中后遍历(深度遍历)
- 二分搜索树是的前序遍历的非递归实现
- 二分搜索树的层序遍历(广度遍历)
- 删除二分搜索树的最大元素和最小元素
- 删除二分搜索数的任意元素
1-为什么要研究树结构
- 树结构本身是一种天然的组织结构
- 高效
- 将数据使用树结构存储后,出奇的高效
2- 二分搜索树基础
什么是二叉树?
-
跟链表一样,二叉树也是一种动态数据结构,即,不需要在创建时指定大小。
-
跟链表不同的是,二叉树中的每个节点,除了要存放元素e,它还有两个指向其它节点的引用,分别用Node left和Node right来表示。
-
类似的,如果每个节点中有3个指向其它节点的引用,就称其为"三叉树"...
-
二叉树具有唯一的根节点。
-
二叉树中每个节点最多指向其它的两个节点,我们称这两个节点为"左孩子"和"右孩子",即每个节点最多有两个孩子。
-
一个孩子都没有的节点,称之为"叶子节点"。
-
二叉树的每个节点,最多只能有一个父亲节点,没有父亲节点的节点就是"根节点"。
-
二叉树的形象化描述如下图:
Class Node{
E e;
Node left;//左孩子
Node right;//右孩子
}
- 二叉树具有天然的递归结构
- 每个节点的左子树也是二叉树
- 每个节点的右子数也是二叉树
- 二叉树不一定是"满"的
- 二叉树不一定是"满的",即,某些节点可能只有一个子节点;
- 更极端一点,整棵二叉树可以仅有一个节点;在极端一点,整棵二叉树可以一个节点都没有;
什么是二分搜索树(Binary Search Tree)?
- 二分搜索树是二叉树
- 二分搜索树的每一个节点的值:
- 大于其左子树的所有节点的值
- 小于其右子树的所有节点的值
- 每一颗子树也是二分搜索树
- 不一定每个二分搜索树都是"满"的
- 存储的元素必须有可比较性
二分搜索树的底层代码
/**
* 二分搜索树 Binray searc Tree
*/
public class BST<E extends Comparable<E>> {//E的类型必须满足可比较性
private class Node {
public E e;//存放元素
public Node left, right;
//带参构造函数
public Node(E e) {
this.e = e;
left = null;
right = null;
}
}
//成员变量
private Node root;//根节点
private int size;//存储多少个元素
//二分搜索树的构造函数
public BST() {
root = null;
size = 0;
}
//成员函数,当前存储多少元素
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
3-向二分搜索树中添加元素
compareTo() 方法
compareTo() 方法用于将 Number 对象与方法的参数进行比较。可用于比较 Byte, Long, Integer等。
该方法用于两个相同数据类型的比较,两个不同类型的数据不能用此方法来比较。
A.compareTo(B) :A是指定的数、B是参数
如果指定的数与参数相等返回0。(A=B)
如果指定的数小于参数返回 -1。(A<B)
如果指定的数大于参数返回 1。(A>B)
使用递归的方式解决二分搜索树的添加操作
- 首先最基本的问题,执行到函数最底层时要进行终止(返回),否则递归就会一直下去
- 最基本的问题是:当某个不为空的节点插入新的节点,假设插入右节点,那么插入的数肯定比当前节点大,
- 然后继续往下,没有节点了
- node此时为空,则当node为空时(返回要插入的这个元素的节点)<——这是最基本问题(最底层)
- 当前的节点的右节点就可以顺利插入元素e;
/**二分搜索树:当前节点
* 大于其左子树的所有节点的值
* 小于其右子树的所有节点的值
* @param node
* @param e
* @return
*/
//向以node为根节点的二分搜索树插入元素e,递归算法
//返回插入新节点后二分搜索树的根
private Node add(Node node,E e){
//1找出最基本的问题,执行到函数最底层时要进行终止(返回),否则递归就会一直下去
//最基本的问题是:当某个不为空的节点插入新的节点,假设插入右节点,那么插入的数肯定比当前节点大,
// 然后继续往下,没有节点了
// node此时为空,则当node为空时(返回要插入的这个元素的节点)<——这是最基本问题(最底层)
// 当前的节点的右节点就可以顺利插入元素e;
//1最基本问题的解决
if(node==null) {//还有一种是从空节点的二叉树中插入元素
size++;//记录元素个数
return new Node(e);
}
if(e.compareTo(node.e)<0){//当前指定的元素e小于node的值,则在左边插入
node.left=add(node.left,e);//调用递归
}
else if(e.compareTo(node.e)>0) {//当前指定的元素e大于node的值,则在右边插入
node.right=add(node.right,e);
}
return node;//返回插入新节点后二分搜索树的根
}
//在二分搜索树中添加元素e
public void add(E e){
root= add(root,e);
}
5-二分搜索树的查询操作(递归算法)
这是最基本的问题:(类似终止条件)
- 1:空二分搜索树
- 2:没有找到
- 3:找到了
//用户使用的添加方法
public void add(E e) {
root = add(root, e);
}
//看以node为根的二分搜索树是否包含元素e,递归算法
private boolean contains(Node node, E e) {
if (node == null)//(这是最基本的问题1:空二分搜索树 2:找到最底部都没有 3:找到了)
return false;
//找到这个元素(这是也最基本的问题)
if (e.compareTo(node.e) == 0)
return true;
//如果这个元素在node的左边,它将递归查找左边的数
else if (e.compareTo(node.e) < 0)
return contains(node.left, e);
//如果这个元素在node的右边
else //e.compareTo(node.e)>0
return contains(node.right, e);
}
//看二分搜索树中是否包含元素e
public boolean contain(E e) {
return contains(root, e);
}
6-二分搜索树的遍历(深度优先遍历)
所谓的遍历:
对于每个节点而言,可能会有左、右两个孩子,所以分成下图中3个点,每次递归过程中会经过这3个点
- 前序遍历:先访问当前节点,再依次递归访问左右子树
- 中序遍历:先递归访问左子树,再访问自身,再递归访问右子树
- 后续遍历:先递归访问左右子树,再访问自身节点
1. 前序遍历
(1)算法思想
前序遍历:先访问当前节点,再依次递归访问左右子树。查看以下动画即可
图片来源:https://blog.csdn.net/ITermeng/article/details/77737480
其实在遍历过程中每个节点都访问了3次,对应着这3个小点,顺序为前-> 中 -> 后,只有在“前”点时才会打印该节点元素值。
最终打印结果:
代码实现:
//二分搜索树的前序遍历
public void preOrder() {
preOrder(root);
}
//前序遍历以node为根节点的二分搜索树,递归算法
private void preOrder(Node node) {
if (node == null)//递归的终止条件
return;
System.out.println(node.e);//打印它走过的节点
preOrder(node.left);
preOrder(node.right);
}
测试准备:
@Override
public String toString() {
StringBuilder res = new StringBuilder();
generateBSTString(root, 0, res);
return res.toString();
}
// 生成以node为根节点,深度为depth的描述二叉树的字符串
private void generateBSTString(Node node, int depth, StringBuilder res) {
if (node == null) {
res.append(generateDepthString(depth) + "null\n");
return;
}
res.append(generateDepthString(depth) + node.e + "\n");
generateBSTString(node.left, depth + 1, res);
generateBSTString(node.right, depth + 1, res);
}
private String generateDepthString(int depth) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; i++)
res.append("--");
return res.toString();
}
在Main中测试
public class Main {
public static void main(String[] args) {
BST<Integer> bst = new BST<>();
int[] nums = {5, 3, 6, 8, 4, 2};
for(int num: nums)
bst.add(num);
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
bst.preOrder();
System.out.println();
System.out.println(bst);
}
}
结果:
5
3
2
4
6
8
5
--3
----2
------null
------null
----4
------null
------null
--6
----null
----8
------null
------null
2. 中序遍历
(1)算法思想
中序遍历:先递归访问左子树,再访问自身,再递归访问右子树。
在遍历过程中每个节点都访问了3次,对应着这3个小点,顺序为前-> 中 -> 后,只有在“中”点时才会打印该节点元素值。
最终打印结果:
查看其打印结果,是按照从小到大的顺序进行打印的,所以在进行实际应用时,可使用二分搜索输的中序遍历将元素按照从小到大顺序输出。其原因与二分搜索树定义相关的!
代码实现:
//二分搜索树的中序遍历
public void inOrder() {
inOrder(root);
}
//中序遍历以node为根的二分搜索树,递归算法
private void inOrder(Node node) {
if (node == null)
return;
inOrder(node.left);
System.out.println(node.e);//打印当前根节点
inOrder(node.right);
}
Main函数测试:
public class Main {
public static void main(String[] args) {
BST<Integer> bst = new BST<>();
int[] nums = {5, 3, 6, 8, 4, 2};
for(int num: nums)
bst.add(num);
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
bst.inOrder();
System.out.println();
}
}
结果:
2
3
4
5
6
8
3. 后序遍历
(1)算法思想
后续遍历:先递归访问左右子树,再访问自身节点。
在遍历过程中每个节点都访问了3次,对应着这3个小点,顺序为前-> 中 -> 后,只有在“后”点时才会打印该节点元素值。
最终打印结果:
代码实现:
//二分搜索树的后序遍历
public void postOrder() {
postOrder(root);
}
//后序遍历以node为根的二分搜索树,递归算法
public void postOrder(Node node) {
if (node == null)//递归终止条件
return;
/*先查询左边子树,再遍历右子树,再遍历这个节点
*/
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
}
测试:结果
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
2
4
3
8
6
5
以上所有深度优先遍历代码实现可分为3个步骤:
- 递归左孩子
- 递归右孩子
- 打印自身
以上遍历只是交换了这3个步骤的执行顺序。
9-二分搜索树是的前序遍历的非递归实现
28进队后出队,其右左节点进队(后进先出),然后左节点16出队,对16节点进行访问,16节点有左右节点,将16的左右节点先右节点、后左节点的方式存入..
/*用非递归的方式(借助栈)实现二分搜索树的前序遍历
*/
public void preNROrder() {
Stack<Node> stack = new Stack<>();
stack.push(root);//把根节点放到栈里面
while (!stack.isEmpty()) {//当栈里面不为空
Node cur = stack.pop();//拿到栈顶元素,放到cur里面
System.out.println(cur.e);
//栈是后入先出的(要实现先访问左子树再访问右子树,就先把右子树放进栈里
if (cur.right != null)
stack.push(cur.right);
if (cur.left != null)
stack.push(cur.left);
}
}
10-二分搜索树的层序遍历(广度遍历)
前序、中序、后序遍历本质都是深度优先遍历
- 层序遍历:根节点设置为第0层;先遍历第0层28、再遍历第1层16、30;
- 再遍历第2层13、22、29、42;逐层向下遍历的节点在广度上进行拓展;
- 这种遍历方式也称为广度优先遍历;通常使用非递归的方式实现(借助队列Queue)
图解:用队列的方式实现层序遍历
1.每一次一个元素入队,从队尾的位置进入队列,初始化时将根节点入队
2.以后每一次要做的事就是先看队首(看该到谁开始遍历了),出队的就是根节点28,访问28对其进行相应的操作,这样28就遍历完了;
3.将根节点 28 的左右孩子(16和30)分别入队【对于队列来说,是先进先出,所以我们按照从左到右的顺序进行入队,所以先入队16后入队30】
4.现在的队首是16,将16拿出来,对其进行访问
5.将 16 的左右孩子 13 和 22 入队,
6.对队首元素 30 出队,对其进行操作,并将 30 的左右孩子(29和42)入队
7.对队首元素 13 出队,对其进行操作,但13没有左右节点,他是个叶子节点;
8.然后与上述相同,依次对队首元素进行操作,队列全部出队;【到这一步,队列的排序就与层序遍历相同了】
//二分搜索树的层序遍历
public void levelOrder() {
Queue<Node> q = new LinkedList<>();
q.add(root);
while (!q.isEmpty()) {//如果队列不为空
Node cur = q.remove();//出队元素放到cur
System.out.println(cur.e);
if (cur.left != null)//有左孩子
q.add(cur.left);
if (cur.right != null)//有右孩子
q.add(cur.right);
}
}
测试结果
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
5
3
6
2
4
8
11-删除二分搜索树的最大元素和最小元素
random.nextInt(int n)
该方法的作用是生成一个随机的int值,该值介于[0,n)的区间,也就是0到n之间的随机int值,包含0而不包含n。
寻找二分搜索树的最小元素:
最小元素都在node的左边
// 寻找二分搜索树的最小元素
public E minimum() {
if (size == 0)
throw new IllegalArgumentException("BST is empty");
Node minNode = minimum(root);
return minNode.e;
}
// 返回以node为根的二分搜索树的最小值所在的节点
private Node minimum(Node node) {
if (node.left == null)
return node;
return minimum(node.left);
}
寻找二分搜索树的最大元素:
最小元素都在node的右边
// 寻找二分搜索树的最大元素
public E maximum() {
if (size == 0)
throw new IllegalArgumentException("BST is empty");
return maximum(root).e;
}
// 返回以node为根的二分搜索树的最大值所在的节点
private Node maximum(Node node) {
if (node.right == null)
return node;
return maximum(node.right);
}
删除二分搜索树最小节点
// 从二分搜索树中删除最小值所在节点, 返回最小值
public E removeMin() {
E ret = minimum();
root = removeMin(root);
return ret;
}
// 删除掉以node为根的二分搜索树中的最小节点
// 返回删除节点后新的二分搜索树的根
private Node removeMin(Node node) {
//递归的终止条件(最基本问题)
if (node.left == null) {//当此时node没有左子树
Node rightNode = node.right;//保存node右子树
node.right = null;//另当前节点node.left=node.right=null 脱离二分搜索树
size--;//控制二分搜索树的大小
return rightNode;//返回它的右子树
}
//递归操作
node.left = removeMin(node.left);
return node;
}
删除二分搜索树的最大节点
// 从二分搜索树中删除最大值所在节点
public E removeMax() {
E ret = maximum();
root = removeMax(root);
return ret;
}
// 删除掉以node为根的二分搜索树中的最大节点
// 返回删除节点后新的二分搜索树的根
private Node removeMax(Node node) {
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
node.right = removeMax(node.right);
return node;
}
删除二分搜索树的任意节点
三种情况(叶子节点可以是以下任意一种情况)
1.要删除的节点没有左子树
2.要删除的节点没有右子树
3.要删除的节点左右子树都有
当要删除的节点左右子树都有:
可以采用2种方式:
1.将该节点的左子树的最大值(前驱),顶替该节点的位置,然后让该节点脱离二分搜索树
2.将该节点的右子树的最小值(后继),顶替该节点的位置,然后让该节点脱离二分搜索树
以下代码是第二种后继的方式:
//从二分搜索树中删除元素为e的节点
public void remove(E e) {
root = remove(root, e);
}
//删除以node为根的二分搜索树中值为e的节点,递归算法
//返回删除节点后新的二分搜索树的根
private Node remove(Node node, E e) {
if (node == null)
return null;
if (e.compareTo(node.e) < 0) {//要删除的元素e比当前元素小
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {//e.equals(node.e)
//待删除节点的左子树为空的情况
if (node.left == null) {
Node rightNode = node.right;//保存一下这个孩子的右子树
node.right = null;//右子树
size--;
return rightNode;
}
//待删除节点的右子树为空的情况
if (node.right == null) {
Node leftNode = node.left;
node.left = null;//让当前的node与二分搜索树脱离 满足node.left=node.right=null
size--;
return leftNode;
}
//第三种情况
//待删除的节点左右子树均不为空
//找到比待删除节点到达的最小节点,即待删除节点的右节点的最小节点
//用这个节点顶替待删除节点的位置
Node successor = minimum(node.right);//找到当前节点右子树最小的值
//successor为顶替待删除的节点(后继)
successor.right = removeMin(node.right);//将node.right的最小值给删除
successor.left = node.left;
node.left = node.right = null;//让当前node与二分搜索树脱离关系
return successor;
}
}