数据结构大纲

2022-07-08  本文已影响0人  夜凉听风雨

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.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 
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、重构二叉树

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

2.7.10.1、平衡

为了提高搜索树的搜索效率，要尽量防止它退化成链表，所以就要平衡二叉搜索树。
当节点数量固定时，左右子树的高度越接近，这棵二叉树就越平衡(高度越低)

图片.png

2.7.10.2、如何平衡？

图片.png

2.7.10.3、 AVL树

平衡因子 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树平衡总结

2.7.11、 红黑树

2.7.12、B树

2.7.12.1、简介

B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现

图片.png
2.7.12.2、特点
2.7.12.3、m阶B树的性质

注：┌m / 2┐表示m / 2向上取整

上一篇下一篇

猜你喜欢

热点阅读