第六章 树和二叉树 作业 参考答案
1、假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。
E B F A D H C G I K J
2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。
A B C D E F G H I J
3、已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为什么?
-+A*BC/DE。
4、设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。
字符A，B，C，D出现的次数为9,1,5,3。其哈夫曼编码如下A:1，B:000，C:01，D:001
5、下列是先序遍历二叉树的非递归子程序，请阅读子程序，填充空格，使其成为完整的算法。 void example(b) btree *b; {
btree *stack[20], *p； int top; if (b!=null) { top=1; stack[top]=b; while (top>0) {
p=stack[top]; top--; printf(“%d”,p->data);
0 1 0 1 9 0 5 1 1 3 哈夫曼编码树
if (p->rchild!=null){
(1)___; (2)___; }
if (p->lchild!=null) {
(3)___; (4)__; } } } }
(1)top++
(2) stack[top]=p->rchild (3)top++
(4)stack[top]=p->lchild