为何哈夫曼树中不存在仅含一个子节点的节点？及编码算法疑问

1. 带单子女节点的编码树会不会引发歧义？ #

不会。前缀编码的核心要求是所有字符对应的编码都互为非前缀，只要保证所有字符都作为叶子节点存在，中间节点不对应任何字符，哪怕树里有单子女节点，也不会出现一个字符的编码是另一个的前缀的情况。比如：假设树中有一个中间节点只有左子节点（叶子，对应字符c），这个中间节点的路径（比如"11"）本身不对应任何字符，而c的编码是"110"，不会和其他叶子的编码（比如"0"、"10"）产生前缀冲突。

2. 为什么哈夫曼树不存在单子女节点？ #

哈夫曼树的核心目标是生成加权路径长度最小的最优前缀编码树，单子女节点属于冗余结构：

• 假设存在一个节点X只有一个子节点Y（Y是叶子或中间节点），把X直接移除，将Y连到X的父节点上，所有经过X的节点的路径长度都会减少1，总加权路径长度会直接减小（减少量等于Y及其子树的总权重）。
• 再从哈夫曼算法的构建逻辑看：算法每次都会选择当前权重最小的两个节点合并成一个新节点，绝不会出现只选一个节点合并的情况，因此自底向上构建的过程中根本不可能产生单子女节点。

3. 有没有其他算法能生成含单子女节点的编码树？ #

当然有，这类算法通常不追求最优加权路径长度，而是满足特定需求：

• 手动构造的自定义前缀编码：完全可以根据需求设计带单子女节点的合法前缀编码树，比如给字符a、b、c分别分配编码"0"、"10"、"110"，对应的树就包含单子女节点（编码"11"对应的节点只有左子节点c）。
• 非最优的编码生成算法：比如某些为了兼容旧系统、或者实现分层编码逻辑的算法，允许生成带单子女节点的结构，只要保证所有字符都在叶子节点即可。

内容的提问来源于stack exchange，提问作者Wang