结构推理
什么是前缀编码?举例说明如何利用二叉树来设计二进制的前缀编码。
【正确答案】前缀码是一编码不是任何其它编码前缀的编码。例如,0和01就不是前缀码,因为编码0是编码01的前缀。仅从编码来看,0和01 是前缀码,但因历史的原因,它不被称为前缀码,而是把一编码不是另一编码前缀的编码称为前缀码。
利用二叉树可以构造前缀码,例如,以A,B,C,D为叶子可构成二叉树,将左分枝解释为0,右分枝解释成1,从根结点到叶子结点的0、1串就是叶子的前缀码。用哈夫曼树可构造出最优二叉树,使编码长度最短。
【答案解析】