数据结构简答知识点

前序序列、中序序列，唯一确定一棵二叉树。
(前序找出根节点，然后根据中序知道该根节点的左右子树，再依据左右子树的根来继续判断)
后序序列、中序序列，唯一确定一棵二叉树。
(后序找出根节点，然后根据中序知道该根节点的左右子树，再依据左右子树的根来继续判断)
前序序列、后序序列，不能确定一棵二叉树的
(无法判断根节点的左右子树，无法确定树)

二叉树的遍历：从根节点开始看。
例如先序遍历，在一棵树中先判断哪个节点为根节点输出，再判断左子节点。

 进入左子节点后，再在当前的树中判断哪个为根节点进行输出。
 如一个树的根左右均遍历完成。那么返回上一层。（书上147页）

树变森林，森林变树：左孩子，右兄弟。特指二叉树。（书上165页）（14年20题）
{
```
   1、树变森林：
  {
```
将右边的子树变为兄弟节点，放到同一深度，右子树与兄弟节点有同一个根节点
（如果有根节点将兄弟节点也连接到根节点上）。
将左边子节点仍为子节点。
（变完之后的森林中的兄弟节点之间的连线去掉）
}
```
 2、森林变树：将兄弟节点（同一平面上的节点）放在右子树上。将子节点仍为子节点。
```
}
AOE网，关键路径，关键活动。
Ve选择通往此点的最大的路径，Vl由Ve逆推减去最小的数值(代价最小的数值)，l-e为可推迟时间(推迟时间为0的点为关键点)
Ve为最早开始时间，Vl为最迟开始时间。
```
       a1
```
Va--------->Vb
e为活动最早开始时间，a1的e=Va的e
l为活动最迟开始时间，a1的l=（Vb的l-a1的代价）
最小生成树：有Kruskal算法和Prim算法。
Kruskal算法：依次连接权值最小的边，不能形成回路，连接N-1条边。
Prim算法：选一条边在它的直接相连的边中选取权值最小的边，不能形成回路，连接N-1条边。
Dijkstra算法：求节点V1到其他节点的最短路径。
选取最短的路径，不断进行比较选择。
二叉排序树：左子树上的节点的数都小于根节点的数，右子树上的节点的数都大于根节点的数。使用中序遍历后可得，从小到大的有序数列。
平衡二叉树：该节点的左右子树层数的绝对值相差不超过1。若不平衡就要进行相应旋转。
平衡二叉树的旋转：LL右单旋转，RR左单旋转，LR先左后右旋转，RL先右后左旋转。
（旋转：找到最低不平衡节点下两条线的左右，旋转时带上在连线上的三个点。）
B-树的构建规则：
中间结点有[m/2]≤ k ≤ m的孩子，[m/2]-1≤ k ≤ m-1的关键字。（【】选取大的数）
B-树始终为平衡多叉树，叶子节点在同一层。
当一层满了之后才向上升一层。
B-树的插入，删除操作始终在叶子节点处进行。
```
     插入：按照排序树左小右大规则，在叶子节点处插入。
     删除：叶子节点直接删除。非叶子节点选择左子树(右子树)中最右(左)下的结点中最后(最前)一个关键字。
```

哈希表表长n，构造（0~~n-1）的表，通常使用除留余数法，得出余数是那个数字放到那个表中。

     处理冲突：若表中已有元素。
  开放地址法：直接放于下一个空闲的表中。          
  二次探测再散列：加 1 的平方，加（-1）的平方，加 2 的平方.....(以此类推)。（14年第18题）