数据结构：数据之间相互存在的一种或多种特定关系的元素的集合。

逻辑结构分类：集合结构，线性结构，树形结构，图形结构。

物理结构分类：顺序存储，链式存储 。

1.二叉树

先来看看什么是树。树中基本单位是结点，结点之间的链接，称为分支。一棵树最上面的结点称之为根节点，而下面的结点为子结点。一个结点可以有0个或多个子结点，没有子结点的结点我们称之为叶结点。

二叉树是指子结点数目不超过2个的树，它是一种很经典的数据结构。而二叉搜索树(BST)是有序的二叉树，BST需要满足如下条件：

若任意结点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

若任意结点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；(有些书里面定义为BST不能有相同值结点，本文将相同值结点插入到右子树)

任意结点的左、右子树也分别为二叉查找树

typedef struct BTNode {

    int value;

    struct BTNode *left;

    struct BTNode *right;

} BTNode;

* 每个节点最多只有一个父节点。

* 节点拥有子树数称为节点的度。

* 度为0的节点称为叶子节点。

* 树的度是树内部个节点度的最大值。

* 节点的层次从根开始定义，根为第一层。总层数即为树的深度 。

* 森林是不相交的树的集合

* **满二叉树**：每个节点都有个子节点，所有叶子都在同一层上

* **完全二叉树**： 完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

* 前序遍历（根节点-左节点-右节点） ，中序遍历（左节点-根节点-右节点），后序遍历（左节点-右节点-根节点）。

* 除了迭代，栈也可以实现二叉树的遍历

* **搜索（查找）二叉树**：任何一个结点，它的左子树的所有结点都比这个根结点要小，它的右子树的所有结点都比这个根结点要大。

* 如果一棵二叉树按照中序遍历得到的序列时有序的，那么这棵二叉树一定是搜索二叉树。

*

* TreeSet:

* 内部填装数据需要继承Comparable<>方法，并实现compareto方法。

* compareto方法返回1，表示新插入的元素比被比较元素大，会插在树的右侧;如果为0表示相同，会舍弃该值。

* TreeMap:

* 本质为红黑树

2.栈

* 后进先出

* 栈的经典应用：

* 波兰表达式 : 中缀表达式转后缀表达式（数字输出，运算符进展，括号匹配出战，栈顶优先级低出栈）。

* 后缀表达式的计算。

*

* 通过维护 Node 连接来实现

3.队列

* LinkedList实现了Queue的接口

* 先进先出。先出的一端为队头，另一端为队尾。

* LinkedList就是天生的队列实现。

4.顺序存储方式线性表（ArrayList）

* 顺序存储方式线性表（ArrayList）：查找效率高，插入删除效率低（ArrayList删除元素后，后面元素会向前位移）

* ArrayList的本质是维护了一个对象数组，对ArrayList的增删改查即对数组进行操作

* 1. List接口中有sort方法，需要实现Comparator方法就能进行排序

* 2. List接口继承Collection，Collection集成Iterable

* 3. System.arraycopy  是用于复制数组的native方法，应学会使用。

*

*  Vector：

*  矢量队列，它是JDK1.0版本添加的类。

*  和ArrayList类似，内部维护一个对象数组。

*  Vector 实现了RandmoAccess接口，即提供了随机访问功能。

*  Vector中的操作是线程安全的,但比ArrayList稍微慢。

5.  链式存储方式线性表（linkedList）

* 链式存储方式线性表（linkedList）：插入效率高，查询效率低

* 通过内部维护连接 Node对象 来实现链式存储结构

6.哈希表

* key存在Set集合中（Set中数据不能相同），Value存在Collection中（可以相同）。

* 无序集合，多线程下不安全

* Hashmap默认初始化大小16，负载因子0.75

* hashmap元素的key可以为空，key对应的index可以相同（链表）

* JDK 1.8 以前 HashMap的实现是数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。

* 针对这种情况，JDK 1.8 中引入了 红黑树（查找时间复杂度为O(logn)）来优化这个问题,

* 红黑树是自动平衡的二叉查找树，通过变色，左转，右转来实现平衡。

7.链式哈希表

* Node<K, V> 每个节点添加头尾指针，构成双向链表

* LruCache的实现（Linkedhashmap默认插入排序，需要配置一个布尔值accessOrder来设置调用排序）。

* LinkedHashMap的实现就是HashMap+LinkedList的实现方式，以HashMap维护数据结构，以LinkList的方式维护数据插入顺序。

* next是用于维护HashMap指定table位置上连接的Entry的顺序的，before、After是用于维护Entry插入的先后顺序的。

* 迭代HashMap的顺序并不是HashMap放置的顺序，Linkedhashmap有顺序，插入顺序或者调用顺序，默认采用插入。

* 线程不安全

*

* 该循环双向链表的头部存放的是最久访问的节点或最先插入的节点，尾部为最近访问的或最近插入的节点，迭代器遍历方向是从链表的头部开始到链表尾部结束，在链表尾部有一个空的header节点，该节点不存放key-value内容，为LinkedHashMap类的成员属性，循环双向链表的入口。

* header的目的是为了记录第一个插入的元素是谁，在遍历的时候能够找到第一个元素。

* 注意这个header，hash值为-1，其他都为null，也就是说这个header不放在数组中，就是用来指示开始元素和标志结束元素的。

*/

8.图

* 图的邻接表的实现

* 图中的元素称为顶点，顶点之间的连线叫做边，边分为无向边和有向边，有向边也称为弧，弧有弧头和弧尾。

* 弧有与之对应的数字，成为权。

* 任意两点之间是联通的，称为连通图。

* 图中一个顶点可以连接无数个顶点

* 无向图定点的边数叫度，有向图顶点的边数叫出度和入度。

* 图的实现：1. 邻接矩阵（一个一维数组表示顶点信息，一个二维数组存储弧的信息）。

* 图的实现：2.  邻接表（散链列表）

* 图-临接矩阵实现

* 图的两种遍历：深度优先遍历，广度优先遍历

* 图的最小生成树的两种算法：普利姆算法，克鲁斯卡尔算法

* 最短路径：迪杰斯特拉算法

/**

  * 最小生成树：

  * 普利姆算法：

  * 获取一个顶点A和它连接的顶点数组X，然后连接权值最小的顶点B，并将B连接的顶点数组合并到X，

  * 仍从X中找出权值最小的顶点连接，以此类推。

*/

/**

  * 最小生成树

  * 克鲁斯卡尔算法：

  * Edge edge0 = new Edge(int begin,int end, int weight);

  * begin为边的起始顶点，end为边的结束顶点，weight为边的权重

  * 通过构建边的数组来进行计算。

  * 思想：按权重从小到大遍历，构成回环的边舍弃

  *

*/

/**

  * 最短路径：

  * 迪杰斯特拉算法：

  * 获取一个顶点A和它连接的顶点数组X，然后连接最小权值(M)的顶点B，然后将B顶点的数组P整合到数组X(数组P相加M和数组X取最小值)

*/