十章节树与有序树.ppt

十章节树与有序树 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望家谱PeterGodfriedBettyAlbertMaryMarivinDorisJudyHalDeniseGregory一般假定在孩子是按年龄排序的一般假定在孩子是按年龄排序的,则这种树是有序的。则这种树是有序的。2语法树语法树“The big elephant ate the peanut”语法图解如下：语法图解如下：3有向树定义定义1 一个有向图，若去掉边的方向，所得无向图一个有向图，若去掉边的方向，所得无向图是一棵树，则称这个有向图为有向树。是一棵树，则称这个有向图为有向树。(a)(b)例例 两个有向树的例子。两个有向树的例子。今后只讨论今后只讨论(b)这样的所谓的这样的所谓的“根树根树”有一个根的树。有一个根的树。4根树根树设设T=(V,E)是一棵有向树，若仅有一个顶点的入度为是一棵有向树，若仅有一个顶点的入度为0，其余的顶点的入度均为其余的顶点的入度均为1，这样一棵有向树我们称为，这样一棵有向树我们称为根根树树。u入度为入度为0的顶点称为的顶点称为树根树根，u出度为出度为0的顶点称为的顶点称为树叶树叶，u出度不为出度不为0的顶点称为的顶点称为分枝点分枝点。例例abcdeabcde5例 画出4阶所有非同构的根树 树根树6例 画出5阶所有非同构的根树 树根树7父亲、儿子、祖先、后代、兄弟父亲、儿子、祖先、后代、兄弟设设T=(V,E)是一棵根树。是一棵根树。u如果如果e=(v,u)E，称，称v是是u的的父父亲亲，u是是v的的儿子儿子。u对对v1,v2V，若存在一条从，若存在一条从v1到到v2的通路，则称的通路，则称v1是是 v2的的祖先祖先，v2是是v1的的后代后代。u若若(v0，v1)，(v0，v2)E，说，说v1与与v2是是兄弟兄弟。a ab be ed di in nm m8子树设设T=(V,E)是一棵根树。是一棵根树。uv0V，v0是是 中一个分支点中一个分支点,所谓所谓以以v0为根的子树为根的子树是指是指T的的一个子图一个子图T，T 以以v0和和v0的的全部的后代为顶点，以从全部的后代为顶点，以从v0出发的所有通路经过的边为出发的所有通路经过的边为边。边。u以以v0的一个儿子为根的子树的一个儿子为根的子树称为称为v0的子树的子树。a ab be ed di in nm m9例例 试回答问题l哪个是树根哪个是树根?l哪些是树叶哪些是树叶?l哪个是哪个是e的父亲的父亲?l哪些是哪些是e的祖先的祖先?l哪些是哪些是e的儿子的儿子?l哪些是哪些是e的后代的后代?l哪些是哪些是e的兄弟的兄弟?l哪些是哪些是e的子树的子树?a ac cb be ed df fh hg gi il lk kj jn nm m10有序树定义定义2 一棵根树，若每一个分枝点出发的边，一棵根树，若每一个分枝点出发的边，分别标以整数分别标以整数1，2，k。则称这样的根树为有序树。则称这样的根树为有序树。有序树可以说是各子树从左到右是有次序的树有序树可以说是各子树从左到右是有次序的树句子句子主语主语谓语谓语形容词形容词冠词冠词名词名词The big elephant ate the peanut例例11例例需要说明的是，一棵有序树的每个分枝点出发的边的需要说明的是，一棵有序树的每个分枝点出发的边的标号并不是要求是连续的。一个分枝点出发的边，若标号并不是要求是连续的。一个分枝点出发的边，若被标上被标上i，则称这条边是这个分枝点的，则称这条边是这个分枝点的 i子树子树。如上图，一个分枝点出发的两条边被分别标上如上图，一个分枝点出发的两条边被分别标上1，3，我们说这个分枝点没有第我们说这个分枝点没有第2子树。子树。句子句子主语主语谓语谓语形容词形容词冠词冠词名词名词The elephant ate the peanut1312m分树、正则分树、正则m分树分树如果一棵有序树的每个分枝点最多有如果一棵有序树的每个分枝点最多有 m个儿个儿子，称这棵有序树为子，称这棵有序树为 m分树分树。若一棵若一棵 m分树的每一个分枝点恰好有分树的每一个分枝点恰好有m 个个儿子，称这样的儿子，称这样的 m分树为分树为正则正则m分树分树。132分树分树:左子树、右子树左子树、右子树对于对于2分树，它的每一个分枝点的第一个子树和第二分树，它的每一个分枝点的第一个子树和第二子树又分别叫子树又分别叫左子树左子树和和右子树右子树。例例 单淘汰赛的正则单淘汰赛的正则2-分树分树 14定理定理9 一棵正则一棵正则m分树的分枝点的个数为分树的分枝点的个数为i，树叶的个数，树叶的个数为为t，则有，则有 (m-1)i=t-1证明：总共有证明：总共有 i个分枝点，每个分枝点有个分枝点，每个分枝点有 m个儿子，个儿子，故总的儿子数目为故总的儿子数目为 mi。而所有的儿子包括全。而所有的儿子包括全部顶点减去一个根，即为部顶点减去一个根，即为 i+t-1，所以有：，所以有：mi=i+t-1即为即为 （m-1)i=t-1。15例5 用带用带4个插座的接线板，连接个插座的接线板，连接19个灯到一个总插座上，个灯到一个总插座上，问至少需要多少块接线板。问至少需要多少块接线板。解：任何一个连接方法都是一棵解：任何一个连接方法都是一棵4分树，分树，按定理按定理9中公式，有中公式，有 (4-1)i 191,所以所以 i616树形图的高度、顶点的路长树形图的高度、顶点的路长在一棵树形图中，在一棵树形图中，n一个顶点的路长规定为从树根到这个顶点的通路一个顶点的路长规定为从树根到这个顶点的通路的长。的长。n一棵树形图的高度即为该树中最长路的长度。一棵树形图的高度即为该树中最长路的长度。在一棵树形图中从树根到每一个顶点有且仅有唯一的在一棵树形图中从树根到每一个顶点有且仅有唯一的一条通路。一条通路。17高为高为h的正则的正则m分树分树 至少有至少有m+(m-1)(h-1)片树叶片树叶，最多有最多有mh片树叶。片树叶。18例 求证一棵正则一棵正则2分树必有奇数个顶点。分树必有奇数个顶点。证明证明:假设一棵正则假设一棵正则2分树有分树有 i个分枝点、个分枝点、t个树叶。个树叶。每个分枝点有每个分枝点有 2个儿子，故总的儿子数目为个儿子，故总的儿子数目为 2i。而所有的儿子包括全部顶点减去一个根，所。而所有的儿子包括全部顶点减去一个根，所以有：以有：2i=i+t-1即为即为i=t-1。从而全部顶点数目为从而全部顶点数目为 i+t=(t-1)+t=2t-1显然显然,它是一个奇数，结论得证明。它是一个奇数，结论得证明。19例 设一棵正则一棵正则2分树的顶点个数为分树的顶点个数为n,则它的树叶个数为：则它的树叶个数为：20例 有8枚硬币，其中恰有1枚是假币，假币比真币重。试用一架天平称出假币，使称量的次数尽可能地少。21例有8枚硬币，其中可能有1枚是假币（但假币不多于1枚），假币与真币重量不等。试用一架天平来称量，3次称出假币或断言假币不存在，请用根树表示你的称量策略。22例例 数学表达式的二分树数学表达式的二分树(二叉树二叉树)以二叉树表示数学表达式的递归定义：以二叉树表示数学表达式的递归定义：若表达式若表达式=(第一表达式第一表达式)(运算符运算符)(第二表达式第二表达式),则则 以左子树表示第一表达式以左子树表示第一表达式 以右子树表示第二表达式以右子树表示第二表达式 根结点的数据库存放运算符根结点的数据库存放运算符+*/c cd da ab b(a*b)+(c/d)+d d+c ca ab b(a+b)+c)+d23第十章 树与有序树10.1 树的基本概念树的基本概念10.2 连通图的生成树和带权连通图的连通图的生成树和带权连通图的最小生成树最小生成树 10.3 有序树有序树10.4 前缀码和最优二分树前缀码和最优二分树 24英文的编码通信英文的编码通信英文的编码通信中，考察用英文的编码通信中，考察用0和和1来表示英文字母的问来表示英文字母的问题，因为字母表中的题，因为字母表中的26个字母必须用个字母必须用0和和1组成的序列组成的序列来表示，故它们可以用长度为来表示，故它们可以用长度为5位位(因因 242625)的序列的序列表示出来。表示出来。要传递一条信息，我们只要传递用来表示消息而组成要传递一条信息，我们只要传递用来表示消息而组成字母序列的一个字母序列的一个0、1字符串即可。在接收端，把这一字符串即可。在接收端，把这一0、1字符串分为长度为字符串分为长度为5位的序列，而这些序列对应的位的序列，而这些序列对应的字母就可以识别出来。字母就可以识别出来。25英文字母使用频数英文字母使用频数26数串划分问题数串划分问题当用各种不同长度的序列来表示字母时，在接收端，当用各种不同长度的序列来表示字母时，在接收端，就存在如何把一个就存在如何把一个0、1的数串划分为对应字母序列的数串划分为对应字母序列的问题？的问题？例如，如果例如，如果 00=e 01=t 0001=w 那么那么 0001=?27前缀码前缀码序列序列 a1a2am 是序列是序列 b1b2bmbm+1bn的的前缀前缀，如果，如果 a1a2am=b1b2bm。对于序列的一个集合来说，若这个集合中的任何序列对于序列的一个集合来说，若这个集合中的任何序列都不是另一个序列的前缀，则这个集合称为都不是另一个序列的前缀，则这个集合称为前缀码前缀码。例例 000,001,01,10,11 是一个前缀码是一个前缀码 1,00,01,000,0001 不是一个前缀码不是一个前缀码 0001=00+01?0001=000+1?0001=0001?282分树分树 前缀码前缀码由任何一棵由任何一棵2分树可以得到一个前缀码，且对应一分树可以得到一个前缀码，且对应一个前缀码也一定存在一棵相应的个前缀码也一定存在一棵相应的2-分树。分树。例例 10,001,010,011,110 为一个前缀码。为一个前缀码。29前缀码前缀码 2分树分树例例 前缀码前缀码01,10,001,110 所对应的一棵所对应的一棵2分树。分树。001 110 10 01 (b)000 00 1 010 011 100 101 110 111 0 0 0 0 00 0 0 0 1 1 1 1 11 10 1 1 1 0 01 (a)30字符串 前缀码中的码字例例:已知前缀码如下图已知前缀码如下图试划分下述字符串试划分下述字符串:1100100011001000111031一段英文所用的字符串的平均长度一段英文所用的字符串的平均长度假设在假设在N个英文字母组成的短文中，英文第个英文字母组成的短文中，英文第 i个字母个字母出现的频率是出现的频率是 wi次，而第次，而第 i个字母用个字母用Li长的长的0和和1序列序列来表示，则来表示，则N个英文字母组成的一段英文所用的字符个英文字母组成的一段英文所用的字符串的平均长度为串的平均长度为 322分树的分树的叶子叶子权权假如我们有一组权假如我们有一组权w w1 1,w,w2 2,w,wn n。不失一般性，。不失一般性，设设 0 0w w1 1w w2 2 w wn n一棵有一棵有n n片叶子的片叶子的2 2分树，如果分配给它的叶分树，如果分配给它的叶子的权分别为子的权分别为w w1 1,w,w2 2,w,wn n，则这棵则这棵2 2分树称为分树称为叶子权为叶子权为 w w1 1,w,w2 2,w,wn n的的2 2分树。分树。332 2分树分树T T的权的权W(T)W(T)定义叶子权为定义叶子权为 w w1 1,w,w2 2,w,wn n的的2 2分树的权分树的权W(T)W(T)为为:W(T)=W(T)=wwi iL(wL(wi i)，其中其中L(wL(wi i)是具有权为是具有权为w wi i的叶子的路长。的叶子的路长。34例例 构造构造权值分别权值分别为为7,5,2,4的的二叉树二叉树abcd75247*2+5*2+2*2+4*2=367*3+5*3+2*1+4*2=46abcd75247*1+5*2+2*3+4*3=35dcab247535最优树最优树在叶子权为在叶子权为w1,w2,wn的所有的所有2分树中，具有最小权分树中，具有最小权的一棵的一棵2分树，称为分树，称为最优树最优树。12+14+33=5960例例36霍夫曼(Huffman D.A)算法 指导思想指导思想:把求带把求带n个权的最优树变为求带个权的最优树变为求带n-1个权的个权的最优树。最优树。37命题命题1存在一棵带权存在一棵带权w1,w2,wn的最优的最优2分树，而且带权分树，而且带权w1和和w2的二片叶子是兄弟。的二片叶子是兄弟。a awx wya aw1 w238命题1的证明显然带权显然带权w1,w2,wn的最优的最优2分树一定存在。设分树一定存在。设T是一棵这样是一棵这样的的2分树。分树。a是是T中通路最长的分支点。中通路最长的分支点。a的两个儿子的两个儿子a1和和a2分分别带权别带权wx和和wy。由于由于T是最优的，所以每一个分枝点都有两个儿子，否则这个是最优的，所以每一个分枝点都有两个儿子，否则这个分枝点可以去掉，让它的儿子代替它，仍是一个带权的分枝点可以去掉，让它的儿子代替它，仍是一个带权的2分分树，但树的权减少了。树，但树的权减少了。设设wxwy，则有，则有w1wx，w2wy。让。让a1带权带权w1，让带权，让带权w1的叶子的叶子带权带权wx，a2带权带权w2，带权，带权w2的叶子带权的叶子带权wy，我们得到一棵新的，我们得到一棵新的带权带权w1,w2,wn的的2分树，设为分树，设为T。显然，。显然，L(wx)L(w1)，L(wy)L(w2)，所以，所以，W(T)W(T)。由于是最优的，所以。由于是最优的，所以W(T)=W(T)，而，而T是是一棵带权最优一棵带权最优2分树且带权分树且带权w1与与w2的两片叶子是兄弟。的两片叶子是兄弟。39命题1的意义从一棵带权最优二分树，一定可以得到一棵带权最小从一棵带权最优二分树，一定可以得到一棵带权最小的两片叶子是兄弟的最优树。所以，可以设的两片叶子是兄弟的最优树。所以，可以设T是一棵是一棵带权带权w1,w2,wn的最优树，且带权的最优树，且带权w1和和w2的两片叶子的两片叶子是兄弟。是兄弟。把带权把带权w1和和w2的两片叶子去掉，让他们的父亲变成一的两片叶子去掉，让他们的父亲变成一片叶子带权片叶子带权w1+w2，这时我们得到一棵带权，这时我们得到一棵带权w1+w2 w3,w4,wn的的2分树，记为分树，记为 T。显然有显然有 W(T)=W(T)-w1-w2。权权w1+w2的路长少了的路长少了140命题2 设设T是一棵带权是一棵带权w1+w2 w3,wn的最优树，将带的最优树，将带权权w1+w2的叶子变为分枝点，让它的两个儿子分的叶子变为分枝点，让它的两个儿子分别带权别带权w1和和w2得一棵带权得一棵带权w1,w2,w3,wn的的2分分树，记为树，记为T。T也是最优树。也是最优树。a aw1 w2a aw1+w241命题2的证明 由已知由已知,显然有显然有 W(T)=W(T)+w1+w2。若若T不是最优树，设不是最优树，设T*是一棵带权是一棵带权w1,w2,wn的最优的最优树且树且W(T*)W(T),且带权且带权w1和和w2的两片叶子是兄弟。的两片叶子是兄弟。从从T*可以得到一个带权可以得到一个带权w1+w2 w3,wn 的的2分树分树T*，且有，且有W(T*)=W(T*)-w1-w2。因为因为T是带权是带权w1+w2 w3,wn的最优树，所以的最优树，所以W(T)W(T*)=W(T*)-w1-w2 于是，有：于是，有：W(T)=W(T)+w1+w2W(T*)这与假设这与假设W(T*)W(T)矛盾。矛盾说明矛盾。矛盾说明T是最优树。是最优树。42例例 求带权求带权2,3,5,7,10最优最优2分树。分树。分析分析：等于构造：等于构造5，5，7，10的最优树；的最优树；等于构造等于构造7，10，10的最优树；的最优树；等于构造等于构造10，17的最优树。的最优树。43哈夫曼树的构造步骤哈夫曼树的构造步骤1)根据给定的根据给定的n个权值个权值，构造，构造n棵只有一个根结点的棵只有一个根结点的二叉树，二叉树，n个权值分别是这些二叉树根结点的权。个权值分别是这些二叉树根结点的权。设设F是由这是由这n棵二叉树构成的集合。棵二叉树构成的集合。2)在在F中选取两棵根结点树值最小的树作为左、右子中选取两棵根结点树值最小的树作为左、右子树，构造一颗新的二叉树，置新二叉树根的权值树，构造一颗新的二叉树，置新二叉树根的权值=左、右子树根结点权值之和。左、右子树根结点权值之和。3)从从F中删除这两颗树，并将新树加入中删除这两颗树，并将新树加入F。4)重复重复 2)和和3)，直到，直到F中只含一颗树为止。中只含一颗树为止。44例例 w=5,29,7,8,14,23,3,11，求哈夫曼树，求哈夫曼树5142978233111429782311358871514292335811113581914292387151135819292314871529291487152911358192342113581923422914871529581135819234229148715295810045例例 最优判定问题最优判定问题等级分数段比例ABCDE059606970798089901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70BACDE2755154030105*1+15*2+40*3+30*4+10*4=275EADBC20540301551040*1+30*2+15*3+5*4+10*4=205哈夫曼树哈夫曼树46例子例子例例 某通讯系统只使用某通讯系统只使用8种字符种字符a、b、c、d、e、f、g、h，其，其使用频率分别为使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11。构造以字符使用频率作为权值的哈夫曼树。将权值取为整构造以字符使用频率作为权值的哈夫曼树。将权值取为整数数w=(5,29,7,8,14,23,3,11)，按哈夫曼算法构造的一棵哈夫，按哈夫曼算法构造的一棵哈夫曼树如下：曼树如下：对应字符的编码对应字符的编码a:0110a:0110b:10b:10c:1110c:1110d:1111d:1111e:110e:110f:00f:00g:0111g:0111h:010h:0101）构造以）构造以 a、b、c、d、e、f、g、h为叶子结点的二叉树；为叶子结点的二叉树；2）将该二叉树所有左分枝标记）将该二叉树所有左分枝标记1，所有右分枝标记，所有右分枝标记0；3）从根到叶子结点路径上标记作为叶子结点所对应字符的编码）从根到叶子结点路径上标记作为叶子结点所对应字符的编码；292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929abecdfhg47哈夫曼编码平均码长与平均压缩率哈夫曼编码平均码长与平均压缩率a:0110b:10c:1110d:1111e:110f:00g:0111h:010平均码长=4*(5%+7%+8%+3%)+3*(14%+11%)+2*(29%+23%)=2.71292919195858424210010015158 8 7 7 3 3 5 5 8 8 1111232314142929abecdfhg若用这三位二进制数(07)对这8个字母进行等长编码,等长编码的长度为3。于是，哈夫曼编码的平均压缩为：2.7131-=1-90.3%=9.7%48例给定权为给定权为 1，4，9，16，25，36，49，64，87，100。构造一棵带权最优构造一棵带权最优3-分树分树(三叉树三叉树)。解解:1491625364964871001455140251?49例给定权为给定权为 1，4，9，16，25，36，49，64，87，100。构造一棵带权最优构造一棵带权最优3-分树分树(三叉树三叉树)。解解:01491625364964875309120010039150构造一棵最优 t叉树（1）首先找出）首先找出 t个最小的权值，然后对这个最小的权值，然后对这t个权值构个权值构造出一个造出一个t叉树，并对该叉树，并对该t叉树的树根置权值为叉树的树根置权值为t个个最小权值之和。依此类推，由构造过程可知，除最小权值之和。依此类推，由构造过程可知，除根外其它分支点恰有根外其它分支点恰有t个儿子。个儿子。（2）如果构造出来的树跟恰好有）如果构造出来的树跟恰好有 t个儿子，那么这棵个儿子，那么这棵树就是最优树就是最优t叉树。如果构造出来的树根的儿子叉树。如果构造出来的树根的儿子数目数目kt，那么在原来的权值中添加，那么在原来的权值中添加 (t-k)个个0，按照步骤按照步骤(1)重新构造重新构造 t叉树，它能保证每个分支叉树，它能保证每个分支点都有点都有t 个儿子，这是最优个儿子，这是最优 t叉树。叉树。51Huffman coding In computer science and information theory,Huffman coding is an entropy encoding algorithm used for lossless data compression.The term refers to the use of a variable length code table for encoding a source symbol(such as a character in a file)where the variable-length code table has been derived in a particular way based on the estimated probability of occurrence for each possible value of the source symbol.It was developed by David A.Huffman while he was a Ph.D.student at MIT,and published in the 1952 paper A Method for the Construction of Minimum-Redundancy Codes.Huffman became a member of the MIT faculty upon graduation and was later the founding member of the Computer Science Department at the University of California,Santa Cruz,now a part of the Baskin School of Engineering.5210.1510.17作业作业2153树是否平面图？如果是，面数是多少？树是否平面图？如果是，面数是多少？课堂练习课堂练习54