42.（10 分）若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有果气符集（字符个数≥2）的不等长编间，每个字农润编达头二进制的0、1 厅列最长为L位，且具有前缀特性。请回答下列问题： （1）哪种数据结构适宜保存上述具有前缀特性的不等长编码? （2）基于你所设计的数据结构，简述从0/1 串到字符串的译码过程。 （3）简述判定某字符集的不等长编码是否具有前缀特性的过程。
【参考答案及解析】
（1）使用一棵二叉树保存字符集中各字符的编码，每个编码对应于从根开始到达某叶结点的一条路径， 路径长度等干编码位数， 路径到达的叶结点中保存该编码对应的字符。 （2）从左至右依次扫描O/1串中的各位。从根开始，根据串中当前位沿当前结点的左子指针或右子指针下移， 直到移动到叶结点时为止。输出叶结点中保存的字符。然后再从根开始重复这个过程。直到扫描到 0/1串结束，译码完成。 （3）二叉树既可用于保存各字符的编码，也可用于检测编码是否具有前缀特性。判定编码是否具有前缀特性的过程，同时也是构建二叉树的过程。初始时，二叉树中仅含有根结点，其左子指针和右子指针均为空。 依次读入每个编码C，建立/寻找从根开始对应于该编码的一条路径，过程如下∶ 对每个编码，从左至右扫描C的各位，根据C当前位（0或 1）沿结点的指针（左子指针或右子指针）向下移动。当遇到空指针时，创建新结点，让为空的指针指向该新结点并继续移动。沿指针移动过程中，可能遇到三种情况∶ ①若遇到了叶结点（非根），则表明不具有前缀特性，返回； ②若在处理C的所有位的过程中，均没有创建新结点，则表明不具有前缀特性，返回； ③若处理C的最后一个编码位时创建了新结点，则继续验证下一个编码。 若所有编码均通过验证，则编码具有前缀特性。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（1）使用一棵二叉树保存字符集中各字符的编码，每个编码对应于从根开始到达某叶结点的一条路径， 路径长度等干编码位数， 路径到达的叶结点中保存该编码对应的字符。 （2）从左至右依次扫描O/1串中的各位。从根开始，根据串中当前位沿当前结点的左子指针或右子指针下移， 直到移动到叶结点时为止。输出叶结点中保存的字符。然后再从根开始重复这个过程。直到扫描到 0/1串结束，译码完成。 （3）二叉树既可用于保存各字符的编码，也可用于检测编码是否具有前缀特性。判定编码是否具有前缀特性的过程，同时也是构建二叉树的过程。初始时，二叉树中仅含有根结点，其左子指针和右子指针均为空。 依次读入每个编码C，建立/寻找从根开始对应于该编码的一条路径，过程如下∶ 对每个编码，从左至右扫描C的各位，根据C当前位（0或 1）沿结点的指针（左子指针或右子指针）向下移动。当遇到空指针时，创建新结点，让为空的指针指向该新结点并继续移动。沿指针移动过程中，可能遇到三种情况∶ ①若遇到了叶结点（非根），则表明不具有前缀特性，返回； ②若在处理C的所有位的过程中，均没有创建新结点，则表明不具有前缀特性，返回； ③若处理C的最后一个编码位时创建了新结点，则继续验证下一个编码。 若所有编码均通过验证，则编码具有前缀特性。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！