一个单位有12个部门，每个部门都有一部电话，但是整个单位只有一根外线，当有电话打过来的时候，由转接员转到内线电话，已知各部门使用外线电话的频率为（次/天）：5 20 10 12 8 43 5 6 9 15 19 32。 利用哈夫曼树算法思想设计内线电话号码，使得接线员拨号次数尽可能少。要求： （1）依据使用外线电话的频率构造二叉树； （2）输出设计出的各部门内线电话号码。

1. 构造哈夫曼树

首先，将各部门使用外线电话的频率按照从小到大的顺序排列，得到以下序列：

5 5 6 8 9 10 12 15 19 20 32 43

然后，将相邻的两个数字合并成一个节点，得到以下序列：

10 6 8 9 10 12 15 19 20 32 43

再将相邻的两个数字合并成一个节点，得到以下序列：

16 8 9 10 12 15 19 20 32 43

再将相邻的两个数字合并成一个节点，得到以下序列：

17 9 10 12 15 19 20 32 43

再将相邻的两个数字合并成一个节点，得到以下序列：

19 10 12 15 19 20 32 43

再将相邻的两个数字合并成一个节点，得到以下序列：

22 12 15 19 20 32 43

再将相邻的两个数字合并成一个节点，得到以下序列：

27 15 19 20 32 43

再将相邻的两个数字合并成一个节点，得到以下序列：

36 19 20 32 43

最后，将剩下的两个节点合并成一个节点，得到以下哈夫曼树：

175
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
20 155
/ \ / \
5 5 43 112
/ \
32 80
/ \
15 17

2. 设计内线电话号码

根据哈夫曼树的构造方法，我们可以得到各部门的内线电话号码：

部门1：

部门2：110

部门3：111

部门4：11110

部门5：11111

部门6：10

部门7：00

部门8：010

部门9：011

部门10：001

部门11：000

部门12：0111

这样，接线员只需要根据外线电话的来电号码，在哈夫曼树上找到对应的部门号码，再拨打内线电话即可。由于哈夫曼树的构造方法保证了频率较高的部门号码较短，因此接线员拨号次数尽可能少。