1：数据结构中有4中基本结构：
1.1：集合结构
集合中的元素有三个特征：
1).确定性（集合中的元素必须是确定的）
2).互异性（集合中的元素互不相同。例如：集合A={1，a}，则a不能等于1）
3).无序性（集合中的元素没有先后之分），如集合{3,4,5}和{3,5,4}算作同一个集合。
1.2：线性结构
常用的线性结构有：线性表(包括顺序表和链表)，数组，栈，队列，双队列。
1.3：树形结构
1.4：图状结构
2：树的相关概念
2.1 树的结点的度
结点拥有的子树数目称为结点的度。
如下图所示：
2.2 结点关系
结点子树的根结点为该结点的孩子结点。相应该结点称为孩子结点的双亲结点。
图2.2中，A为B的双亲结点，B为A的孩子结点。
同一个双亲结点的孩子结点之间互称兄弟结点。
图2.2中，结点B与结点C互为兄弟结点。
2.3 结点层次
从根开始定义起，根为第一层，根的孩子为第二层，以此类推。
图2.3表示了树的层次关系
2.4 树的深度
树中结点的最大层次数称为树的深度或高度。图2.3所示树的深度为4。
3：二叉树的相关概念
3.1 二叉树有以下特点：
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
3.2 斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
3.3 满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
满二叉树的特点有：
1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
2）非叶子结点的度一定是2。
3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
3.4 完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
如下图所示：
3.5 二叉树遍历分为：前序遍历，中序遍历，后序遍历，层次遍历
3.5.1 前序遍历
前序遍历通俗的说就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图3.5所示二叉树访问如下：
从根结点出发，则第一次到达结点A，故输出A;
继续向左访问，第一次访问结点B，故输出B；
按照同样规则，输出D，输出H；
当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；
I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；
向E左子树，故输出J；
按照同样的访问规则，继续输出C、F、G；
图3.5所示二叉树的前序遍历输出为：
ABDHIEJCFG
3.5.2 中序遍历
中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图3.5所示二叉树中序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；
H右子树为空，则返回至D，此时第二次到达D，故输出D；
由D返回至B，第二次到达B，故输出B；
按照同样规则继续访问，输出J、E、A、F、C、G；
图3.5所示二叉树的中序遍历输出为：
HDIBJEAFCG
3.5.3 后序遍历
后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。
图3.5所示二叉树后序访问如下：
从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；
到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H；
H右子树为空，则返回至H，此时第三次到达H，故输出H；
由H返回至D，第二次到达D，不输出D；
继续访问至I，I左右子树均为空，故第三次访问I时，输出I；
返回至D，此时第三次到达D，故输出D；
按照同样规则继续访问，输出J、E、B、F、G、C，A；
图3.5所示二叉树的后序遍历输出为：
HIDJEBFGCA
3.5.4 层次遍历
层次遍历就是按照树的层次自上而下的遍历二叉树。针对图3.5所示二叉树的层次遍历结果为：ABCDEFGHIJ
3.5.5 遍历常考考点
对于二叉树的遍历有一类典型题型。
1）已知前序遍历序列和中序遍历序列，确定一棵二叉树。
例题：若一棵二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，请画出这棵二叉树。
分析：前序遍历第一个输出结点为根结点，故A为根结点。早中序遍历中根结点处于左右子树结点中间，故结点A的左子树中结点有CB，右子树中结点有EDF。
如下图所示：
按照同样的分析方法，对A的左右子树进行划分，最后得出二叉树的形态如下图所示：
2）已知后序遍历序列和中序遍历序列，确定一棵二叉树。
后序遍历中最后访问的为根结点，因此可以按照上述同样的方法，找到根结点后分成两棵子树，进而继续找到子树的根结点，一步步确定二叉树的形态。
注意：已知前序遍历序列和后序遍历序列，不可以唯一确定一棵二叉树。
4：哈希表(散列表)的介绍
哈希表是一种非常重要的数据结构, 几乎所有的编程语言都有直接或者间接的应用这种数据结构.
哈希表通常是基于数组进行实现的, 但是相对于数组, 它也很多的优势:
它可以提供非常快速的插入-删除-查找操作
无论多少数据, 插入和删除值需要接近常量的时间: 即O(1)的时间级. 实际上, 只需要几个机器指令即可
哈希表的速度比树还要快, 基本可以瞬间查找到想要的元素
哈希表相对于树来说编码要容易很多.
哈希表相对于数组的一些不足:
哈希表中的数据是没有顺序的, 所以不能以一种固定的方式(比如从小到大)来遍历其中的元素.
通常情况下, 哈希表中的key是不允许重复的, 不能放置相同的key, 用于保存不同的元素.
那么, 哈希表到底是什么呢?
似乎还是没有说它到底是什么.
这也是哈希表不好理解的地方, 不像数组和链表, 甚至是树一样直接画出你就知道它的结构, 甚至是原理了.
它的结构就是数组, 但是它神奇的地方在于对下标值的一种变换, 这种变换我们可以称之为哈希函数, 通过哈希函数可以获取到HashCode.
