- 根树及其应用.ppt

7-8 根树及其应用前面我们讨论的树，都是一个无向图， 下面我们讨论有向图的树 定义7-8.1 如果一个有向图在不考虑边 的方向时是一棵数，那么，这个有向图称 为有向树定义7-8.2 一棵有向树，如果恰有一个 结点的入度为0，其余所有结点的入度都为 1，则称为根树入度为0的结点称为根， 出度为0的结点称为叶，出度不为0的结点 称为分支点或内点图7-8.1 有向树和根树例如图7-8.1(b)表示的是一棵根树，其中v1为 根，v2，v4，v8，v9为分枝点，其余结点为叶 在根树中，任意一个结点v的层次，就是从根 到该结点的单向通路的长度 在图7-8.1(b)中，有三个结点的层次为1，有 五个结点的层次为2，有三个结点的层次为3从根树的结构可以看出，树中每一个结点可以 看作是原来树中的某一棵子树的根，由此可知， 根树亦可递归定义为：定义7-8.3 根树包括一个或多个结点，这些结 点中某一个称为根，其它所有结点被分成有限个 子根树 这个定义把n个结点的根树用结点数少于n的 根树来定义，最后得到每一棵都是一个结点的根 树，它就是原来那棵树的树叶 对于一棵根树，如果用图形来表示，可以有树 根在下或树根在上的两种画法。

图7-8.2 根树的两种画法图7-8.2(a)是根树自然表示法，即树从它 的树根向上生长图7-8.2(b)和(c)都是由 树根往下生长，它们是同构图，其差别仅 在于每一层上的结点从左到右出现的次序 不同，为此今后要用明确的方式，指明根 树中的结点或边的次序，这种树称为有序 树设a是根树中的一个分枝点，若从a到b 有一条边，即a＜b，则结点a称为结点b的 “父亲”，而结点b称为结点a的“儿子”假 若a＜c，则结点a称为结点c的“祖先”，而 结点c称为结点a的“后裔”同一个分枝点 的“儿子”称为“兄弟” m叉树是一种特殊的根树，在m=2时， 称为二叉树，它在计算机科学中有着广泛 的应用定义7-8.4 在根树中，若每一个结点的 出度小于或等于m，则这棵树称为m叉树 如果每一个结点的出度恰好等于m或零 ，则这棵树称为完全m叉树若所有的树 叶层次相同，则这棵树称为正则m叉树， 若m=2时，称为二叉树 有许多实际问题可用二叉树或m叉树来 表示例如M和E两人进行网球比 赛，如果一人连胜两盘或共胜 三盘就获胜，比赛结束图7- 8.3表示了比赛可能进行的各种 情况，它有十片树叶，从根到 树叶的每一条路对应比赛可能 发生的一种情况，即：MM， MEMM，MEMEM，MEMEE ，MEE，EMM，EMEMM， EMEME，EMEE，EE。

图7-8.3我们要指出，任何一棵有序树都可以改 写为对应的二叉树如图7-8.4(a)中的m叉 树可用下述方法改为二叉树：⑴除了最左边的分枝点外，删去所有从每一结 点长出的分枝在同一层次中，兄弟结点间用从 左到右的有向边连接，如图7-8.4(b)所示 ⑵选定二叉树的左儿子和右儿子如下：直接处 于给定结点下面的结点，作为左儿子，对于同一 水平线上给定结点右邻结点，作为右儿子，以此 类推，如图7-8.4(c)所示图7-8.4 m叉树改写为二叉树用二叉树表示有序根树的方法，可以推 广到有序森林上去,如图7-8.5所示图7-8.5 二叉树表示森林在树的实际应用中，我们经常研究完全m叉树 定理7-8.1 设有完全m叉树，其树叶数为t，分枝 点数为i，则(m-1)i=t-1 证明 若把m叉树当作是每局有m位选手参加比 赛的单淘汰赛计划表，树叶数为t表示参加比赛的选 手数，分枝点数为 i 表示比赛的局数， 因为每局比赛将淘汰(m-1)位选手，比赛的结果 共淘汰(m-1) i位选手，最后剩下一个冠军， 因此(m-1)i+1=t 即(m-1) i =t-1例1. 设有28盏灯，拟共用一个电源插座 ，问需用多少块具有四种插座的接线板。

解 将四叉树每个分枝点看作是具有四 插座的接线板，树叶看作电灯，则(4- 1)i=28-1, i=9，所以需要九块具有四插座 的接线板例2 设有一台计算机，它有一条加法指 令，可计算三个数的和，如果要计算九个 数的和，至少要执行几次加法命令 解 若把九个数看作是完全三叉树的九 片树叶，则有(3-1)i=9-1, i=4，所以，需要 执行四次加法指令在计算机的应用中，还常常考虑二叉树 的通路长度问题 定义7-8.5 在根树中，一个结点的通路 长度，就是从树根到此结点的通路中的边 数我们把分枝点的通路长度称作内部通 路长度，树叶的通路长度称作外部通路长 度定理7-8.2 若完全二叉树有n个分枝点，且内部 通路长度总和为I，外部通路长度总和为E，则 E=I+2n 证明 对分枝点数目n进行归纳 当n=1时，E=2，I=0，故E=I+2n成立 假设n=k-1时成立，即E’=I’+2(k-1) 当n=k时，若删除去一个分枝点v，该分枝点与 根的通路长度为l，且v的两个儿子是树叶，得到新 树T’将T’与原树比较，它减少了两片长度为l+1的 树叶和一个长度为l的分枝点，因为T’有(k-1)个分 枝点，故E’=I’+2(k-1)。

但在原树中，有 E=E’+2(l+1)-l=E’+l+2, I=I’+l，代入上式得E-l-2=I- l+2(k-1)，即E=I+2k二叉树的一个重要应用就是最优树问题 给定一组权w1，w2，…，wt，不妨设 w1≤w2≤…≤wt设有一棵二叉树，共有t片 树叶，分别带权w1，w2，…，wt，该二叉 树称为带权二叉树 定义7-8.6 在带权二叉树中，若带权为 wi的树叶，其通路长度为L(wi)，我们把 w(T)=称为该带权二叉树的权在所有带权 w1，w2，…，wt的二叉树中，找到一棵使 w(T)最小的那棵树，称为最优树假若给定一组权w1，w2，…，wt，为了 找最优树，我们先证明下面定理： 定理7-8.3 设T为带权w1≤w2≤…≤wt的最 优树，则 ⑴带权为w1，w2的树叶是兄弟 ⑵以树叶为儿子的分枝点，其通路长度 最长证明 设在带权w1，w2，…，wt的最优树中，v是通路长 度最长的分枝点，v的儿子分别为wx和wy，故有 L(wx)≥L(w1) L(wy)≥L(w2) 若有L(wx)＞L(w1)，将wx与w1对调，得到新树T’，则 w(T’)-w(T)=( L(wx)·w1 + L(w1) ·wx)- ( L(wx)·wx + L(w1) ·w1) = L(wx)( w1- wx)+ L(w1)( wx - w1)= ( wx - w1)( L(w1)- L(wx))＜0。

即w(T’)＜w(T)与T是最优树的假定矛盾故 L(wx)= L(w1) 同理可证 L(wx)= L(w2)因此 L(w1) = L(w2)= L(wx)= L(wy) 分别将w1，w2与wx，wy对调得到一棵最优树，其中带权 w1和w2的树叶是兄弟定理7-8.4 设T为带权w1≤w2≤…≤wt的最 优树，若将以带权w1，w2的树叶为儿子的 分枝点改为带权w1+w2的树叶，得到一棵 新树T’，则T’也是最优树 证明 根据题设，有 w(T)=w(T’)+w1+w2 若T’不是最优树，则必有另外一棵带权 为w1+w2，w3，…，wt的最优树T”对T” 中带权为w1+w2的树叶vw1+w2生成两个儿子 ，得到树 ，则 w( )=w(T”)+ w1+w2因为T”是带权为w1+w2，w3，…，wt的最优树 树，故 w(T”)≤w(T’) 如果w(T”)＜w(T’)，则w( )＜w(T)，与T是带 权为w1，w2，…，wt最优树矛盾，因此 w(T”)=w(T’) T’是一棵带权为w1+w2，w3，…，wt的最优树 根据上面两个定理，要画一棵带有t个权 的最优树，可简化为画一棵带有t-1个权的 最优树，而又可简化为画一棵带t-2个权的 最优树，依此类推。

具体的做法是：首先 找出两个最小w值，设为w1和w2，然后对t -1个权w1+w2，w3，…，wt求作一棵最优 树，并且将这棵最优树的结点v w1+w2分叉 生成两个儿子v1和v2，依此类推此称为 Huffman算法例3. 设一组权2，3，5，7，11，13， 17，19，23，29，31，37，41求相应 的最优树 解：见P334图7-8.7 最优二叉树二叉树的另一个应用，就是前缀码问题 我们知道，在远距离通讯中，常常用0 和1的字符串作为英文字母传送信息，因为 英文字母共有26个，故用不等长的二进制 序列表示26个英文字母时由于长度为1的序 列有2个，长度为2的二进制序列有22个， 长度为3的二进制序列有23个，依此类推， 我们有 2+22+23+…+2i≥26 2i+1-2≥26, i≥4因此，用长度不超过四的二进制序列就 可表达26个不同英文字母但是由于字母 使用的频繁程度不同，为了减少信息量， 人们希望用较短的序列表示频繁使用的字 母当使用不同长度的序列表示字母时， 我们要考虑的另一个问题是如何对接收的 字符串进行译码？定义7-8.7 给定一个序列集合，若没有 一个序列是另一个序列的前缀，该序列集 合称为前缀码。

例如{000，001，01，10}是前缀码， 而{1，0001，000}就不是前缀码定理7-8.5 任何一棵二叉树的树叶可对应一个 前缀码 证明 给定一棵二叉树，从每一个分枝点引出 两条边，对左侧边标以0，对右侧边标以1，则每 片树叶可以标定一个0和1的序列，它是由树根到 这片树叶的通路上各边标号所组成的序列，显然 ，没有一片树叶的标定序列是另一片树叶的标定 序列的前缀，因此，任何一棵二叉树的树叶可对 应一个前缀码定理7-8.6 任何一个前缀码都对应一棵二叉树 证明 设给定一个前缀码，h表示前缀码中最 长序列的长度我们画出一棵高度为h的正则二 叉树，并给每一分枝点射出的两条边标以0和1， 这样，每个结点可以标定一个二进制序列，它是 从树根到该结点通路上各边的标号所确定，因此 ，对长度不超过h的每一二进制序列必对应一个 结点对应于前缀码中的每一序列的结点，给予 一个标记，并将标记结点的所有后裔和射出的边 全部删去，这样得到一棵二叉树，再删去其中未 标记的树叶，得到一棵新的二叉树，它的树叶就 对应给定的前缀码图7-8.8 二叉树对应前缀码例如，图7-8.8给出了与前缀码{000， 001，1}对应完全二叉树，其中图(a)是高 度为3的正则二叉树，对应前缀码中序列的 结点用方框标记，图(b)是对应的二叉树。

通过前缀码和二叉树的对应关系，我们 可知，如果给定前缀码对应的二叉树是完 全二叉树，则此前缀码可进行译码例如图7-8.8(b)中所对应的前缀码 {000,001，01，1}，可对任意二进制序列进 行译码 设有二进制序列 00010011011101001 可译为000,1,001,1,01,1，1,01,001 如果被译的信息最后部分不能译前缀码中 的序列，可约定添加0或1，直至能够译出为 止作业（7- 8）P337 (3)(5) a)(8)。