离散数学第7章-8根树及其应用

1、7-8 根树及其应用p328一、根树1、有向树定义7-8.1 如果一个有向图在不考虑边的方向时是一棵树，那么，该有向图称为 有向树。 2、根树 定义7-8.2 一棵有向树,如果恰有一个结点的入度为0，其余所有结点的入度都为1,则称为根树(rooted tree)。树根:入度为0的结点称为T的树根。树叶:出度为0的结点称为树叶，分枝点:出度不为0的结点称为分枝点或内点。结点的层次：从根到该点的单向通路长度。 根树的画法有：树根在下，向上生长； 树根在上，向下生长。规定根树的画法：根画在最上方，如边的箭头全指向下，可以省略全部箭头，分层次画。V0为树根，6片叶，5个分枝点，2个结点层次为1，5个结

2、点层次为2，3个结点层次为3。（以上两个图是同构的）3、子树 定义7-8.3：任一结点v及其后代导出的子图称为根树的子树。 定义7-8.3 p329 根树包含一个或多个结点,这些结点中的某一个称为根,其他所有结点被分成有限个子根树。如上图可分成4个子树 在有向树中，结点的出现次序是没有意义的。但实际应用中，有时要给出同一级中结点的相对次序，这便导出有序树的概念。4、有序数 在根树中规定了每一层上结点的次序，称为有序树。 为表示结点间的关系，有时借用家族中的术语。定义 在以v0为根的树中， （1）v1，v2,，vk称为v0的 儿子，v0称为它们的父亲。vi，vj 同为一顶点v的儿子时，称它们为兄

3、弟。 （2）顶点间的父子关系的传递闭包称为顶点间的祖孙关系。即当vi为vi+1 (i = 1, 2, l-1) 的父亲时，v1是vl的祖先，vl为v1的子孙。 （3）根树T自身及以它的树根的子孙为根的根树（T的子图），均称为T的子树（subtree），后者又 称为T的真子树。二、m叉树p3291、 m叉树 在根树T中若每个结点的出度均m则称T为m叉树。2、完全m叉树 若每个分枝点的出度恰好等于m则称T为完全m叉树 。3、正则m叉树 若完全m叉树T的所有树叶的层数均相同则称T正则m叉树。 若m叉树是有序的，则称T为m叉有序树，若m叉完全树是有序的则称T为完全m叉有序树，若m叉正则树是有序的，则称

4、T为m叉正则有序树。 练习：画出3叉树、完全3叉树、正则3叉树4、二叉树 当m=2时，称为二叉树。 二元有序树的每个结点至多有两个儿子，其序按左右分，分别为左儿子，右儿子，任一分支点最多有两棵子树，称为左子树和右子树。二叉树完全二叉树正则二叉树 常用的二叉树、完全二叉树和正则二叉树。不难看出，二叉树中的每个结点v，至多有两个子树，分别称为v的左子树和右子树。若v只有一个子树，则称它为左子树或右子树均可。在二叉树的图形表示中，v的左子树画在v的左下方，v的右子树画在v的右下方。例两人进行网球比赛五局三胜p330 5、有很多实际应用，可用二叉树或m叉树表示。可以指出，按下面算法，任何一棵有序树均能

5、转成二叉树。其算法是：(1) 除最左边的分枝结点外，删去所有从每一个结点长出的分枝。在同一级中，兄弟结点之间用从左到右的弧连接。(2) 选取直接位于给定结点下面的结点作为左儿子，与给定结点位于同一水平线上且紧靠它的右边结点作为右儿子，如此类推。 上述算法能够推广到有序森林上去。三、性质1.定理7-8.1 p331 设有完全m叉树，其树叶的数目为t, 分支数为i, 则(m-1)i=t-1。证明思路： t位选手参加比赛，每局m位选手,单淘汰赛,每局淘汰(m-1)位,共比赛i局,最后剩1位选手。因此有： (m-1)i+1=t 例题1、2 p332给出此定理的应用示例。请画出树。四、再讨论二叉树 1.

6、结点通路长度p332 在根树中，一个结点的通路长度，就是从树根到该结点的通路中的边数。2.内部通路长度 分支点的通路长度称为内部通路长度，3.外部通路长度 树叶的通路长度称为外部通路长度。4.定理7-8.2p332 设有完全二叉树有n个分支点，且内 部通路长度为总和为I ，外部通路长度总和为E ， 则 E=I+2n。 证明思路：对分支点n采用数学归纳法。五、最优树（最优二叉树） 二叉树的一个重要应用就是最优树问题。1.带权二叉树 p332 给定一组数w1，w2，wn。令一棵二叉树有n个叶结点，并对它们分别指派w1，w2，wn作为权，则该二叉树称为加权二叉树。2.带权二叉树的权定义7-8.6 在

7、带权二叉树T中，若带权为wi树叶， 其通路长度为L(wi) ,把 t w(T) = wi L(wi) i=1 称为该带权二叉树权。3.最优树 所有带权w1, w2, wt的二叉树树中， w(T)最小的那棵树，称为最优树。27549w(T)=7*2+5*2+2*3+4*3+9*2=607 9 254w(T)=2*1+4*2+5*3+（7+9）*4=89相同的权但树权不同4. 求最优树A）定理7-8.3 设T为带权w1w2wt的最优树，则 1) 带权w1,w2的树叶，vw1, vw2是兄弟。 2) 以树叶vw1, vw2为儿子的分支点,其通路长度最长。证明思路：设在带权w1, w2, wt的最优树

8、中, v是通路最长的分支点, v的儿子分别带权wx和wy,故有 L(wx) L(w1) L(wy) L(w2) 若L(wx) L(w1),将wx与w1对调,得到新树T,则 w(T)-w(T)=w1L(wx)+wxL(w1)-wxL(wx)+ w1L(w1) = L(wx)(w1 - wx)+ L(w1)(wx - w1) = (wx - w1)L(w1) - L(wx) 0即w(T)w(T),与是最优树假设矛盾。故L(wx)=L(w1)。 同理可证L(wx)=L(w2)。因此 L(wx)=L(wy)=L(w1)=L(w2)。分别将w1, w2与wx, wy对调得一最优树,vw1, vw2是兄弟

9、。证明思路：根据假设，有 w(T)= w(T) +w1+ w2 若T不是最优树, 则必有另一棵带权w1+w2, w3, wt的最优树T。对T中带权w1+w2的树叶vw1+w2生成两个儿子，得到新树T* ，则 w(T*)= w(T) +w1+ w2因为T是带权w1+w2, w3, wt的最优树，故 w(T) w(T) 若w(T)w(T),则w(T*)w(T),与T是带权w1, w2, wt的最优树矛盾，因此 w(T) = w(T)T是带权w1+w2, w3, wt的最优树。 求最优树B）定理7-8.4 设T为带权w1w2wt的最优树，若将以带权w1和w2的树叶为儿子的分支点改为带权w1+w2的树

10、叶,得到一棵新树T,则T也是最优树。 根据上述两个定理，求一棵有n个权的最优树，可简化为求一棵有n-1个权的最优树，而这又可简化为求一棵有n-2个权的最优树，依此类推。具体作法是：首先找出两个最小的权值，设w1和w2。然后对n-1个权w1+w2，w3，wn求作一棵最优树，并且将这棵树中的结w1+w2代之以w1 w2，依此类推。 小结最优树的定义树的路径长度定义为： 树中每个结点的路径长度之和。 结点的路径长度定义为： 从根结点到该结点的路径上 分支的数目。 树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 W(T) = wklk (对所有叶子结点)。 在所有含 n 个叶子结点、并带

11、相同权值的 m 叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。例如：27 9 75492W(T)= 72+52+23+43+92 =60W(T)= 74+94+53+42+21 =89 54 给定的 n 个权值 w1, w2, , wn， 且 w1 w2， , wn1）连接权为w1, w2两片叶，得一个分 枝点权为w1+w2。 如何构造最优树Huffman 算法 以二叉树为例： 2） w1+w2 ，w3, w4, , wn 中选出两个 最小的权，连接对应顶点（不一定 是树叶），得新分枝点及所得的权。3）重复2）直到形成n-1个分枝点，n 片树叶为止。例如: 已知权值 W= 5,

12、 6, 2, 9, 7 求最优树956277967139716132995271667132900001111000110110111例题3 p334练习p337（5）所以表示26个不同的英文字母用长度不超过4的二进制 六、二叉树的应用前缀码问题 1. 26个英文字母的表示：长度1 2个编码 0，1长度2 22 . 00，01，10，11长度3 23 . 000，001，010，011，100，101，110，111.表示26个字母 2+22+23 2n26 n4 由于字母使用的频繁程度不同，为了减少信息量，常用的字母用长度短的字符串。 那么如何对接收到的信息进行译码呢？ 设序列=1 ，2 ，

13、n ，任意i ，i，ij 时i ，i互不为前缀。称为前缀码。2. 前缀 设 =12.n长度为n的字符串，称其子串1，12 ， 123 ，.， 12.n-1分别为的长度1，2，n-1的前缀。3.前缀码 定义7-8.7 给定一个序列的集合，若没有一个序列是另一个序列的前缀，该序列集合称为前缀码。如果i取值0，1，其为二元前缀。如1，00，011，0101，01001，01000 是前缀码。 000，001，01，10，11 是前缀码 0，10，110，1111 是前缀码而 1，0001，000 ，1，01，101，0011，00，011，0101，0100，01001，01000不是前缀码4.定理7-8.5 任意一棵二叉树的树叶可对应一个前缀码。证明思路： 给定一棵二叉树T具有t片树叶，则从每一个分支点v引出一到两条边。1）若v有两条边，对左侧边标以0，对右侧边标以1；2）若v只有一条边，其边标上0或1。则每片树叶将可标定一个0和1的序列，它是由树根到这片树叶的通路上各边标号所组成的序列，显然，没有一片树叶的标定序列是另一片树叶标定序列的前缀，因此，任何一棵二叉树的树叶可对应一个前缀码。 5.若T是完全二叉树，则有T产生的前缀码是唯一的。95271667132900001111000110110111前缀码为00，01，10，110，111 10100100010000前缀码为