树与二叉树转换，森林与二叉树的转换，哈夫曼编码例题详解
- 二叉树的前序序列和后序序列正好相反，则该二叉树一定是（B）
- A.空或只有一个结点
- B.高度等于其结点数
- C.任一结点无左孩子
- D.任一结点无右孩子
2.任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（A）
- A.肯定不发生改变
- B.肯定发生改变
- C.不能确定
- D.有时发生变化
答案解析
[解析] 如果用符号D表示访问根结点，用L表示遍历左子树，用 R表示遍历右子树，那么前序、中序、后序遍历可分别表示为：DLR、 LDR、LRD。由此可见，在三种遍历序列中L和R的相对次序都是L在前、R在后。所以，任何一棵二叉树的叶结点在前序、中序、后序序列中的相对次序都不会发生改变。
3.为5个使用频率不等的字符设计哈夫曼编码，不可能的方案是（D）
- A.001,001,010,011,1
- B.0000,0001,001,01,1
- C.000,001,01,10,11
- D.00,100,101,110,111
4.设哈夫曼编码的长度不超过4，若已经对两个字符编码为1和01，则最多还可以为（C）个字符编码。
A.2
B.3
C.4
D.5
5.具有100个结点的完全二叉树的叶子结点数为【填空1】
【填空1】50
6.设森林中有4棵树，树中结点的个数依次为n1,n2,n3,n4,则把森林转换成二叉树后，其根节点的右子树上有【填空1】个结点，根节点的左子树上有【填空2】个结点。
【填空1】n2+n3+n4
【填空2】n1-1
7.某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是【填空1】。
【填空1】CDBGFEA
8.在有n个叶子的哈夫曼树中，分支结点的总数为【填空1】
【填空1】n-1
9.已知某字符串S*有8种字符，各种字符分别出现2次，1次，4次，5次，7次，3次，4次和9次，对该字符串用{0,1}来进行前缀编码，该字符串的编码至少有【填空1】位。
【填空1】98
10.已知二叉树的中序序列为CBEDAFIGH，后序序列为CEDBIFHGA，试构造该二叉树？
注：请用文字或上传图片作答。
11.对给定的一组键值W={5,2,9,11,8,3,7},试构造相应的哈夫曼树，并计算它的带全路径长度WPL。
注：请用文字或上传图片作答。