type
status
date
slug
summary
tags
category
icon
password
前言
算法与数据结构第三次作业，章节范围 树和二叉树
一、填空题
1. 二叉树和树的主要差别是（ 二叉树每个结点最多有两棵子树，且有左右之分 ），（ 树每个结点可以有多棵子树，且子树无左右顺序之分 ）。
2. 深度为 k 的完全二叉树至少有（ ）个结点，至多有（ ）个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是（ ）。
3. 一棵二叉树的第 i ( i ≥ 1 ) 层最多有（ ）个结点；一棵有 n（ n ＞ 0 ）个结点的满二叉树共有（ ）个叶子结点和（ ）个非叶子结点。
板书解析
<ins/>
二、画图计算题
1. 假设一棵二叉树的层序序列是 A B C D E F G H I J 和中序序列是 D B G E H J A C I F ，画出该二叉树。
2. 设给定权集 w = { 2, 3, 4, 7, 8, 9 } ，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。
WPL计算:
- 节点2: 路径长度4，贡献 2×4 = 8
- 节点3: 路径长度4，贡献 3×4 = 12
- 节点4: 路径长度3，贡献 4×3 = 12
- 节点7: 路径长度2，贡献 7×2 = 14
- 节点8: 路径长度2，贡献 8×2 = 16
- 节点9: 路径长度2，贡献 9×2 = 18
总WPL = 8 + 12 + 12 + 14 + 16 + 18 = 80
链接课本
3. 已知一棵树的先根和后根遍历次序如下：
先遍历：a b e f g c d h i
后根遍历：e f g b c h i d a
试画出此树，并画出转化后的二叉树，以及此二叉树的后序线索二叉树。
a）原始树：
b）转化后的二叉树：
c）后序线索二叉树：
tag=0为儿子，tag=1为线索
4.已知一棵度为m的树中有n_1个度为1的结点，n_2个度为2的结点，…，n_m个度为m的结点，问该树中有多少个叶子结点？
5.给出树的先根序、后根序遍历序列；将树转化为二叉树；给出二叉树的先序、中序、后序序列；画出二叉树对应的中序线索二叉树。
1）树：
- 先根遍历序列：A B E F G C D H I
- 后根遍历序列：E F G B C H I D A
2）转化：
3）二叉树：
- 先序序列： A B E F G C D H I
- 中序序列： E F G B C H I D A
- 后序序列： G F E I H D C B A
4）中序线索二叉树：
6.给出森林的先根序、后根序遍历序列；将森林转化为二叉树，画出最后得到的二叉树的二叉链表。
1）森林：
- 先根序遍历序列 A B C E D F G H I J
- 后根序遍历序列 B E C D A G H F J I
2）二叉树：
3）二叉链表：
7.假定电文中仅出现8个字母，出现频率分别为{0.02, 0.03, 0.06, 0.07, 0.10, 0.19, 0.21, 0.32}，求每个字母的哈夫曼编码。若用0-7的二进制表示为等长编码，如何比较两种编码的优缺点。
频率 | 哈夫曼编码 |
0.02 | 10000 |
0.03 | 10001 |
0.06 | 1001 |
0.07 | 1010 |
0.10 | 1011 |
0.19 | 00 |
0.21 | 01 |
0.32 | 11 |
WPL = 261
哈夫曼编码在频率差异大时显著提升压缩率，适合存储或带宽敏感场景；
等长编码简单高效，适用于实时处理或频率均匀的情况。
8.已知某系统在通讯联络中只给出现八种字符，其概率分布分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，试求哈夫曼树，并设计哈夫曼编码（课本）。
1）哈夫曼树：
2）哈夫曼编码：
9.将算术表达式（ ( a + b ) + c * ( d + e ) )
* ( g + h ) 转化为二叉树，并写出后序遍历的序列（后缀表达式）。
1）二叉树：
2）后序遍历的序列：
<ins/>
三、简答题
What is Huffman tree? Give the characteristics of Huffman code? 什么是哈夫曼树？请给出哈夫曼编码的特性？
简洁版答案
定义：有n个权值的集合：{W₁，W₂，…，Wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为Wi，则其中带权路径长度WPL最小的二叉树称为最优二叉树或哈夫曼树
特性：平均码长最短；是前缀码
超长版答案
哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最短的二叉树。
其定义如下：给定一组带有权重（通常为频率或概率）的叶子节点，通过哈夫曼算法构建一棵二叉树，使得树的带权路径长度（WPL）最小。哈夫曼树在编码理论、数据压缩等领域有广泛应用，典型的如哈夫曼编码。
哈夫曼编码（Huffman Code）的特性：
- 最优前缀特性（Prefix Property）：哈夫曼编码是一种前缀码，即任意一个字符的编码都不会是另一个字符编码的前缀。这一特性保证了编码的唯一可译性，使得在解码过程中不会出现歧义。
- 无歧义性（Unambiguous）：由于具有最优前缀特性，哈夫曼编码能够被唯一地解码。在解码时，可以通过哈夫曼树从根节点开始，根据编码的每一位（0或1）向左或向右移动，直到到达叶子节点，从而确定对应的字符。
- 编码效率高（High Efficiency）：哈夫曼编码根据字符出现的频率进行编码，频率高的字符分配较短的编码，频率低的字符分配较长的编码。这样可以使得编码后的数据长度最短，达到最优压缩效果。
- 唯一性（Uniqueness）：虽然哈夫曼编码的构建过程可能因左右子树的选择不同而产生不同的编码方案，但每种方案的带权路径长度相同，且每个字符的编码都是唯一的。
四、术语表示题
Give the English of the terminologies. 树、森林、二叉树、遍历二叉树、线索二叉树、哈夫曼树（最优二叉树）、前缀码、编码、解码。
树：Tree
森林：Forest
二叉树：Binary Tree
遍历二叉树：Traversing Binary Tree
线索二叉树：Threaded Binary Tree
哈夫曼树（最优二叉树）：Huffman Tree(Optimal Binary Tree)
前缀码：Prefix Code
编码：Encode
解码：Decode
<ins/>
- 作者:EageYren
- 链接:https://eageyren.edu.deal/learning/algorithm3
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
