离散数学第十一章树.ppt

第第十一十一章章 树树离散数学离散数学 陈志奎主编陈志奎主编人民邮电出版社人民邮电出版社前言n1847年，德国学者柯希霍夫（Kirchhof）在研究物理问题时提出了树的概念。他用一类线性方程组来描述一个电路网络的每一条支路中和环绕每一个回路的电流。他像数学家一样抽象地思考问题：用一个只由点和线组成的相应的组合结构来代替原来的电路网络，而并不指明每条线所代表的电器元件的种类。事实上，他把每个电路网络用一个基本图来代替。为了解相应的方程组，他用一种结构方法指出，只要考虑一个图的任何一个“生成树”所决定的那些独立圈就够了。他的方法现已成为图论中的标准方法。前言n1857年，英国数学家凯莱（CaylayArthur）从事计数由给定的碳原子数n的饱和碳氢化合物的同分异构物时，独立地提出了树的概念。凯莱把这个问题抽象地叙述为：求有P个点的树的数目，其中每个点的度等于1或4，树上的点对应一个氢原子或一个碳原子。凯莱的工作是图的计数理论的起源。法国数学家若尔当在1869年作为一个纯数学对象独立地发现了树，他并不知道树与现代的化学学说有关。n1889年凯莱给出了完全图Kn的概念。前言n1956年Kruskal设计了求最优树的有效算法。n树是一类既简单而又非常重要的图，是计算机中一种基本的数据结构和表示方法，在输电网络分析设计、有机化学、最短连接及渠道设计等领域也都有广泛的应用。n本章将对树进行详细的讨论，主要包括树的基本性质和生成树，以及有向树中的m叉树、有序树和搜索树等。PART PART 0101PART PART 0202树与生成树有向树及其应用主要内容11.1树与生成树n定义11.1 连通且不含回路的图称为树。树中度为1的结点称为叶，度大于1的结点称为枝点或内点。根据这个定义，平凡图K1也是树。K1是一个既无叶又无内点的平凡树。n定义11.2 在定义11.1中去掉连通的条件，所定义的图称为森林。森林的每个支都是树。6树及其性质11.1树与生成树n例11.1 图11.1所示是森林，他的每个分支（a）、（b）都是一棵树。图11.17树及其性质11.1树与生成树n定理11.1 设T是无向（n，m）图，则下述命题相互等价。（1）T连通且无回路。（2）T无回路且m=n-1。（3）T连通且m=n-1。（4）T无回路但新增加任何一条边（端点属于T）后有且仅有一个回路。（5）T连通，但是删去任何一边后便不再连通。（6）T的每一对结点之间有且仅有一条道路可通。8树及其性质11.1树与生成树n推论11.1 任何非平凡树至少有二片叶。证明：设（n,m）树T有t片叶，则，由定理11.1中命题（2），可得，即n例11.2 设是一棵树，它有两个2度节点，一个3度节点，三个4度节点，求的树叶数。解：设树有片树叶，则的节点数的边数又由得所以，即树有9片树叶。9树及其性质11.1树与生成树n推论11.2 阶大于2的树必有割点。证明：由知道T至少有一个度数大于1的内点v，再由定理11.1中命题（5），T-v不是连通的，故v必是割点。10树及其性质11.1树与生成树n定义11.3 若无向（连通图）G的生成子图是一棵树，则称该树是G的生成树或支撑树，记为。生成树中的边称为树枝。图G中其他边称为的弦。所有这些弦的集合称为的补。n例11.3 图11.2中（b）、（c）所示的树、是图（a）的生成树，而（d）所示的树不是图（a）的生成树。图11.211生成树与最小生成树11.1树与生成树n例11.4 某地要兴建个工厂，拟修筑道路连接这处。经勘测其道路可依如图11.2（a）的无向边铺设。为使这处都有道路相通，问至少要铺几条路？解：这实际上是求G的生成树的边数问题。一般情况下，设连通图G有n个节点，m条边。由树的性质知，T有n个节点，n-1条树枝，m-n+1条弦。在图11.2（a）中，n=5，则n-1=4，所以至少要修条路才行。由图11.2可见，要在一个连通图中找到一棵生成树，只要不断地从的回路上删去一条边，最后所得无回路的子图就是的一棵生成树。于是有以下定理。12生成树与最小生成树11.1树与生成树n定理11.2 无向图为连通当且仅当有生成树。证明：先采用反证法来证明必要性。若G不连通，则它的任何生成子图也不连通，因此不可能有生成树，与G有生成树矛盾，故G是连通图。再证充分性。设G连通，则G必有连通的生成子图，令T是G的含有边数最少的生成子图，于是T中必无回路（否则删去回路上的一条边不影响连通性，与T含边数最少矛盾），故T是一棵树，即生成树。13生成树与最小生成树11.1树与生成树n定义11.4 设是加权无向图，中所有边的加权长度之和称为的加权长度。G的所有生成树中加权长度最小者称为的最小生成树。最小生成树有很广泛的应用。例如要建造一个连接若干城市的通讯网络，已知城市和之间通讯线路的造价，设计一个总造价为最小的通讯网络，就是求最小生成树。14生成树与最小生成树11.1树与生成树n例11.5 图11.3显示了利用Kruskal算法生成最小生成树的过程。通俗地讲，该算法就是想将图中的边按权重从小到大排列，再从小到大一次取出每条边做检查。一开始取最小的边，由该边导出一部分子图，然后依次每取一边加入得到的部分子图。若仍为无回路，将该边与原有部分子图的边导出一个新子图；若得到回路，将该边放弃。上述过程继续进行直到所有的边都检查完毕，这样得到的生成子图就是最小生成树。图11.315生成树与最小生成树11.1树与生成树nKruskal算法（1）选取G中权最小的一条边，设为。令（2）若，输出G（S），算法结束。（3）设已选边构成集合。从E-S中选边，使其满足条件：不含圈；在E-S的所有满足条件的边中，有最小的权。（4）转（2）。16生成树与最小生成树PART PART 0101PART PART 0202树与生成树有向树及其应用主要内容11.2有向树及其应用n定义11.5 一个结点的入度为0，其余结点的入度均为1的弱连通有向图，称为有向树。在有向树中，入度为0的结点称为根，出度为0的结点称为叶，出度大于0的结点称为分支结点，从根至任意结点的距离称为该结点的层或级，所有结点的级的最大值称为有向树的高度。n例11.6 图11.4画出了一棵有向树，是根，是叶，是分支结点，定点的层数是1，树的高度是3。图11.418有向树11.2有向树及其应用n定理11.3 设是有向图D的结点。D是以为根的有向树，当且仅当从至D的任意结点恰有一条路径。19有向树11.2有向树及其应用n定义11.6 每个弱分支都是有向树的有向图，称为有向森林。n定义11.7 在有向树中，若从到可达，则称是的祖先，是的后代；又若是根树中的有向边，则称是的父亲，是的儿子；如果两个节点是同一节点的儿子，则称这两个节点是兄弟。20有向树11.2有向树及其应用n定义11.8 在有向树T中，若任何结点的出度最多为m，则称T为m叉树；如果每个分支结点的出度都等于m，则称T为完全m叉树；进一步，若T的全部叶点位于同一层次，则称T为正则m叉树。n例11.7 在图11.5(a)是一棵二叉树，而且是正则二叉树；图11.5(b)是一棵完全二叉树；图11.5(c)是一棵三叉树，而且是正则三叉树；图11.5(d)是一棵完全三叉树。21m叉树图11.511.2有向树及其应用n定理11.4 若T是完全m叉树，其叶数为t，分枝点数为i，则证明：在分枝点中，除根的度数为m外，其余各分枝结点的度皆为m+1。各叶点的度为1，总边数为mi，由图论基本定理得到即这个定理实质上可以用每局有m个选手参加的单淘汰制比赛来说明。t个叶表示t个参赛的选手，i则表示必须按排的总的比赛局数。每一局由m个参赛者中产生一个优胜者，最后决出一个冠军。22m叉树11.2有向树及其应用n例11.8 设有28盏电灯，拟公用一个电源插座，问需要多少块具有四插座的接线板？这个公用插座可以看成是正则四叉树的根，每个接线板看成是其它的分枝点，灯泡看成是叶，则问题就是求总的分枝点的数目，由定理11.4可以算得。因此，至少需要9块接线板才能达到目的。23m叉树11.2有向树及其应用n定义11.9 设V是二叉树D的叶子的集合，R+是全体正实数的集合，W:VR+，则称为加权二叉树。对于D的任意叶v，称W(v)为v的权，称（其中,V是叶子的集合）为的叶加权路径长度，其中W(v)是叶子v的权，L(v)为v的级。我们用叶子表示字母或符号，用分支结点表示判断，用权表示字母或符号出现的机率，则叶加权路径长度就表示算法的平均执行时间。2411.2有向树及其应用n例11.9 图11.6（a）和（b）表示了识别A,B,C,D的两个算法，A,B,C,D出现的概率分别是0.5，0.3，0.05，0.15。图11.6（b）表示的算法优于11.6（a）表示的算法。25图11.611.2有向树及其应用n定义11.10 设是叶加权二叉树。如果对于一切叶加权二叉树只要对于任意正实数r，D和中权等于r的叶的数目相同，就有的叶加权路径长度不大于的叶加权路径长度，则称为最优的。这样，我们把求某问题的最佳算法就归结为求最优二叉树的问题。2611.2有向树及其应用假定我们要找有m片叶，并且它们的权分别为的最优二叉树。不妨设是按递增顺序排列的。即。设是满足要求的最优二叉树，D中以为权的叶分别为。显然，在所有的叶中，和的级最大。不妨设和与同一个分支结点邻接，令，并且，容易证明，是最优的，当且仅当是最优的。这样把求m片叶的最优二叉树归结为求m-1片叶的最优二叉树。继续这个过程，直到归结为求两片叶的最优二叉树，问题就解决了。2711.2有向树及其应用n例11.10 求叶的权分别为0.1、0.3、0.4、0.5、0.5、0.6、0.9的最优二叉树。计算过程如下：所得出的最优二叉树如图11.7所示，叶中的数表示权，所有分支结点中的数之和就是叶加权路径长度。28图11.711.2有向树及其应用n定义11.11 如果在有向树中规定了每一层次上节点的次序，这样的有向树称为有序树。在有序树中规定同一层次节点的次序是从左至右。29有序树11.2有向树及其应用n例11.11 我们可以用有向有序树表达算术表达式，其中叶表示参加运算的数或变量，分支节点表示运算符。如代数式可表示为图11.8的有向有序树。为方便起见，我们借用家族树的名称来称呼有向有序树的结点。如在图11.9中，称是和的父亲，是的长子，是的哥哥，是的弟弟，是的伯父，是的堂兄。30有序树11.2有向树及其应用n定义11.12 一个有向图，如果它的每个连通分支是有向树，则称该有向图为(有向)森林；在森林中，如果所有树都是有序树且给树指定了次序，则称此森林是有序森林。例如，图11.11是一个有序森林。在图11.10中，（a）和（b）是相同的有向有序树，因为同一级上结点的次序相同。但是如果考虑结点之间的相对位置，他们就不同了。在（a）中，位于的左下方；而在（b）中，位于的右下方，它们是不同的位置有向有序树。31有序树图11.10图11.1111.2有向树及其应用n定义11.13 为每个分支结点的儿子规定了位置的有向有序树，称为位置有序树。在位置二元有向有序树中，可用字母表0,1上的字符串唯一地表示每个结点。用空串表示根。设用表示某分支结点，则用表示它的左儿子，用表示它的右儿子。这样，每个结点都有了唯一的编码表示，并且不同结点的编码表示不同。如在图11.12的（a）中，的编码表示分别为,0,1,00,10,11。位置二元有向有序树全体叶的编码表示的集合称为它的前缀编码。如图11.12的（a）的前缀编码是00,10,11。不同的位置二元有向有序树有不同的前缀编码。这种表示方法便于用计算机存贮位置二元有向有序树。32有序树11.2有向树及其应用在二叉树编码中，显然每两个叶点的码都不可能一个是另一个前缀，因为要成为前缀则必然有祖先和后裔的关系，这与叶的定义不合。例如集合000，001，010，1是前缀码；集000，1001，01，00则不是前缀码，因为00是000的前缀。显然，采用前缀码可以唯一确定接收的符号串内容。例如000，001，010，1为前缀码，当接收的符号串为，则可译为1，001，010，001，001。33有序树11.2有向树及其应用n例11.12 图11.12是由前缀码000，001，01，10，11构造二叉树的例子，（a）中黑点表示前缀码中每个序列对应的叶，（b）是最后得到的编码二叉树。图11.1234有序树11.2有向树及其应用可以在有向有序森林和位置二元有向有序树之间建立一一对应关系。在有向有序森林中，我们称位于左边的有向有序树的根为位于右边的有向有序树的根的哥哥。设与有向有序森林F对应的位置二元有向有序树为T。我们规定，它们有相同的结点。在F中，若是的长子，则在T中是的左儿子。在F中，若是的大弟，则在T中，是的右儿子。这中对应关系称为有向有序森林和位置二元有向有序树之间的自然对应关系。例如，图11.13中（a）是有向有序森林，（b）是对应的位置二元有向有序树。图11.1335有序树11.2有向树及其应用显然当森林中只有一棵树时，上面的转化方法就是把任意m元树转化成二元有向有序树的方法了。从上面的讨论我们可以作出以下的结论：如果一个实际问题可以抽象成一个图，则可以将这个图转化成树（求这个图的生成树），对任何一棵树都可以转化成与其对应的二元树，对二元树我们可以方便地在计算机中存贮与访问。下面我们就来介绍二元树的存贮与访问方式。利用连接分配技术可以方便地表示二元树，其中所包含的结点结构为：这里，LLINK或RLINK分别包含一个指向所论结点的左子树或右子树的指针（或称指示数、指示字）、DATA包含与这个结点有关的信息。36有序树LLINKDATARLINK11.2有向树及其应用n数据结构中，在使用树作数据结构时，经常需要遍访二元有序树的每一个节点，就是检查存储于树中的每一数据项。对于一棵根树的每一个节点都访问一次且仅访问一次称为遍历或周游一棵树。二叉树的遍历算法主要有下列3种。（1）前序遍历算法前序遍历算法的访问次序为：访问根；在根的左子树上执行前序遍历；在根的右子树上执行前序遍历。37二叉树的遍历11.2有向树及其应用（2）中序遍历算法中序遍历算法的访问次序为：在根的左子树上执行中序遍历算法；访问根；在根的右子树上执行中序遍历算法。（3）后序遍历算法后序遍历算法的访问次序为：在根的左子树上执行后序遍历算法；在根的右子树上执行后序遍历算法；访问根。38二叉树的遍历11.2有向树及其应用如果某一子树是空的（即该结点没有左或右的子孙时）则所谓周游就什么也不执行。换句话说，当遇到空子树时，则它被认为已完全周游了。如图11.14所示的树，其前序周游、中序周游和后序周游将按下列次序处理结点。ABCDEFGH（前序）CBDAEGHF（中序）CDBHGFEA（后序）39二叉树的遍历图11.1411.2有向树及其应用既然周游时，要求向下而后又要往上追溯树的一部分，所以允许往上追溯树时的指针信息必须暂时保存起来（如图11.14（b）。注意到已表示在树中的结构信息，使得从树根往下运动是可能的，但往上运动必须采取与往下运动相反的手法，因此在周游树时，要求有一个栈保留指针的值。现在我们给出前序周游的算法。40二叉树的遍历11.2有向树及其应用nPREORDER算法：给定一棵二元树,它的根结点地址是变量T，它的结点结构和上面描述的相同，本算法按前序周游这棵二元树。利用一个辅助栈S，S的顶点元素的下标是TOP，P是一个临时变量,它表示我们处在这棵树中的位置。1置初态如果T=NULL，则退出(树无根,因此不是真的二元树)；否则PT；TOP0。2访问结点，右分枝地址进栈，并转左处理结点P。如果PRLINK(P)NULL，则置TOPTOP+1；STOPRLINK(P)；PLLINK(P)。3链结束否?如果PNULL，则转向第2步。4右分枝地址退栈如果TOP=0则退出；否则令PSTOP；TOPTOP-1，并转向第2步。41PREORDER算法11.2有向树及其应用其中，算法的第2步和第3步是访问和处理结点。如果该结点的右分枝地址存在的话，则让它进栈，并跟踪左分枝链直到这个链结束。然后进入第4步，并将最近遇到的右子树根结点的地址从栈中删除，再按第2步与第3步处理它。对于图11.14的二元树，追踪上述算法后地址记为“NE”。在这里，所谓访问结点就是输出它的标号。42PREORDER算法栈的内容P访问P输出串NAAANENBBABNE NDNCCABCNE NDNULLNENDDABCDNENULLNEEABCDENFNULLNFFABCDEFNGGABCDEFGNHNULLNHHABCDEFGHNULL11.2有向树及其应用n例11.13 设有n根火柴，甲乙两人依次从中取走1或2根，但不能不取，谁取走最后一根谁就是胜利者。为了说明方法，不妨设n=6。在图11.15中6表示轮到甲取时有6根火柴，4表示轮到乙取时有4根火柴，以此类推。显然，一当出现1或2状态，甲取胜，不必再搜索下去。同样，1或2是乙取胜的状态。图11.15搜索树43搜索树11.2有向树及其应用若甲取胜时，设其得分为1，乙取胜时甲的得分为-1。无疑，轮到甲作出判决时，他一定选（-1，1）中的最大者；而轮到乙作出判决时，他将选取使甲失败，选+1、-1中最小者。这个道理是显而易见的。比如甲遇到图11.16（a）的状态时，甲应选max(1,-1)=1，即甲应取1根火柴使状态进入。同理，乙遇到图11.16（b）的状态时，乙应选取max(-1,1)=-1，使甲进入必然失败的状态为好。如图11.15所示，开始时若有6根火柴，先下手者败局已定，除非对手失误。44搜索树图11.1611.2有向树及其应用下面我们将举例介绍搜索树的DFS算法（深度优先搜索(DeepFirstSearch)）。DFS算法的基本思想如下：（1）当E(G)的所有边未经完全搜索时，任取一结点，给以标志且入栈（以先入后出为原则叫做栈，先入先出者叫做队）。（2）对与点关联的边依次进行搜索时，当存在另一端点未给标志的边时，把另一端点作为，给以标志，并且入栈；转（2）。（3）当与关联的边全部搜索完毕时（即不存在以为端点而未经搜索的边时），则以点从栈顶退出，即让取走后的栈顶元素作为转（2）。（4）若栈已空，但还存在未给标志的节点时，取其中任一结点作转（2）。若所有节点都已给标志时，则算法终止。45DFS算法11.2有向树及其应用n例如图11.17的邻接矩阵为设从开始，给以标志，与相邻的节点依次为，即由于第一个邻接点未给标志，故入栈且给标志。但，而第一个邻接结点已给标志，故取边，给以标志，且入栈。又，由于，都已给标志，故取边，给以标志并入栈，但与相邻的结点全部都给了标志，故退栈。此时栈顶点为，但与相邻的结点均已给标志，故退栈。，因类似理由依次退栈。栈空，故结束。46DFS算法图11.1711.2有向树及其应用n例11.14 设有一个44的棋盘，当一个棋子放到其中一个格子里去以后，则这格子所在的行和列以及对角线上所有的格子都不允许放别的棋子。现在有4个棋子，试问它在这个棋盘上有哪几种容许的布局？第一行的格子有4个，故第一行有4种选择，第二行则有3种选择；第三行则有2种选择；最后一行无选择的余地。它的状态可用下面的图11.18的树表示。图11.184711.2有向树及其应用可能状态如图11.19所示的那样，要确定哪几种状态是被允许的，就要对这棵树进行搜索。一旦某结点被判定为不被容许，这个结点下的树枝可以全部剪去。比如i=1时，j=2不被容许，则i=1，j=2，k=3（或4）便无需搜索。现在把搜索的过程形象地列表于图11.19中，搜索过程则表示于图11.20中。图11.20图11.214849谢谢！