第六章 树和二叉树 作业 参考答案

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