数据结构
2020-42
若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数≥2）的不等长编码，每个字符的编码均为二进制的 0、1 序列，最长为 L 位，且具有前缀特性。请回答下列问题：
1）哪种数据结构适宜保存上述具有前缀特性的不等长编码？
2）基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程。
3）简述判定某字符集的不等长编码是否具有前缀特性的过程。
答案
1）使用二叉树保存编码。每个编码对应一条从根到叶结点的路径，左、右分支分别表示 0、1，叶结点保存相应字符。
2）译码过程：从根节点开始，逐个读取 0/1 串的比特，根据比特值选择子节点（0 对应左子节点，1 对应右子节点），直到到达叶节点，输出对应字符；然后重置回根节点，重复此过程直到输入串结束。
3）判定过程同时也是构建二叉树的过程。初始时只有根结点，左右指针均为空。依次读入每个编码 C，从根开始按 C 的每一位沿相应分支向下；遇到空指针时创建新结点。处理过程中：
- 尚未扫描完
C就到达已有叶结点，说明某个已有编码是C的前缀，不具有前缀特性； - 扫描完
C时一个新结点都没有创建，说明C是某个已有编码的前缀，也不具有前缀特性； - 只有在处理
C的最后一位时创建新叶结点，才继续检查下一个编码。
若所有编码均通过上述检查，则该字符集的编码具有前缀特性。