#1024程序员节|正文#
六、树和二叉树
6.1 树的基本概念
| 描述 | 结果 |
|---|---|
| 结点的度 | 子结点的个数 |
| 树的度 | 最大结点的度 |
| 叶子结点 | 没有子结点的结点 |
| 内部结点 | 除根结点和叶子结点外的结点 |
| 父节点 | 有子结点的结点 |
| 子节点 | 有父结点的结点 |
| 兄弟节点 | 有同一个父结点的结点 |
| 层次 | 4层 |
6.2 二叉树的基本概念
二叉树的重要特性：
1、在二叉树的第i层上最多有 2 i − 1 2^{i-1} 2i−1个结点（i>=1)
2、深度为k的二叉树最多有 2 k − 1 2^k-1 2k−1个节点（k>=1)
3、对任何一棵二叉树，如果其叶子结点数为 n 0 n_0 n0,度数为2的结点数为 n 2 n_2 n2,那么 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1
4、如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到 l o g 2 n + 1 log_2^n+1 log2n+1层，每层从左到右，则对任一节点i(1<=i<=n)有：
如果有i=1,则结点i无父结点，是二叉树的根；如果i>1,则父结点是 ⌊ i 2 ⌋ \lfloor{\frac{i}{2}}\rfloor ⌊2i⌋;
如果2i>n,则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i;
如果2i+1>n,则结点i无有子节点，否则，其右子节点是结点2i+1.
6.3 二叉树的遍历
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
层次遍历：按层从左至右，从上到下遍历
| 前序遍历 | 12457836 |
|---|---|
| 中序遍历 | 42785136 |
| 后序遍历 | 48752631 |
| 层次遍历 | 12345678 |
6.4 反向构造二叉树
有前序序列为
ABHFDECG,中序为HBEDFAGC构造二叉树
6.5 树转二叉树
孩子结点一左子树结点
兄弟结点一右孩子结点
6.6 查找二叉树（二叉树排序）
特点：左孩子小于根，右孩子大于根，例如序列：89,48,56,112,51,20
插入节点：
- 若该键值结点已存在，则不再插入，如：48
- 若查找二叉树为空树，则以新节点为查找二叉树
- 将要插入结点键值与插入后父结点键值比较，就能确定新节点是父结点的做子节点，还是右子结点。
删除结点：
- 若待删除结点是叶子结点，则直接删除
- 若待删除接地那只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，如：56
- 若待删除的节点p有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s,结点s必属于上述 1 ,2,情况之一，如89
6.6 构造霍夫曼树（最优）
树的路径长度
权
带权路径长度
树的带权路径长度
例：1，2,4,8
第一个权值：
2
∗
2
+
4
∗
3
+
8
∗
3
+
1
∗
1
=
41
2*2+4*3+8*3+1*1=41
2∗2+4∗3+8∗3+1∗1=41
第二个权值： 4 ∗ 2 + 1 ∗ 3 + 2 ∗ 3 + 8 ∗ 2 = 25 4*2+1*3+2*3+8*2=25 4∗2+1∗3+2∗3+8∗2=25
例：假设有一组权值5,29,7,8,14,23,3,11请尝试构造哈夫曼树
6.7 线索二叉树
-
为什么要有线索二叉树
-
线索二叉树的概念A
-
线索二叉树的表示
-
如何将二叉树转化为线索二叉树
### 6.8 平衡二叉树
平衡二叉树提出的原因？
例：对数列{1,5,9,8,39,73,88}构造排序二叉树，可以构造出多棵排序二叉树，可以构造出多棵形式不同的排序二叉树。
**定义：**任意结点的左右子树深度相差不超过1，每节点的平衡度只能为 -1,0 或1
七、图
7.1 基本概念
1、有向图
2、无向图
3、完全图：在无向图中，若每对顶点之间都有一条边相连，则称为完全图。在有向图中，若每对顶点之间都有两条有向边相互连接，则称为完全图。
4、度，入度，出度
7.2 存储结构（邻接矩阵）
用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素
R
i
j
R_{ij}
Rij定义为：
R
i
j
=
{
1
若顶点
i
到顶点
j
有邻接边
0
顶点
i
到顶点
j
没有邻接边
}
R_{ij}= \begin {Bmatrix} 1 \quad 若顶点i到顶点j有邻接边 \\ 0 \quad 顶点i到顶点j没有邻接边 \end{Bmatrix}
Rij={1若顶点i到顶点j有邻接边0顶点i到顶点j没有邻接边}
R 1 = [ 0 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 ] R_1=\begin{bmatrix} \quad 0 \quad 1 \quad 1 \quad 0 \quad 0\quad \\ \quad 1 \quad 0 \quad 1 \quad 1 \quad 1\quad \\ \quad 1 \quad 1 \quad 0 \quad 1 \quad 1\quad \\ \quad 0 \quad 0 \quad 1 \quad 0 \quad 1\quad \\ \quad 0 \quad 0 \quad 1 \quad 1 \quad 0\quad \\ \end{bmatrix} R1= 0110010111110110010100110
7.3 存储结构（邻接表）
首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。
7.4 图的遍历
| 遍历方法 | 说明 | 示例 | 图例 |
|---|---|---|---|
| 深度优先 | 1. 首先访问出发顶点V 2.依次从V出发搜索V的任意一个邻接点W; 3.若W未访问过，则从该点出发继续深度优先遍历，它类似于树的深度优先遍历。 | V 1 , V 2 , V 4 , V 8 , V 5 , V 3 , V 6 , V 7 V_1,V_2,V_4,V_8,V_5,V_3,V_6,V_7 V1,V2,V4,V8,V5,V3,V6,V7 |  |
| 广度优先 | 1.首先访问出发顶点V 2.然后访问与顶点V邻接的全部未访问顶点W、X、Y… 3.然后再依次访问 W、X.Y...邻接的未访问的顶点； | V 1 , V 2 , V 3 , V 4 , V 5 , V 6 , V 7 , V 8 V_1,V_2,V_3,V_4,V_5,V_6,V_7,V_8 V1,V2,V3,V4,V5,V6,V7,V8 |  |
7.5 拓扑排序
我们把有向边表示活动之间开始的先后关系。这种有向图称为用定点表示活动网络，简称AOV网路。
上图的拓朴序列有：02143567，01243657，02143657，01243567。
7.6 最小生成树（普利姆算法）
先找一个最小的权值（如：A：200），然后在根据A关联的边，查找最小的路径权值，依次。。。
7.7 最小生成树（克鲁斯卡尔算法）
每次查找最小的路径权值，只要不形成闭环，就一直找最小
八、查找
8.1 基本概念
查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
查找长度：在查找运算中，需要对比关键字的次数称为查找长度。
平均查找长度（ASL：Average Search Length):所有查找过程中进行关键字的比较次数的平均值。
### 8.2 顺序查找
顺序查找：又称“线性查找”，通常用于线性表。
算法思想：从头到jio挨个找（或者反过来也OK）
查找目标：43
一般情况下，
c
i
=
n
−
i
+
1
c_i=n-i+1
ci=n−i+1,因此在此等概率情况下，顺序查找成功的平均查找长度为
A
S
L
s
s
=
∑
i
=
1
n
p
i
c
i
=
1
n
∑
i
=
1
n
(
n
−
i
+
1
)
=
n
+
1
2
ASL_{ss}=\sum_{i=1}^n p_ic_i = \frac{1}{n}\sum_{i=1}^n(n-i+1)=\frac{n+1}{2}
ASLss=i=1∑npici=n1i=1∑n(n−i+1)=2n+1
8.3 折半查找
折半查找又称为”二分查找“，仅适用用有序的顺序表。
例题：请给出在含有12个元素的有序表{1,4,10,16,17,18,23,29,33,40,50,51}中二分查找关键字17的过程。
折半查找在查找成功时关键字的比较次数最多为 ⌊ l o g 2 n ⌋ + 1 \lfloor log_2n \rfloor +1 ⌊log2n⌋+1次，折半查找的时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n).
8.4 分块查找
特点：快内无序，块间有序
第一步在索引表中确定待查记录所在的块，第二步在快内顺序查找。
8.5 哈希表（散列表）
散列表（Hash Table),又称为哈希表。是一种数据结构，特点是数据元素的关键字与其存储地址直接相关。
例：有一堆数据元素，关键字分别为{19,14,23,1,68,20,84,27,55,11,10,79},散列函数 H(key)=key%13
19%13=6
14%13=1
23%13=10
1%13=1
若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”，通过散列函数确定的位置已经存放了其他元素，则成这种情况为“冲突。
解决冲突的方法：
- 开放地址法
- 链地址法
- 再哈希法
- 建立一个公共溢出区
九、排序
9.1 基本概念
1、排序：就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。
稳定与不稳定 ：排序前后相同元素的位置没有改变称为稳定排序，反之，改变则称为不稳定排序。
内部排序与外部排序
2、排序方法分类：
| 方法名 | 分类 |
|---|---|
| 插入类排序 | 直接插入排序、希尔排序 |
| 交换类排序 | 冒泡排序、快速排序 |
| 选择类排序 | 简单选择排序、堆排序、归并排序、基数排序 |
9.2 直接插入排序
算法思想：每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中直到全部记录插入完成。
### 9.3 希尔排序
算法思想：先将待排序表分割成若干形如
L
[
i
,
i
+
d
,
i
+
2
d
,
.
.
.
,
i
+
k
d
]
L[i,i+d,i+2d,...,i+kd]
L[i,i+d,i+2d,...,i+kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d,重复上述过程，直到d=1为止。
9.4 冒泡排序
算法思想：从后往前（或从前往后）两两比较相邻元素的值，若逆序（即A[i-1]>A[i])则交换它们，直到序列比较完。称这样的过程为“一趟”冒泡排序。
9.5 快速排序
算法思想：在待排序表L[1…n]中人去一个元素pivot作为枢轴（或基准，通常去首元素），通过一趟排序将待排序序表换分为独立的两个部分，L[1…k-1]和L[k+1…n],使得L[1…k-1]中的所有元素都小于pivot，L[k+1…n]中的元素都大于等于pivot，则pivot放在其最终位置L[k]上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直到每部分内只有一个元素或为空为止，即所有元素放在了其最终位置上。 
### 9.7 简单选择排序
算法思想：每一趟在待排序元素中选取关键字最小的元素加入有序子序列。
9.7 堆排序
设有n个元素的序列，{k1,k2,…kn},当且仅当满足下述关系之时，称之为堆。
（1） k i < = k 2 i ; 且 k i < = k 2 i + 1 k_i<=k_{2i} ;且ki<=k_{2i+1} ki<=k2i;且ki<=k2i+1
(2)） k i > = k 2 i ; 且 k i > = k 2 i + 1 k_i>=k_{2i} ;且ki>=k_{2i+1} ki>=k2i;且ki>=k2i+1
其中（1）称为小顶堆，（2)称为大顶堆
9.8 归并排序
算法思想：把两个或多个已经有序的序列合并成一个。
9.9 基数排序
基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数的选择和关键字的分解是根据关键字的类型来决定的例如：关键字是十进制数，则按个位十位来分解。
9.10 评价指标
期待程序员专属日
1024~~~~~~~~~~~~~~~~~~~~~~~~~~————————————————————————
————————————-————————1024~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
**~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~1024————————————-————————
