树与二叉树
树与二叉树
1. 树的基本概念
- 树：n（n≥0）个结点的有限集，根结点、子树、叶子结点、度、层次、深度
- 森林：若干棵互不相交的树的集合
2. 二叉树的定义与特征
- 每个结点最多有两个子结点（左、右）
- 满二叉树、完全二叉树、二叉排序树、平衡二叉树
3. 存储结构
- 顺序存储：用数组存储完全二叉树
- 链式存储：每个结点有数据域、左/右指针域
4. 二叉树的遍历
- 前序遍历（根左右）
- 中序遍历（左根右）
- 后序遍历（左右根）
- 层序遍历（按层次）
5. 线索二叉树
- 利用空指针存储前驱/后继信息，提高遍历效率
6. 树、森林的存储与遍历
- 孩子表示法、双亲表示法、孩子兄弟表示法
- 森林与二叉树的转换
7. 应用
- 二叉搜索树、平衡二叉树、哈夫曼树与哈夫曼编码
习题
习题 1
简述树和二叉树的主要区别。
答案与解析
树每结点可有任意多子结点，二叉树每结点最多两个
习题 2
二叉树的前序、中序、后序遍历顺序分别是什么？
答案与解析
前序：根左右；中序：左根右；后序：左右根
习题 3
如何用数组存储完全二叉树？
答案与解析
根结点下标 1，左子 2i，右子 2i+1，父结点 i/2
习题 4
线索二叉树的作用是什么？
答案与解析
利用空指针存储前驱/后继，提高遍历效率
习题 5
哈夫曼树的主要应用是什么？
答案与解析
最优前缀编码、数据压缩
考研真题
真题 1
(2023 年 408 真题) 在由 6 个字符组成的字符集 S 中，各字符出现的频次分别为 3, 4, 5, 6, 8, 10，为 S 构造的哈夫曼编码的加权平均长度为（ ）。
A. 2.4 B. 2.5 C. 2.67 D. 2.75
答案与解析
答案：B
解析：
构造哈夫曼树的过程如下：
- 将频次从小到大排序：3, 4, 5, 6, 8, 10。
- 选取最小的两个频次 3 和 4，合并成新节点，权值为 7。
- 剩余频次为 5, 6, 7, 8, 10。选取最小的两个 5 和 6，合并成新节点，权值为 11。
- 剩余频次为 7, 8, 10, 11。选取最小的两个 7 和 8，合并成新节点，权值为 15。
- 剩余频次为 10, 11, 15。选取最小的两个 10 和 11，合并成新节点，权值为 21。
- 剩余频次为 15, 21。合并成根节点，权值为 36。
计算加权路径长度 (WPL)：
- 频次为 10 的字符编码长度为 2。
- 频次为 8 的字符编码长度为 2。
- 频次为 6 的字符编码长度为 3。
- 频次为 5 的字符编码长度为 3。
- 频次为 4 的字符编码长度为 3。
- 频次为 3 的字符编码长度为 3。
WPL = (10 _ 2) + (8 _ 2) + (6 _ 3) + (5 _ 3) + (4 _ 3) + (3 _ 3) = 20 + 16 + 18 + 15 + 12 + 9 = 90
加权平均长度 = WPL / 总频次 = 90 / (3+4+5+6+8+10) = 90 / 36 = 2.5
真题 2
(2018 年 408 真题) 已知某二叉树的中序遍历序列为 JGDHKBAELIMCF，后序遍历序列为 JGKHDBLMIEFCA，则其前序遍历序列为（ ）
A. ABDGHJKCEFILM B. ABDGJHKCEILMF C. ABDHKGJCEILMF D. ABDGJHKCEIMLF
答案与解析
答案：B
解析：
- 确定根节点： 后序遍历的最后一个元素是树的根节点。因此，根节点是
A。 - 划分左右子树： 在中序遍历中找到根节点
A，其左边的序列JGDHKB是左子树的中序遍历，右边的序列ELIMCF是右子树的中序遍历。 - 递归确定左子树：
- 左子树的后序遍历为
JGKHDB（在原后序遍历中，位于右子树后序遍历LMIEFCA之前的部分）。 - 左子树的根是
B（后序遍历JGKHDB的最后一个元素）。 - 在中序遍历
JGDHKB中，B的左边是JGDHK，右边为空。所以B没有右子树。 - 继续递归左子树
JGDHK，其后序遍历为JGKHDB（去掉B），根为D。 - 在中序遍历
JGDHK中，D的左边是JG，右边是HK。
- 左子树的后序遍历为