T42 前缀特性 不等长编码

• 适合保存前缀特性编码的数据结构
  • 哈夫曼树: 构建二叉树，叶子结点表示字符，路径表示编码
• 译码过程
  • 对于给定01串，从根结点开始遍历哈夫曼树
  • 遇到0向左子树移动，遇到1向右子树移动
  • 到达叶子结点时，输出对应字符，并返回根结点继续译码
• 判定前缀特性:(构建哈夫曼树的过程)
  • 初始二叉树仅含根结点
  • 依次读入每条编码，建立编码对应的路径
    • 对于给定的编码串，从根结点开始，按照编码的每一位向左子树或右子树移动
    • 如果路径上不存在对应的子结点，则创建新的子结点
  • 可以遇到三种情况
    • 遇到叶结点: 说明存在前缀冲突，不具备前缀特性
    • 处理所有位后，均没有创建新结点: 说明存在前缀冲突，不具备前缀特性
    • 处理最后一个编码位时，创建了新结点: 说明该编码具备前缀特性
  • 判定全部编码均具备前缀特性，则整个编码集具备前缀特性