1、线性表
1.1、数组
1.1.1、简介
数组是一段连续的内存
1.1.2、动态数组
有动态扩容功能和动态缩容功能。
添加元素超过申请的最大空间数后，会重新申请一个更大的空间，如原空间的1.5倍，来装载这些元素。
删除元素，少于申请的空间数的某个百分比的时候，如25%，将会重新申请一个更小的空间，来装载这些元素，达到节约空间的目的。
1.2、链表
1.2.1、单向链表
有next指针
first指针指向第一个节点
查数据要从第一个节点一直找下一个节点
图片.png
1.2.2、双向链表
有pre指针和next指针
first指针指向第一个节点，last指针指向最后一个节点
图片.png
查数据的时候可以计算要查询的位置是从第一个节点往后查快，还是从最后一个节点往前查快。
所以双向链表查询某个节点的时候，平均时间要比单向链表节省一半。
1.2.3、单向循环链表
最后一个节点的next又指向第一个节点形成循环。
图片.png
只有一个节点时：
图片.png
1.2.4、双向循环链表
图片.png
经典面试题：
如何判断一个链表是否有环？
翻转链表
1.3、栈
栈是一种特殊的线性表，只能在一端进行操作
往栈中添加元素的操作，一般叫做push,入栈
从栈中移除元素的操作，一般叫做pop，出栈(只能移除栈顶元素,也叫做:弹出栈顶元素)
后进先出的原则，Last In First Out， LIFO
图片.png
比如浏览器前进后退，软件的撤销恢复都是栈的应用。使用2个栈来做到这种功能。
1.4、队列
1.4.1、简介
队列是一种特殊的线性表，只能在头尾两端进行操作
队尾(rear) :只能从队尾添加元素，一般叫做enQueue,入队
队头(front) :只能从队头移除元素，一般叫做deQueue, 出队
1.4.2、双端队列
双端队列是能在头尾两端添加、删除的队列
1.4.3、循环队列
-
和队列一样，只能在队尾加入元素，队首移除元素。
可以使用动态数组来实现循环队列功能，加一个指针，指向队首元素。
移除队首元素就将该元素置空，然后指针往后挪一位。
队尾添加的元素超过最大值后再从第一个内存空间往后加。
1.4.4、循环双端队列
-
可以在队首添加删除，也可以在队尾添加删除元素。
有一个队首指针，队尾位置是根据队首指针的位置计算出来的，具体为：
// frontIndex：队首指针位置，
// size：队列元素数量
// elements.length：数组总长度
(front + size - 1) % elements.length
2、树
节点、根节点、父节点、子节点、兄弟节点
空树：没有任何节点
子树、左子树、右子树
节点的度：子树的个数
树的度：所有节点的度中最大的值
叶子节点：度为0的节点
层数(level) :根节点在第1层，根节点的子节点在第2层，以此类推(有些教程也从第0层开始计算)
节点的深度(depth) :从根节点到当前节点的唯一路径上的节点总数
节点的高度(height) :从当前节点到最远子叶子节点的路径上的节点总数
树的深度:所有节点深度中的最大值
树的高度:所有节点高度中的最大值
树的深度等于树的高度
有序树：
树中任意节点的子节点之间有顺序关系
无序树：
树中任意节点的子节点之间没有顺序关系
也称为“自由树”
森林：
由m (m≥0)棵互不相交的树组成的集合
2.1、二叉树
-
二叉树的特点
每个节点的度最大为2 (最多拥有2棵子树)
左子树和右子树是有顺序的
即使某节点只有一棵子树，也要区分左右子树
2.2、多叉树
每个节点的度最大超过2
2.3、真二叉树
所有节点的度要么为0要么为2
图片.png
2.4、满二叉树
所有节点的度都要么为0，要么为2。且所有的叶子节点都在最后一层
图片.png
2.5、完全二叉树
叶子节点只会出现最后2层，且最后1层的叶子结点都靠左对齐
从根结点至倒数第2层是一棵满二叉树
图片.png
2.6、二叉搜索树
又被称为二叉查找树，二叉排序树
任意一个节点的值都大于其左子树所有节点的值
任意一个节点的值都小于其右子树所有节点的值
它的左右子树也是一棵二叉搜索树
二叉搜索树可以大大提高搜索数据的效率
二叉搜索树存储的元素必须具备可比较性
图片.png
2.7、二叉树的遍历
2.7.1、前序遍历
访问顺序：根节点、前序遍历左子树、前序遍历右子树
图片.png
- 实现思路: 使用递归
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);
}
2.7.2、中序遍历
访问顺序：中序遍历左子树、根节点、中序遍历右子树
图片.png
规律：二叉搜索树的中序遍历结果是升序或者降序的
- 实现思路: 使用递归
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);
}
2.7.3、后续遍历
访问顺序：后序遍历左子树、后序遍历右子树、根节点
图片.png
- 实现思路: 使用递归
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) ;
}
规律：
为了方便记忆前中后序遍历，先遍历父节点的叫前序遍历，先遍历一个子节点再到父节点的叫中序遍历，先遍历全部子节点最后到父节点的叫后序遍历。
2.7.4、层序遍历
访问顺序：从上到下、从左到右依次访问每一个节点
图片.png
-
实现思路: 使用队列
1、将根节点入队
2、循环执行以下操作，直到队列为空
--- 2.1、将队头节点A出队，进行访问
--- 2.2、将A的左子节点入队
--- 2.3、将A的右子节点入队
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. right != null) {
queue.offer(node.right);
}
}
}
-
经典面试题：
翻转二叉树
2.7.5、重构二叉树
-
以下结果可以保证重构出唯一的一棵二叉树
前序遍历+中序遍历
后序遍历+中序遍历 -
前序遍历+后序遍历
如果它是一棵真二叉树(Proper Binary Tree)，结果是唯一的
不然结果不唯一
2.7.6、前驱节点
中序遍历时的前一个节点
如果是二叉搜索树，前驱节点就是前一个比它小的节点
比如下图中序遍历的顺序是1、2、3、4、5、6、7、8、9、10、11、12、13
那么8的前驱节点就是7， 13的前驱节点是12
图片.png
2.7.7、后继节点
中序遍历时的后一个节点
如果是二叉搜索树，后继节点就是后一个比它大的节点
2.7.8、删除二叉搜索树的某个节点
2.7.8.1、删除叶子节点
直接删除叶子节点
如果是父节点的左节点
node.parent.left = null
如果是父节点的右节点
node.parent.right = null
如果有父节点
node.parent = null
2.7.8.2、删除度为1的节点
用子节点替代原节点的位置
如果要删除的节点是根节点，那么让根节点指向它的子节点
图片.png
2.7.8.3、删除度为2的节点
1、先用前驱或者后继节点的值覆盖原节点的值
2、然后删除相应的前驱或者后继节点
如果一个节点的度为2，那么它的前驱、后继节点的度只可能是1或0
2.7.9、二叉搜索树的复杂度
搜索一个节点的复杂度和树的高度有关
图片.png
图片.png
2.7.10、平衡二叉搜索树（Balanced Binary Search Tree）
英文简称为: BBST
-
经典常见的平衡二叉搜索树有
1、AVL树
Windows NT内核中广泛使用
2、红黑树 - C++ STL (比如map、set )
- Java的TreeMap、 TreeSet、 HashMap、 HashSet
- Linux的进程调度
- Ngix的timer管理
一般也称它们为:自平衡的二叉搜索树(Self-balancing Binary Search Tree)
2.7.10.1、平衡
为了提高搜索树的搜索效率，要尽量防止它退化成链表，所以就要平衡二叉搜索树。
当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡(高度越低)
图片.png
2.7.10.2、如何平衡？
图片.png
2.7.10.3、 AVL树
- 平衡因子(Balance Factor) :某结点的左右子树的高度差
平衡因子
-
AVL树的特点
1、每个节点的平衡因子只可能是1、0、-1 (绝对值≤1，如果超过1,称之为“失衡”)
2、每个节点的左右子树高度差不超过1
3、搜索、添加、删除的时间复杂度是O(logn)
AVL树
2.7.10.3.1、LL-右旋转（单旋）
LL表示失衡节点在某节点的左节点(L)的左节点(L)下
旋转过程
2.7.10.3.2、RR-左旋转（单旋）
RR表示失衡节点在某节点的右节点(R)的右节点(R)下
旋转过程
2.7.10.3.3、LR-RR左旋转，LL右旋转（双旋）
LR表示失衡节点在某节点的左节点(L)的右节点(R)下
先进行RR-左旋转，变为了2.7.10.3.1、LL-右旋转（单旋）中的情况
再进行LL-右旋转，恢复平衡
旋转过程
2.7.10.3.4、RL-LL右旋转，RR左旋转（双旋）
RL表示失衡节点在某节点的右节点(R)的左节点(L)下
先进行LL-右旋转，变为了2.7.10.3.2、RR-左旋转（单旋）中的情况
再进行RR-左旋转，恢复平衡
旋转过程
2.7.10.3.5、恢复平衡统一处理
恢复平衡可以不判断上面的四种情况，而直接用一套方法统一处理。
图片.png
通过观察上图，可以发现，这四种失衡的情况，平衡后的样子是一样的。
规律：
1、都会让d节点到最中间，成为这棵树的根节点。
2、让b节点加上a子树和c子树成为一棵子树，成为d节点的左子树。
3、让f节点加上e子树和g子树成为一棵子树，成为d节点的右子树。
2.7.10.3.6、AVL树平衡总结
-
在AVL树中添加一个节点，如果导致失衡，只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡。
-
但是如果是删除一个节点，只会导致父节点或者祖先节点失衡（只有一个节点会失衡），让父节点或者祖先节点恢复平衡后，可能会导致更高层的祖先节点失衡（最多需要O(logn)次调整）
2.7.11、 红黑树
2.7.12、B树
2.7.12.1、简介
B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现
图片.png
2.7.12.2、特点
- 1个节点可以存储超过2个元素、可以拥有超过2个子节点
- 拥有二叉搜索树的一些性质
- 平衡，每个节点的所有子树高度一致
- 比较矮
2.7.12.3、m阶B树的性质
- 假设一个节点存储的元素个数为X
- 根节点:1 ≤ X ≤ m - 1
- 非根节点:┌m / 2┐ - 1 ≤ x ≤ m - 1
- 如果有子节点，子节点个数y = x + 1
Δ 根节点: 2 ≤ y ≤ m
Δ 非根节点: ┌m / 2┐ ≤ y ≤ m
○ 比如m = 3, 2 ≤ y ≤ 3,因此可以称为(2, 3) 树、2-3树
○ 比如m = 4, 2 ≤ y ≤ 4,因此可以称为(2, 4)树、2-3-4树
○ 比如m = 5, 3 ≤ y ≤ 5,因此可以称为(3, 5) 树
○ 比如m = 6, 3 ≤ y ≤ 6,因此可以称为(3, 6) 树
○ 比如m = 7, 4 ≤ y ≤ 7,因此可以称为(4, 7) 树
注：┌m / 2┐表示m / 2向上取整
网友评论