这不是三元正则树
8
3 45 6 7 12
W(T)=(1+2)×3+(3+4)×2+(5+6+7)×2+ 8×1 =67
Huffman算法的推广算法
m元正则树的分支点数s与树叶数t之间满足 (m-1)s=t-1
求m元最优树时应分两种情况讨论
(t-1)/(m-1)为整数时，说明所求树T为m元正则 树，可仿Huffman算法求最优m元树。
行遍2元有序正则树的方式：
最佳前缀码
数 频率 编码 码
码 (%)
长
0 25 01
2
1 20 11
2
2 15 001 3
3 10 100 3
4 10 101 3
5 10 0001 4
6 5 00000 5
7 5 00001 5
二元树的应用4
波兰符号法与逆波兰符号法
行遍(周游)根树T : 对T 的每个顶点访问且仅访问 一次.
第9章 树
9.1 无向树及生成树 9.2 根树及其应用
Huffman算法的推广算法
求一棵带权为1，2，3，4，5，6，7，8的
最优3元树 ？
这不是三元正则树
78
12 3
45 6
W(T)=(1+2+3)×3+(7+8)×2+ (4+5+6) ×2+=78
Huffman算法的推广算法
求一棵带权为1，2，3，4，5，6，7，8的 最优3元树
因为16=24 < 26 < 32=25，所以要用5位表示。
用不定长二进制数表示英文字母：
若规定，可用1bit表示英文字母，也可用2 bit表示英文字母。若1 位和两位不足以表示26个英文字母，可用3 bit。再不够，用4 bit。
至少需要多少位二进制数？设需要 i 位二进制数，于是， 下列的不等式成立： 26 ≤ 21＋22＋…＋2i = 2i+1–2
1(看作右边). 将从树根到每一片树叶的通路上标的数字组成的字符
串记在树叶处, 所得的字符串构成一个前缀码.
右图的树叶都互为前缀码
求图示的二元树产生的前缀码
解：在图中每一个分枝点引出的左侧边标记0，右 侧边标记1。
由根结点到树叶的路经上各边的标记组成的0、1 序列作为对应树叶的标记，得右图。
数据 儿子1 儿子2 …… 儿子n
链表结点的单元个数若
➢ 固定得较大 ➢ 按需分配 会浪费较多空间或使算法复杂。
所以，树的存储表示大都先转化成二元树。
二元树的应用1
二元树可以表示任何一棵有序根树 方法如下：
①从根结点开始，保留父亲和最左边儿子的连线，取消 和其他儿子的连线，兄弟之间用从左到右的有向边连 接。
产生的前缀码为01,11,000,0010,0011
0
1
01
1
01
01
由任意一个前缀码求对应一个二元树
设1,01,000是一前缀码，画出对应一个二元树
解：画出一个高为3的正则二元树，给各边标记0或1，每 一个结点对应一个0、1序列，如果某个0、1序列是前缀码 的元素，则标记该结点。
将已标记结点的所有后代和该结点的射出边全部删除，再 删除未加标记的树叶，得到要求的二元树。
解: 用Huffman算法求以频率(乘以100)为权的最优 2元树. 这里 w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25.
最佳前缀码
相当于求 5, 5, 10, 10, 10, 15, 20, 25 的最优2元树.
数 频率 编码 码 (%) 0 25 01 1 20 11 2 15 001 3 10 100 4 10 101 5 10 0001 6 5 00000 7 5 00001
其中1, 2, …, m为非空字符串, 且任何两个互
不为前缀。
2元前缀码: 只出现两个符号(如0与1)的前缀码。
如 {0,10,110, 1111}, {10,01,001,110}是2元前 缀码。
{0,10,010, 1010} 不是前缀码。
前缀码
一棵2元树产生一个二元前缀码:
对每个分支点, 若关联2条边, 则给左边标0, 右边标1; 若只关联1条边, 则可以给它标0(看作左边), 也可以标
例如：若用00表示e，用01表示t，用0001表示q。当接 收员接收到0001时，就无法区分这是et，还是q。为了 解决这个问题，引入前缀码的概念。
二元树的应用3——前缀码
设 =12…n-1n是长度为n的符号串 的前缀: 12…k , k=1,2,…,n-1 前缀码: {1, 2, …, m},
解之，得i ≥4
故用长度不超过4位的二进制数足以表示26个英文字母。
二元树的应用2
在英文中有些字母使用频率较高，另一些字母使 用频率较低。
为了减少通信中传递的信息量，人们希望用位数 较少的二进制数表示频繁使用的字符，用位数较 多的二进制数表示不常使用的字符。
这样就会大大缩短信息串的总长度。但是也产生 了一个问题。接收者如何将0、1组成的长串，准 确无误地分割成字母对应的0、1序列呢？
(t-1)/(m-1)的余数为k时，1 ≤ k ≤ m-2，说明所 求树是非正则的，
此时将k+1个较小的权对应的树叶 作为兄弟放在最高层次上，然后仿 Huffman算法求最优m元树即可。
二元树的应用1
由于树在计算机内存中可通过多重链表来表示，
各链表结点所占内存单元的个数依赖于该结点的儿子数，
若一个结点有 n 个儿子，一般要用(n+1)个单元表示该结点， （n个单元用来指出该结点的各儿子的位置），结点一般表示为：
二元树的应用1
二元树可以表示任何一棵有序根树 方法如下：
②选定二叉树的左儿子和右儿子如下：处于给定结点下 方的结点作为该结点的左儿子，同一水平线上与给定 结点右邻的结点作为该结点的右儿子。
二元树的应用2
在通信中常用二进制串表示英文字母。最少用多少位二进 制数就能表26个英文字母呢？
用定长二进制数表示英文字母：
最佳前缀码
例 在通信中，设八进制数字出现的频率如下：
数码
01234 5
6
7
出现频率(%) 25 20 15 10 10 10 5 5
采用2元前缀码, 求传输数字最少的2元前缀码 (称作最佳前 缀码), 并求传输10n(n2)个按上述比例出现的八进制数字需 要多少个二进制数字？若用等长的 (长为3) 的码字传输需要 多少个二进制数字?