二叉树的一个重要应用最优树问题

二叉树的一个二叉树的一个重要应用重要应用最优树问题最优树问题给定一组权给定一组权w1,w2,wt,不妨设不妨设w1w2wt。设。设有一棵二叉树，共有有一棵二叉树，共有t片片树叶，分别带权树叶，分别带权w1,w2,wt,该二叉树称该二叉树称为为带权二叉树带权二叉树。定义定义1 在带权二叉树中，若在带权二叉树中，若带权为带权为wi的树叶，其通路长的树叶，其通路长度为度为L(wi)，我们把，我们把w(T)=wiL(wi)称为该带权二称为该带权二叉树的权。在所有带权叉树的权。在所有带权w1,w2,wt的二叉树中，的二叉树中，w(T)最小最小的那棵树，称为最的那棵树，称为最优树。优树。ti=1定理定理3 设设T为带权为带权w1w2wt的最优树，则的最优树，则 a）带权）带权w1,w2,wt的树叶的树叶vw1,vw2是兄弟。是兄弟。b）以树叶）以树叶vw1,vw2为儿子为儿子的分枝点，其通路长度的分枝点，其通路长度最长最长。定理定理4 设设T为带权为带权w1w2wt的最优树，的最优树，若将以带权若将以带权w1和和w2的树叶的树叶为儿子的分枝点改为带权为儿子的分枝点改为带权w1+w2的树叶，得到一棵的树叶，得到一棵新树新树T，则，则T也是最优树。也是最优树。代之以代之以w1+w2w2w1例例1：设有一组权设有一组权 2、3、5、7、11、13、17、19、23、29、31、37、41。求相应。求相应的最优树。的最优树。二叉树的另一二叉树的另一个应用个应用前缀码问题前缀码问题定义定义2 给定一个序列给定一个序列的集合，若没有一个的集合，若没有一个序列是另一个序列的序列是另一个序列的前缀，该序列集合称前缀，该序列集合称为前缀码。为前缀码。例如：例如：000，001，01，10，11是前缀是前缀码，而码，而1，0001，000就不是前缀码。就不是前缀码。定理定理5 任意一棵二叉任意一棵二叉树的树叶可对应一个树的树叶可对应一个前缀码。前缀码。证明证明 给定一棵二叉树，从给定一棵二叉树，从每一个分枝点引出两条边，每一个分枝点引出两条边，对左侧边标以对左侧边标以0 0，对右侧边，对右侧边标以标以1 1，则每片树叶将可标，则每片树叶将可标定一个定一个0 0和和1 1的的序列序列，它是由，它是由树根到这片树叶的通路上各树根到这片树叶的通路上各边标号所组成的序列，边标号所组成的序列，显然，没有一片树叶的标定显然，没有一片树叶的标定序列是另一片树叶标定序列序列是另一片树叶标定序列的前缀，因此，任何一棵二的前缀，因此，任何一棵二叉树的树叶可对应一个前缀叉树的树叶可对应一个前缀码。码。定理定理6 任何一个前缀任何一个前缀码都对应一棵二叉树。码都对应一棵二叉树。证明证明 设给定一个前缀码，设给定一个前缀码，h h表示前缀码中最长序列的表示前缀码中最长序列的长度。我们画出一棵高度为长度。我们画出一棵高度为h h的的正则二叉树正则二叉树，并给每一，并给每一分枝点射出的两条边标以分枝点射出的两条边标以0 0和和1 1，这样，每个结点可以标定一这样，每个结点可以标定一个二进制序列，它是由树根个二进制序列，它是由树根到该结点通路上各边的标号到该结点通路上各边的标号所确定，因此，对于长度不所确定，因此，对于长度不超过超过h h的每一二进制序列必的每一二进制序列必对应一个结点。对应一个结点。对应于前缀码中的每一序列对应于前缀码中的每一序列的结点，给予一个标记，并的结点，给予一个标记，并将标记结点的所有后裔和射将标记结点的所有后裔和射出的边全部删去，这样得到出的边全部删去，这样得到一棵二叉树，再删去其中未一棵二叉树，再删去其中未加标记的树叶，得到一棵新加标记的树叶，得到一棵新的二叉树，它的树叶就对应的二叉树，它的树叶就对应给定的前缀码。给定的前缀码。图（图（b）中所对应的前缀码）中所对应的前缀码00，001，01，1。设有二。设有二进制序列可译为进制序列可译为000，1，001，1，01，1，1，01，001。我们知道，在远距我们知道，在远距离通讯中，常常用离通讯中，常常用0和和 1的字符串作为英文的字符串作为英文字母的传送信息，因字母的传送信息，因为英文字母共有为英文字母共有26个，个，故如用不等长的故如用不等长的H进进制序列表示制序列表示 26个英文个英文字母时，由于长度为字母时，由于长度为 1的序列有的序列有 2个，长度个，长度为为2的的H进制序列有进制序列有 2个，长度为个，长度为 3的有的有 2个，依此类推，我们个，依此类推，我们有有 22，226 ZI12P26，474因此，用长度不超过因此，用长度不超过四的二进制序列就可四的二进制序列就可表达表达26个不同英文字个不同英文字母。但是由于字母使母。但是由于字母使用的频繁程度不同，用的频繁程度不同，为了减少信息量，人为了减少信息量，人们希们希望用较短的序列去表望用较短的序列去表示频繁使用的字母。示频繁使用的字母。当使用不同长度的序当使用不同长度的序列列表示字母时，我们要表示字母时，我们要考虑的另一个问题是考虑的另一个问题是如何对接收到的字符如何对接收到的字符串串进行详码？进行详码？回回 四四 例如图例如图788给出给出了与前缀码忏叭了与前缀码忏叭001，01，万对应的完，万对应的完全二叉树，其中图全二叉树，其中图k）是高度为是高度为3的正则二叉的正则二叉树，对应前缀码中序树，对应前缀码中序列的结点用方框标记，列的结点用方框标记，图（的是经删剪后得图（的是经删剪后得到的对应三叉树。到的对应三叉树。通过前缀码和二叉通过前缀码和二叉树的对应关系，我们树的对应关系，我们可知，如果给定前缀可知，如果给定前缀码码对应的二叉树是完全对应的二叉树是完全二叉树，则此前缀码二叉树，则此前缀码可进行译码。可进行译码。例如，可对例如，可对任意二进制序列进行任意二进制序列进行译码。译码。如果被译的如果被译的信息最后部分不能成信息最后部分不能成为前缀码中的序列，为前缀码中的序列，可约定可约定添加添加0或或1，直至能够，直至能够译出为止译出为止 证明设在带权证明设在带权W，创创b，。的，。的最优树中，最优树中，0是通路长是通路长度度最长的分校点，用的最长的分校点，用的儿子分别带权儿子分别带权Wi和。和。0，故有，故有 LtheDeL（Wi L（叫（叫L（W）若若L枷枷JLJ，将，将叩与一对调，得到新叩与一对调，得到新材材T。则。则 。许一叫。许一叫n一一（LedW十十Ltw叨叨J 一一（L（叫（叫W十十L（W卜卜W）一一L0wih一。干一。干L（。（。1）tw一心一心 一（一（w一一w）（）（L（W）一）一 L（w）0即。叨即。叨）。）。w，与，与T是最优树的假定矛盾。是最优树的假定矛盾。故工故工ho一一L（心。（心。同理可证同理可证LboL（W）。因此）。因此 Ltw）一石）一石功一功一LedL。）。）分别将分别将o七，。与七，。与o七，。对调得到一七，。对调得到一棵最优树，其中带权棵最优树，其中带权创创h和以。和以。的树叶是兄弟。回的树叶是兄弟。回 证明根据题设，有证明根据题设，有 一。（万一。一。（万一。W卜。卜。1W。若若T不是最优树，则必不是最优树，则必有另一棵带权地十。有另一棵带权地十。，。，。a，。；的最，。；的最优优树树P。对。对y中带权地十中带权地十创会的树叶。创会的树叶。生成两个儿子，得到生成两个儿子，得到新树分，则一新树分，则一 。（。（f一叫一叫p）。）。l十一。十一。因因为为T”是带权。是带权。1Wb，W，。，。t的最优的最优树，故树，故 ho（”）。（）。（T。如果。如果。W）。仔，）。仔，则。曲。侧，与则。曲。侧，与Y是是带权。，带权。，。最优树的假设矛盾，最优树的假设矛盾，因此因此”、“。卜。卜。们，们，er是带权是带权Ww，w，W的最优树。回的最优树。回 根据上述两条定理，根据上述两条定理，要画一棵带有：个权要画一棵带有：个权的最优裕，可简化为的最优裕，可简化为画一棵带有画一棵带有t一一1个权个权的最优树，而这又可的最优树，而这又可简化为画一棵带有简化为画一棵带有t一一2个权的最优树，依此个权的最优树，依此类推。具体做法是：类推。具体做法是：首先找出两个最小的。首先找出两个最小的。值值以刀地和地，然后对以刀地和地，然后对卜卜1个权地十个权地十w，w。wb作一担全作一担全优树，并且将这棵最优树，并且将这棵最优树中的结点优树中的结点K刁代之刁代之m八八依此类推。依此类推。M首先组合首先组合 2十已并十已并寻找寻找5、5、7、11、Af的的MMforsg65依！依！k来推。边来推。边人二人二，。，。u。，。，H。D 8 3 57 M 1317 19 23 29 31 37 41 5 5 711 18 17 19 23 29 31 37 41 10 7 11 13 17 192329 31 37 Af 17 11 18 17 19 23 29 31 37 41 17 24 17 19 23 29 31 87 41 24 34 19 op 29 31 37 41 M 34 42 W 31 37 41 M 42 53 at 37 41 425365gr41 We cd 6578 95 78 951M 238 它对应的历优树如自它对应的历优树如自7ed7所示。所示。