一、线性表
是一种线性结构，由零个和多个数据元素构成的有限序列
特征:
在一个序列中，除了头尾元素，每个元素都有且只有一个直接前驱和一个直接后继，而头元素没有直接前驱，尾元素没有直接后继
数据结构中常见的线性结构有数组、单链表、双链表、循环链表等
1.数组
在实际的物理内存上也是连续存储的，数组有上界和下界，下标从0开始，第一个元素称为下界，最后个元素称为上界，超过这个范围的下标使用数组，将造成数组越界错误。数组分为固定数组和动态数组，固定数组的大小必须在编译时就确定， 动态数组允许在运行时申请数组内存
特点：数据连续，支持快速随机访问
2.单向链表
由节点构成，每个节点内都包含下一个节点的指针，节点依次链接成链表，因此在物理内存上是不连续的
特点：数据不连续，随机访问慢，增删元素效率高
3.双向链表
跟单链表一样， 双链表也是由节点组成，每个节点都有两个措针，分别指向直接前驱和直接后继，因此，从任一节点开始， 都可以很方便的访问它的前驱和后继节点
4.栈
特点：
（1）栈中的数据按照“先进后出”(FILO) 的方式进出栈
（2）添加/删除元素时，只能从栈顶进行操作
栈通常包括以下三种操作
push 向栈中添加元素
peek 返回栈顶元素
pop 返回并删除栈顶元素
5.队列
特点：
（1）队列中的数据按照“先进先出”(FIFO) 的方式进出队列
（2）在队尾添加元素(入队)，在队首删除元素(出队)
二、树
树是n(n=-0)个节点的有限集，n=0称为空树，n>0时，有限集的元素构成一个具有层次感的数据结构。 区别于线性表的一对一的元素关系，树中的节点是一对多的关系
树具有以下特点：
（1） n>0时， 根节点是唯一的，不存在多个根节点
（2）每个节点有零个至多个子节点，除了根节点外，每个节点有且只有一个父节点，根节点没有父节点
树的相关概念/术语:
（1）子树
除根节点外，每个子节点都可以分为多个不相交的子树
（2）孩子与双亲
若一个节点有子树，那么该节点称为子树的双亲，子节点称为该节点的孩子
（3）兄弟
具有相同双亲的节点互为兄弟
（4）节点的度
一个节点拥有子树的数量
（5）叶子
没有子树，即度为0的节点
（6）分支节点
除叶子节点外的节点，即度不为0的节点
（7）内部节点
除根节点外的分支节点
（8）层次
根节点为第一层，其余节点的层数等于其双亲节点的层次加一
（9）树的高度
也称为树的深度，树中节点的最大层次
（10）有序树
树中节点各子树之间存在次序，不可随意交换位置
（11）无序树
树中节点各子树之间的次序不重要，可随意交换位置
（12）森林
0或多棵互不相交的树的集合
1.二叉树
满足以下两个条件的树即为二叉树
（1）本身是有序树，且区分左右子树，不可随意交换子树位置
（2）树中包含的各个节点的度不能超过2，即只能是0、1或者2。0表示该节点为叶子节点，1表示该节点只有左子树或右子树，2表示该节点有左右子树
2.斜树、满二叉树、完全二叉树、二叉查找树
2.1斜树
分为左斜树和右斜树，所有节点都只有左子树的二叉树称为左斜树，反之称为右斜树，二者统称为斜树。斜树已经退化成线性结构，无法体现出二叉树查找的优异性
2.2满二叉树
需要满足以下两个条件:
（1）所有节点都具有左右子树
（2）所有叶子节点都在同一层
在同样深度的二叉树中， 满二叉树的节点数量是最多的， 叶子节点的数量也是最多的
2.3完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的节点依次从左到右分布， 则此二叉树被称为完全二叉树
2.4二叉查找树(BST， Binary Search Tree)
又称为二叉排序树或二叉搜索树，它改善了二叉树的查找效率。
二叉查找树具有以下性质：
（1）若左子树不为空，则左子树上所有节点的值都小于它根节点的值
（2）若右子树不为空，则右子树上所有节点的值都大于它根节点的值
（3）左、右子树也是二叉查找树
（4）没有键值相等的节点，即键值不能重复
3.平衡二叉树
遵循以下特点的二叉树， 即为平衡二叉树
（1）每棵子树中的左子树和右子树的高度差不能超过1
（2）每棵子树都要求是平衡二叉树
常见实现方法有AVL、红黑树、替罪羊树、Treap和伸展树等
遍历方式：
若二叉树为空，则返回空操作
（1）前序遍历(简记: VLR)
先访问根节点，然后遍历根节点的左子树，最后遍历右子树
（2）中序遍历(简记: LVR)
从根节点开始，先遍历根节点的左子树，然后访问根节点，最后遍历右子树
（3）后序遍历(简记: LRV)
从右到左先叶子后节点的方式遍历访问左右子树，最后访问根节点
3. 1AVL树的旋转
（1）单向右旋平衡处理
在根节点左子树的左子树上插入节点， 导致失去平衡，则需要进行一次向右的顺时针旋转
（2）单向左旋平衡处理
在根节点右子树的右子树上插入节点，导致失去平衡，则需要进行一次向左的逆时针旋转
（3）双向旋转(先左后右)平衡处理
在根节点左子树的右子树上插入节点，导致失去平衡，则需要进行两次旋转操作
（4）双向旋转(先右后左)平衡处理
在根节点右子树的左子树上插入节点，导致失去平衡，则需要进行两次旋转操作
3.2红黑树
红黑树的特点：
（1）是一种二又查找树，所以根节点比左边的都大，比右边的都要小
（2）根节点是黑色
（3）默认将空节点作为叶子节点，且都是黑色
（4）黑色节点的左右子节点必须是红色
（5）每个节点到达其所有可达叶子节点路径上的黑色节点数量必须一致，即任意节点到该节点可达叶子节点路径上的所有黑色节点数量一样
注意：插入的新节点默认为红色，原因是需要满足此条
（6）每个节点要么红色要么黑色
红黑树的平衡方法：
（1）通过旋转，和AVL的旋转一样，即左旋和右旋
(口诀:左右左右)左旋：把该节点作为其右子节点的左子节点，被占的节点作为其右子节点
(口诀:右左右左)右旋：把该节点作为其左子节点的右子节点，被占的节点作为其左子节点
（2）通过改变节点的颜色，也就是对节点重新着色
如果需要两者结合的时候，先变色或先旋转都行，只要最后达到平衡即可
红黑树的删除：
删除非叶子节点，用对应的中序遍历(按照节点值的从小到大排序)的前驱节点顶替要删除节点的位置，之后根据需要再做重新平衡的操作
三、图(Graph)
由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为: G(V,E)，其中G表示一个图，V表示图G中顶点的集合， E是图G中边的集合
图的相关术语：
（1）顶点的度
指图中与顶点相关联边的条数。对于有向图来说，顶点的度等于该顶点的出度与入度之和
（2）邻接
若无向图中的两个顶点V1和V2存在于条边(V1,V2)， 则称顶点V1和V2邻接；若有向图中存在一条边<V3,V4> ，则称顶点V3和V4邻接，且V3邻接到V4或V4邻接到V3
（3）路径
在无向图中，若从顶点Vi出发有一组边可到达顶点Vj， 则称顶点Vi到顶点Vj的顶点序列为顶点Vi到顶点Vj的路径
（4）连通
若从Vi到Vj有路径可通，则称顶点Vi和顶点Vj是连通的
（5）权(Weight)
有些图的边或弧具有与它相关的数字，则称该数字为权
1.1无向图
如果图中任意两个顶点之间的边都是无向边(没有方向的边)则称该图为无向图。无向图用小括号"()" 表示，如(V1,V2)
1.2有向图
如果图中任意两个顶点之间的边都是有向边(有方向的边)，则称该图为有向图。有向图用小括号“<>"表示，如<V1,V2>
1.3完全图
（1）无向完全图
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。n个顶点的无向完全图有n*(n 1)/2条边
（2）有向完全图
在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。n个顶点的有向完全图有n*(n-1)条边
2.图的遍历
（1）深度优先搜索遍历(DFS)
假设初始状态是图中所有顶点都未被访问，则从某个顶点V出发，首先访问该节点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和顶点V有路径相通的顶点都被访问到。若此时还有其他未被访问到的顶点，则另选一个未被访问到的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止
（2）广度优先搜索遍历(BFS)
又称宽度优先搜索或横向优先搜索。主要思想：从图中某顶点V出发，在访问了V之后依次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得先被访问的邻接点先于后被访问顶点的邻接点被访问，直至图中所有已被访问顶点的邻接点都被访问到。如果此时图中还有顶点未被访问到，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。简单来说，广度优先搜索遍历图的过程是以顶点V为起点，由近至远，依次访问和V有路径相通且路径长度为1，2，3...的顶点
