树、森林——树与二叉树的应用（哈夫曼树编码）

一、定义由哈夫曼树生成的字符二进制编码左分支记 0右分支记 1左右可以互换编码不唯一但最短总长度唯一从根走到叶子依次记录 0、1就是该叶子对应字符的哈夫曼编码二、核心性质前缀编码任意一个编码都不是另一个编码的前缀不会二义解码不会出错权值越大 → 编码越短权值越小 → 编码越长整体平均码长最短最优前缀编码三、编码步骤构建好哈夫曼树左路 0右路 1根 → 叶子顺着路径写二进制每个叶子独立得到一串编码四、特点考点哈夫曼树没有度为 1 结点不会出现多余码位n 个叶子总共n 个编码编码不唯一但最短 WPL 唯一哈夫曼编码总长 整棵树 WPL五、解码规则从根出发遇 0 走左遇 1 走右走到叶子输出对应字符依次重复即可六、总结口诀左 0 右 1 根到叶大权短码小长些互不前缀无歧义最短编码哈夫曼。