UOJ Logo PP Online Judge

PPOJ

#116. 数据结构实验3: 树的 Huffman 编码

统计

描述

给你一个字母出现的频率,请输出 Huffman 树形成的表。

输入

27 个数字,代表 Huffman 树的每个字母出现的频率。

输出

一张 Huffman 表,对于每行:

第一个数代表权值,第二个数代表左孩子,第三个数代表右孩子,第四个数代表这个结点的父亲结点。

样例一

输入

64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1 168

输出

64 0 0 45
13 0 0 33
22 0 0 37
32 0 0 39
103 0 0 48
21 0 0 36
15 0 0 33
47 0 0 41
57 0 0 43
1 0 0 28
5 0 0 31
32 0 0 39
20 0 0 36
57 0 0 43
63 0 0 44
15 0 0 34
1 0 0 28
48 0 0 42
51 0 0 42
80 0 0 46
23 0 0 37
8 0 0 32
18 0 0 35
1 0 0 29
16 0 0 34
1 0 0 29
168 0 0 50
2 10 17 30
2 24 26 30
4 28 29 31
9 30 11 32
17 22 31 35
28 2 7 38
31 16 25 38
35 32 23 40
41 13 6 40
45 3 21 41
59 33 34 44
64 4 12 45
76 35 36 46
92 37 8 47
99 18 19 47
114 9 14 48
122 38 15 49
128 1 39 49
156 40 20 50
191 41 42 51
217 5 43 51
250 44 45 52
324 46 27 52
408 47 48 53
574 49 50 53
982 51 52 0

提示

可以证明,按 Huffman 提供的算法形成的 Huffman 树是唯一的。