Email：fws365@scu.edu.cn 2019年9月11日星期三 离散　　数学 计算机学院 冯伟森 Email：fws365@scu.edu.cn 2019年9月11日星期三.

Presentation on theme: "Email：fws365@scu.edu.cn 2019年9月11日星期三 离散　　数学 计算机学院 冯伟森 Email：fws365@scu.edu.cn 2019年9月11日星期三."— Presentation transcript:

1 Email：fws365@scu.edu.cn 2019年9月11日星期三
离散　　数学 计算机学院 冯伟森 2019年9月11日星期三

2 主要内容 完全二叉树 Huffman算法 2019/9/11 计算机学院

3 内容回顾 定义11.4 设T是一棵有向树，如果恰有一个结点的入度为0，其余所有结点的入度均为1，则称为根树或外向树。
入度为0的结点称为树根；出度为0的结点称为树叶；入度为1，出度大于0的结点称为内点；又将内点同树根统称为分支点。 如果恰有一个结点的出度为0，其余所有结点的出度均为1，则称为内向树。（如上例中的(d)) 2019/9/11 计算机学院

4 m叉树 定义11.5 在根树T中，若每个分支点的出度至多为m，则称T为m叉树； 若每个分支点的出度都等于m，则称T为完全的m叉树；
若T的全部叶结点位于同一层次，则称T为正则m叉树； 二叉树的每个结点v至多有两棵子树，分别称为v的左子树和右子树。 2019/9/11 计算机学院

5 定理11.5 若T是完全m叉树，其树叶数为t，分支点数为 i，则下式成立： （m-1）×i＝t-1 证明 由假设知，该树有i+t个结点。
m×i＝i+t-1 即 （m-1）×i＝t-1 2019/9/11 计算机学院

6 这个定理实质上可以用每局有m个选手参加的单淘汰制比赛来说明。t个叶表示t个参赛的选手，i则表示必须安排的总的比赛局数．每一局由m个参赛者中产生一个优胜者，即淘汰（m-1）个选手，故比赛结果共淘汰（m-1）i个选手，最后剩下一个冠军，所以 (m-1)i+1=t。 2019/9/11 计算机学院

7 例11.5 设有28盏电灯，拟公用一个电源插座，问需要多少块具有四插座的接线板?
解: 这个公用插座可以看成是正则四叉树的根，每个接线板看成是其它的分枝点，灯泡看成是叶，则问题就是求总的分枝点的数目。由定理11.5可以算得i = （28 -1）/3 = 9，因此，至少需要9块接线板才能达到目的。 2019/9/11 计算机学院

8 例11.6 假设有一台计算机，它有一条加法指令，可 计算3个数的和。如果要求9个数x1,x2,x3,x4,x5,
(a) x2 x3 x4 x5 x6 x7 x8 x9 x1 x2 x3 x4 x5 x6 x7 x8 x9 (b) 解 用3个结点表示3个数，将表示3个数之和的结点作为它们的父结点。这样本问题可理解为求一个完全三叉树的分支点问题。把9个数看成树叶。由定理11.5知，有(3-1)i = 9-1，得i = 4。所以至少要执行4次加法指令。 2019/9/11 计算机学院

9 把有序树转换为二叉树 从根开始，保留每个父亲同其最左边儿子的连线，撤销与别的儿子的连线。 兄弟间用从左向右的有向边连接。
按如下方法确定二叉树中结点的左儿子和右儿子：直接位于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依此类推。 反过来，我们也可以将二叉树还原为有序树。 2019/9/11 计算机学院

10 例11.7 将下图a转化为一棵二叉树。 v10 v9 v4 v7 v6 v3 (c) v1 v2 v11 v5 v8 v10 v3 v4
(b) v1 v2 v11 v9 v5 v7 v8 2019/9/11 计算机学院

11 距离、层数、高 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 定义11.6 在根树中，从树根到任一结点v的道路长度，称为根到该结点的距离（也称为结点的层数）；称层数相同的结点在同一层上；所有结点的层数中最大的称为根树的高。 2019/9/11 计算机学院

12 分支点的道路长度之和为L，各树叶的道路长度 之和为J， 则 J＝L+2×i。 证明：对分支点数目i进行归纳。
当i = 1时，L = 0，J = 2，故J = L + 2i成立。 假设i = k时定理结论成立。 2019/9/11 计算机学院

13 当i=k+1时，设在完全二叉树T中，v是一个道路长度为l的分枝点且其两个儿子v1和v2都是叶，则T–{v1,v2}是含k个分枝点的完全二叉树T’，它减少了二片长度为I+1的树叶和一个长度为I的分枝点。 由归纳假设J’=L’+2k， 比较T和T’=T–{v1,v2}，可得 J = J’+ 2（I + 1）-l = J’+l+2， L= L’+l，于是 J = L’+ 2k +l+2 =L+2（k + 1）， 即J = L+ 2i。 2019/9/11 计算机学院

14 例11.8 i=5，L=7，J=17 2019/9/11 计算机学院

15 最优二叉树 定义：设T是有t个叶的二叉树，各叶分别带权 w1，w2, …,wt，各叶的道路长度分别为 l1，l2，…，lt，定义T的权为 。
使W(T)取最小值的T，这个T称为带权 w1，w2, …,wt 的最优二叉树。 2019/9/11 计算机学院

16 Huffman定理（11.7） 在带权为w1≤w2≤…≤wt的最优二叉树中,必有T满足: 权为w1,w2的两片树叶v1,v2是兄弟；
设v1,v2的父亲是v，如果从T中删去v1，v2 ，并把v改成带权为w1+w2的叶之后的树记为T1，则T1是带权为w1+w2，w3, …,wt的最优二叉树。 2019/9/11 计算机学院

17 Huffman算法 给定实数w1,w2, …,wt，且w1≤w2≤…≤wt。 连接权为w1,w2的两片树叶，得一个分支点，其权为w1+w2；
在w1+w2，w3, …,wt中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分枝点及所带的权； 重复②，直到形成t-1个分支点，t片树叶为止。 2019/9/11 计算机学院

18 例11.9 给定一组权0.1，0.3，0.4，0.5，0.5，0.6，0.9，求对应的最优二叉树。 图3 图1 图2 2019/9/11
计算机学院

19 图4 图5 2019/9/11 计算机学院

20 图6 2019/9/11 计算机学院

21 习题十一 14、15、16、18、19、21 2019/9/11 计算机学院