《数据结构（C语言版）》严蔚敏编著，第6-10章重点详略

树和二叉树

树有许多结点，每个结点拥有的子树数称为结点的度。

注意：树的度是树内各结点的度的最大值

二叉树

• 二叉树的性质

  • 在二叉树的第i层上至多有2^i-1个结点
  • 深度为k的二叉树至多有2^k-1个结点
  • 任何一棵二叉树，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀ = n₂+1

• 满二叉树：深度为k且有2^k-1个结点的二叉树

• 完全二叉树：每个结点都与满二叉树中结点对应的二叉树（满二叉树的不满形态）

• 完全二叉树的重要特性

  1. 具有n个结点的完全二叉树的深度为log₂n+1
  2. 结点为i的，双亲结点为i/2；2i大于结点总数的无左孩子，否则左孩子结点为2i；同理，右孩子结点为2i+1

二叉树存储结构

• 顺序存储结构：

• 链式存储结构：

不同形式 | | 结点结构| |
:-: | :-: | :-: | :-: | :-:
两个指针域 | lchild | data | rchild
三个指针域 | lchild | data |parent|rchild

遍历二叉树

• 如图所示二叉树：
  • 先序遍历（波兰式：先根=>左子树=>右子树）的先序序列为：-+a*b-cd/ef
  • 中序遍历（左子树=>中根=>右子树）的中序序列为：a+b*c-d-e/f(在根两端的结点肯定在不同左右子树上)
  • 后序遍历（逆波兰式：左子树=>右子树=>后根）的后序序列为：abcd-*+ef/- (确定最末是根)
• 任意两个序列即可确定一棵二叉树

树和森林

树的存储结构

• 双亲表示法：一组连续空间存储树的结点，同时在每个结点中附设一个指示器只是其双亲结点在链表中的位置。

• 孩子表示法：
  • 把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构。
  • 树的每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，每个指针指向一棵子树的根结点。其中结点同构的表示方法，因为树中有很多结点的度小于d，链表中会有很多空链域造成浪费。有n个结点度为k的树中必有n(k-1)+1个空链域。

• 孩子兄弟表示法：又称二叉树表示法/二叉链表表示法，即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。

1
2
3
4

typedef struct CSNode{
  ElemType data;
  struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree

森林与二叉树的转换

酌情填坑

哈夫曼树

• 有n个权值[w1, w2, w3,…,wn]，构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，其中带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼树。
• 构造哈夫曼树：
  1. 在权值集合中选择最小的两个权值构造二叉树，新二叉树的根结点的权值为左右子树上根结点的权值之和
  2. 在集合中删除这两个权值，同时将新权值加入集合中
  3. 重复以上两步，直到集合中只含一个权值。这棵树就是哈夫曼树。
• 哈夫曼编码：设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码就称为哈夫曼编码。(可理解为：使用频率最高的字符要求在树的层次越浅，使用频率最低的字符在树最深的层次上)

例题

已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11。试设计哈夫曼编码。

解：设权w = {5, 29, 7, 8, 14, 23, 3, 11}。

图

术语

• 图分为有向图和无向图
• 有(1/2)*n(n-1)条边的无向图称为完全图；有n(n-1)条弧的有向图称为有向完全图。(完全图之间各顶点连通)
• 顶点v的度是和v相关联的边的数目，其中有向图又分别细分为入度和出度。
• 子图：能重叠在原图上的部分图
• 无向图中如果任意两个顶点都是连通的，则称其为连通图，连通分量指的是无向图中不同的极大连通子图；类似的，在有向图中任意两个顶点互相之间都有路径，则称为强连通图，有向图中不同的极大强连通子图称作有向图的强连通分量。
• 一个连通图的生成树是一个极小连通子图，含有图中全部顶点，但只有足以构成一棵树的n-1条边。(可以理解成图中不存在环，不存在冗余的边)
• 如果一个图有n个顶点和小于n-1条边，则是非连通图；多于n-1条边，则一定有环。

图的存储结构

数组表示法

邻接矩阵：以二维数组表示有n个顶点的图

1
2
3
4
5

if(i,j连通){
  A[i][j] = 权值;//如果是无向图，需要再多加一条语句：A[j][i] = 权值;
}else{
  A[i][j] = ∞;
}

邻接表

• 是图的一种链式存储结构，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（有向图就是以顶点vi为尾的弧）。
• 每个结点由3个域组成：[int adjvex邻接点域指示与顶点vi邻接的点,* nextarc链域指针指示下一条边或弧的结点, info数据域存储权值等信息]

​

• 对于有向图来说，也有邻接表，记录顶点的出度；还有逆邻接表，记录顶点的入度。

图的遍历

• **深度优先搜索 (Depth First Search)**：类似于树的先根遍历。从图中一个顶点出发，访问此顶点，依次从该点未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到。其余未被访问的顶点重复上述过程，直到图中所有顶点都被访问为止。
• **广度优先搜索(Breadth First Search)**：类似于树的按层次遍历的过程。从图中一个顶点出发，访问此顶点，依次访问该点的各个邻接点，然后分别从这些邻接点出发依次访问它们的邻接点。

图的连通性

• 最小生成树问题：最小生成树小结
• Prim算法时间复杂度为O(n²)，n为顶点。Kruskal时间复杂度为(elog_e)，其中e为边数，更适合求边稀疏的最小生成树。

有向无环图

• 拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序，称为拓扑排序。不允许有环。(例：《软件专业的学生必须学习的课程》 先决条件)

• 进行拓扑排序（AOV Activity On Vertex 顶点表示活动的网）：

  1. 在有向图中选一个没有前驱的顶点且输出
  2. 从图中删除该顶点和它的后继弧
  3. 重复，直到所有顶点输出

• 关键路径(AOE Activity On Edge 边表示活动的网)：路径长度最长的路径，其上均是关键活动。

最短路径

源点到其余顶点的最短路径

Dijkstra算法

(待补)

每一对顶点间的最短路径

Floyd算法

(待补)

查找

折半查找(Binary Search)

先确定待查记录所在的范围，以处于区间中间位置的关键值和待查数比较，若不等，逐步缩小范围直到找到或查找区间的大小小于0为止。

代码实现

1
2
3
4
5
6
7
8
9
10

public static int binSearch(int nums[], int key) {
    int low = 0, high = nums.length - 1;
    while (low <= high){
        int mid = (low + high)/2;
        if(nums[mid] == key) return mid;
        else if(nums[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

二叉排序树

也称二叉查找树。是动态查找表，表结构本身是在查找过程中动态生成的。

二叉排序树有如下性质：

1. 左子树上所有结点的值均小于它的根结点的值
2. 右子树上所有结点的值均大于它的根结点的值
3. 左右子树也分别为二叉排序树

平衡二叉树

也称AVL树。

平衡二叉树有如下性质：

1. 左子树和右子树都是平衡大叉树
2. 左子树和右子树的深度之差绝对值不超过1

二叉树上结点的平衡因子定义为该结点的左子树的深度减去右子树的深度，平衡因子只可能是-1，0，1

B-树

是一种平衡的多路查找树，在文件系统中很有用。

一棵m阶的B-树是一棵具有如下特性的m叉树：

1. 树中每个结点至多有m棵子树
2. 根结点至少有两棵子树
3. 除根之外的所有非终端结点至少有m/2棵子树
4. 所有叶子结点都出现在同一层次上，且不带信息，可以看作是外部结点或查找失败的结点，实际上这些结点不存在。

B+树

B+树是应文件系统所需而出的一种B-树的变型树。

一棵m阶的B+树和m阶的B-树差异在于：

1. 有n棵子树的结点中含有n个关键字
2. 所有的叶子结点中包含了全部的关键字信息
3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树中的最大/最小关键字

哈希表

不经过任何比较，一次存取便能得到所查记录

处理冲突：

1. 开放定址法：自动往后退一位
2. 再哈希法：再次进行哈希计算
3. 链地址法：把所有关键字为同义词的记录存储在同一先行链表中
4. 建立一个公共溢出区：一旦发生冲突都填入溢出表

内部排序

插入排序

• 直接插入排序：将一个记录插入到已排好序的有序表中
• 希尔排序（缩小增量排序）：先将整个待排记录序列分隔成为若干子序列分别进行直接插入排序，等到整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。子序列的构成不是简单的逐段分割，而是将像个某个”增量”的记录组成一个子序列。

冒泡排序

过程

降低一个记录的关键字和第二个记录的关键字进行比较，若为逆序则交换这两个记录，然后比较第二个记录和第三个记录的关键字，以此类推，直到第n-1个记录和第n个记录的关键字进行过比较为止。这是第一趟冒泡排序，其结果使得最大的数被安置到最后一个记录的位置上。

然后进行第二趟排序，结果将第二大的数字安置到倒数第二的位置上。

本质上是不断将大数沉淀到后位。

动图展示：BUBBLE SORT

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <stdio.h>
int main()
{
  int a[100],i,j,t,n;
    scanf("%d",&n);  //输入一个数n，表示接下来有n个数
    for(i=1;i<=n;i++)  //循环读入n个数到数组a中
        scanf("%d",&a[i]);
    //冒泡排序的核心部分
    for(i=1;i<=n-1;i++) //n个数排序，只用进行n-1趟
    {
        for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归位的数，想一想为什么到n-i就可以了。
        {
            if(a[j]<a[j+1]) //比较大小并交换
            {  t=a[j]; a[j]=a[j+1]; a[j+1]=t;  }
        }
    }
    for(i=1;i<=n;i++)  //输出结果
        printf("%d ",a[i]);
    getchar();getchar();
    return 0;
}

快速排序

过程

设立数组第一个数为starter，在首尾分别设立两个指针i, j，j向前找到第一个小于starter的与i找到的大于starter的数互换，最后相遇的时候，把starter放到相遇点上，也就是在starter之前是小于starter的无序集合，在starter之后是大于starter的无序集合。

待排记录被分成了独立的两部分，接下去分别对这两部分按照之前的方式再进行排序，直到数组有序为止。

动图展示：QUICK SORT

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public void quickSort(int[] nums, int left, int right){
    int i, j, starter;
    if(left > right)return;
    starter = nums[left];
    i = left;
    j = right;
    while (i != j){
        while (nums[j] <= starter && i < j)j--;
        while (nums[i] >= starter && i < j)i++;
        if(i < j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    nums[left] = nums[i];
    nums[i] = starter;

    quickSort(nums, left, i-1);
    quickSort(nums, i+1, right);
}

堆排序

完全二叉树中所有非终端结点的值均不大于(如果是最大生成堆就是不小于)其左右孩子结点的值。在输出堆顶元素后，使得剩余n-1个元素的序列重新又建成一个堆，继续输出堆顶元素，如此反复执行，就能得到一个有序序列，这个过程就是堆排序。

归并排序

初始序列含有n个记录，可以分为长度为1的n个子序列，然后两两排序归并，得到n/2个长度为2或1的有序子序列，继续两两归并，直到得到一个长度为n的有序序列为止。