【课程大纲】
1_0 课程简介 共7页.pptx
2_1绪论 共32页.pptx
2_2线性表-顺序表 共12页.pptx
2_3线性表-链表 共43页.pptx
3_1栈和队列 共29页.pptx
3_2递归和非递归 共22页.pptx
4_1串 共18页.pptx
5_1 数组 共19页.pptx
6_1二叉树 共19页.pptx
6_2森林和哈夫曼树 共15页.pptx
7_1 图（存储、遍历、连通） 共49页.pptx
7_2图（拓扑排序、关键路径、最短路径） 共52页.pptx
8_1集合与查找（静态查找、哈希、二叉排序树、平衡二叉树） 共28页.pptx
8_2集合与查找（B-树） 共12页.pptx
9内排序 共25页.pptx
### 数据结构与算法基础课程知识点总结
#### 一、课程概览
本课程是一门关于数据结构与算法的基础课程，涵盖了计算机科学中的核心概念和技术。课程总共分为九个部分，覆盖了从基本的数据结构到高级的算法设计方法，旨在帮助学生理解和掌握数据结构的基本原理及其在实际编程中的应用。
#### 二、二叉树与森林
##### 1. 二叉树的遍历
- **前序遍历**：按照“根节点—左子树—右子树”的顺序访问各个节点。
- **中序遍历**：按照“左子树—根节点—右子树”的顺序访问各个节点。
- **后序遍历**：按照“左子树—右子树—根节点”的顺序访问各个节点。
- **层次遍历**：按层从上到下，从左至右访问所有节点。
例如，在给定的二叉树 `a(b(d, e(g)), c(f))` 中，其遍历结果分别为：
- 前序遍历：`abdgcefh`
- 中序遍历：`dgbaehfc`
- 后序遍历：`gdbehfca`
- 层次遍历：`abcdgef`
##### 2. 线索化二叉树
- **定义**：通过改造二叉树中的空指针域，使其指向其相邻节点（前驱或后继），从而使得在不使用递归的情况下也能实现二叉树的遍历。
- **中序线索化二叉树的遍历**：通过对二叉树进行中序遍历，并在线索化过程中修改空指针指向来完成。
- **二叉树的中序线索化**：通过对二叉树进行一次中序遍历，将遍历过程中的每个节点的前驱节点的右指针指向当前节点，同时将当前节点的左指针指向其前驱节点，从而实现中序线索化。
##### 3. 二叉树的应用实例
- **表达式运算树**：例如，表达式 `A + (B * (C - D)) / E - F * (G + H)` 可以用二叉树来表示，其中每个内部节点代表一个操作符，每个叶子节点代表一个操作数。这种树有助于计算表达式的值。
#### 三、森林、树与二叉树之间的转换
##### 1. 树的物理结构
- **父链结构**：每个节点包含一个指向其父节点的链接。
- **子链结构**：每个节点包含多个指向其子节点的链接。
- **子链-兄弟链结构**：除了指向子节点的链接外，还包括指向同级节点（兄弟节点）的链接。
##### 2. 树与森林
- **树**由一个根节点加上其所有子树构成。
- **森林**是由多个树组成的集合。
##### 3. 树与二叉树之间的转换
- **树转二叉树**：将树中每个节点的所有子节点连接到该节点的右子节点，形成一棵二叉树。每个子节点的右边添加一个虚拟的右子节点，直到没有更多的子节点为止。
- **二叉树转树**：对于给定的二叉树，将其右子节点视为兄弟节点，左子节点视为子节点，从而还原成原来的树结构。
#### 四、哈夫曼树
##### 1. 哈夫曼树（最优二叉树）
- **定义**：哈夫曼树是一种特殊的二叉树，它具有最小的带权路径长度（WPL）。每个叶子节点都有一个权重，表示出现的频率。
- **哈夫曼树的总权值**：通过计算所有叶子节点的权重乘以其深度的总和得到。
例如，考虑以下哈夫曼树：
```
75
/ \
36 39
/ \ / \
12 24 14 25
/ \ / \
5 7 8 6 14
/ \
3 11
```
此树的总权值为：`5*3 + 7*3 + 3*4 + 11*4 + 8*3 + 6*4 + 12*2 + 24*2 + 14*3 + 25*3 = 369`。
##### 2. 哈夫曼算法
- **初始化**：将每个叶子节点视为一个单独的二叉树。
- **重复步骤**：
- 选择两个根节点权值最小的二叉树；
- 创建一个新的根节点；
- 将这两个二叉树分别作为新根节点的左右子树；
- 新根节点的权值为其左右子树根节点权值之和；
- 重复以上步骤，直至只剩下一个二叉树。
##### 3. 哈夫曼编码
- **定长编码与变长编码**：定长编码是每个字符都使用相同长度的编码，而变长编码则是不同字符可能使用不同长度的编码。
- **最优变长编码**：哈夫曼编码是一种最优的变长编码方式，它能够有效地压缩数据。
例如，考虑以下哈夫曼树：
```
75
/ \
36 39
/ \ / \
12 24 14 25
/ \ / \
5 7 8 6 14
/ \
3 11
```
对应的哈夫曼编码为：
- `a`: 100
- `b`: 110
- `c`: 111
- `d`: 101
- `e`: 0
这种编码方式可以用于高效地传输数据。例如，“abe bace ddec”对应的编码为：“1000110100011101011010111”，接收方可以根据哈夫曼树解码出原始数据。
