数据结构相关
本篇先写数据结构相关，后续再补充算法相关。
定义：数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
数据结构可按照逻辑结构和物理结构进行分析。
逻辑结构：是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。
物理结构：指的就是数据元素在计算机存储空间的存放形式。常见有顺序、链接、索引、散列等
针对于我们程序开发，通常数据结构就研究其逻辑结构，物理结构不需要我们处理，存储空间会按照相应逻辑结构自动进行转换存储，需要了解的是其内部增删改查的性能。我们着重了解下逻辑结构：
（图片摘自网络）
1、集合：
数据结构的集合不同于Java中的集合（ArrayList、LinkedList...），这里的集合概念同高中数学的集合类似，是一组无关系数据的集合，用数学表示：U={1,2,56,324,8}。Java的List其实是线性结构。
2、线性结构：
数据元素之间存在一对一的关系。
3、树形结构：
数据元素之间存在一对多的关系。
4、图形结构：
数据元素之间存在多对多的关系。
下面针对线性结构、树形结构、图形结构再展开分析：
一、线性结构：
常见线性结构有：线性表、栈、队列、串、 数组、广义表
线性表：必须存在唯一的一个“第一元素”和“最后一个元素”；除了第一个元素外，均有唯一的的前驱；除了最后一个元素外，均有唯一的后继。
栈：一个遵循先进后出原则的线性表。
队列：一个遵循先进先出原则的线性表。
串：字符串简称串，是一种特殊的线性表，它的数据元素仅由一个字符组成。
数组：是一个有序（在物理结构上）元素序列集合，一般长度一定，但子元素依然可以数组或者子表，组成多维的情况。
广义表：广义表是线性表的推广，但其本质依然属于线性表，并没有超出线性表的定义。其与一般线性表的区别是，其子元素可以是一个子表。
在此说下，Java中的List，常用的List有ArrayList，LinkedList、Vector。ArrayList和LinkedList都是线程不安全，区别在于物理结构上的差异，ArrayList是顺序存储，LinkedList是链式存储。至于Vector，可以理解为线程安全的ArrayList。
二、树形结构：
相关定义：
度：结点拥有的子树数称为结点的度
结点：结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲
深度：树中结点的最大层次成为树的深度（Depth）或高度，空树深度为0，非空>0。
有序树与无序树（长子，次子。。）：树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则成为无序树。
树的典型代表是二叉树：二叉树、
二叉树：每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），二叉树的子树有左右之分，其次序不能随意颠倒。
二叉树分类：满二叉树、完全二叉树、平衡二叉树、二叉查找树等。
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
完全二叉树：一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
平衡二叉树：又被称为AVL树，它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
二叉查找树：又称二叉搜索树、二叉排序树。可以是空树，规则：
①若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
② 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
③ 左、右子树也分别为二叉排序树；
红黑树：在二叉查找树基础上再加了5个特性：
性质1.节点是红色或黑色。
性质2.根节点是黑色。
性质3.每个叶子节点（注意是叶子，NIL节点，空节点）是黑色的。
性质4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续 的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树因为特性5，同时也是为了保持查找效率，对红黑树的深度做了一定限制，所以每次插入过程都可能伴随着左旋、右旋操作。详细参考：http://www.cnblogs.com/skywang12345/p/3245399.html
多叉树：
常见有B树、B+树等。详情可以参考：https://www.cnblogs.com/George1994/p/7008732.html
最后再介绍下遍历二叉树：
1）先序遍历二叉树：根 --> 左 --> 右
2）中序遍历二叉树：左 --> 根 --> 右
3）后序遍历二叉树：左 --> 右 --> 根
注意的是这里的先、中、后指的的根结点在遍历过程中的顺序，左孩子到右孩子的顺序不会变。
三、图形结构：
可以参考网址：https://blog.****.net/Ontheroad_/article/details/72739380，这里总结的很到位