数据结构基础复习

参考书籍及图片来源：《大话数据结构》

一、线性表

• 顺序存储结构 --> 便于 add 和 get，不便于 insert 和 delete，需要提前定义大小
• 链式存储结构 --> 便于 insert 和 delete，不便于 get，不需要提前定义大小
  • 单链表
  • 循环链表
  • 双链表
  • 双向循环链表

二、栈与队列（特殊的线性表）

• 栈：只能在一端进行插入与删除，先进后出
  • 顺序栈
  • 链栈
• 队列：只能在一端掺入，另一端删除，先进先出
  • 顺序队列
  • 循环队列
  • 链队列

三、串

四、树（面试重难点）

1. 定义

2. 结构表示法

   • 双亲表示法

   

   • 孩子表示法

     
     

   方法一损耗空间，方法二损耗时间

   ​

   • 孩子兄弟表示法

3. 简单分类

1. 二叉树：每个节点最多两颗子树，左子树与右子树顺序不能颠倒
2. 斜树：特殊二叉树，所有节点往左斜的叫左斜树，右边同理；每层只有一个节点
3. 满二叉树：所有分支节点都有左右节点，所有叶子都在同一层
4. 完全二叉树：最后一层可以缺胳膊少腿的满二叉树（最后一层从左往右排，可以不排满，但中间不能有空）

4. 遍历方法

1. 前序遍历：先左后右，从根节点开始，每个节点没有左节点才能遍历右节点

2. 中序遍历

3. 后序遍历：最后访问根节点

4. 层序遍历

5. 分类（重难点）

1. 线索二叉树：利用好每个节点的空指针域，化作双向链表；线索化的过程就是在遍历过程中修改空指针的过程
2. 赫夫曼树与赫夫曼编码：根据频率从下往上构造一颗最优二叉树，应用与压缩和解压缩领域
3. 二叉排序树（二叉查找树）：中序遍历，左子树值小于根节点值，右子树值大于根节点值，左、右子树也是二叉排序树；可以提高查找、插入、删除的速度
4. 平衡二叉树（AVL树）：弥补二叉排序树极端倾斜的缺点，每个节点的左子树与右子树高度差至多等于1
5. 红黑树一种含有红黑结点并能自平衡的二叉查找树
6. B 树多路平衡查找树
7. B+ 树优化后的多路平衡查找“树”