离散数学第十一章树.ppt

第十一章 树 离散数学 陈志奎主编 人民邮电出版社 前言 n1847年，德国学者柯希霍夫（Kirchhof）在研究物理问题时提出了树 的概念。他用一类线性方程组来描述一个电路网络的每一条支路中和环 绕每一个回路的电流。他像数学家一样抽象地思考问题：用一个只由点 和线组成的相应的组合结构来代替原来的电路网络，而并不指明每条线 所代表的电器元件的种类。事实上，他把每个电路网络用一个基本图来 代替。为了解相应的方程组，他用一种结构方法指出，只要考虑一个图 的任何一个“生成树”所决定的那些独立圈就够了。他的方法现已成为 图论中的标准方法。 前言 n1857年，英国数学家凯莱（Caylay Arthur）从事计数由给定的碳原子 数n的饱和碳氢化合物的同分异构物时，独立地提出了树的概念。凯莱把 这个问题抽象地叙述为：求有P个点的树的数目，其中每个点的度等于1 或4，树上的点对应一个氢原子或一个碳原子。凯莱的工作是图的计数理 论的起源。法国数学家若尔当在1869年作为一个纯数学对象独立地发现 了树，他并不知道树与现代的化学学说有关。 n1889年凯莱给出了完全图Kn的概念。 前言 n1956年Kruskal设计了求最优树的有效算法。 n树是一类既简单而又非常重要的图，是计算机中一种基本的数据结构和 表示方法，在输电网络分析设计、有机化学、最短连接及渠道设计等领 域也都有广泛的应用。 n本章将对树进行详细的讨论，主要包括树的基本性质和生成树，以及有 向树中的m叉树、有序树和搜索树等。 PART PART 0101 PART 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.1 7 树及其性质 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.2 11 生成树与最小生成树 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.3 15 生成树与最小生成树 11.1 树与生成树 nKruskal算法 （1）选取G中权最小的一条边，设为 。令 （2）若 ，输出G（S），算法结束。 （3）设已选边构成集合 。从E-S中选边 ，使其满足条件： 不含圈； 在E-S的所有满足条件的边中， 有最小的权。 （4） 转（2）。 16 生成树与最小生成树 PART PART 0101 PART PART 0202 树与生成树 有向树及其应用 主要内容 11.2 有向树及其应用 n定义11.5 一个结点的入度为0，其余结点的入度均为1的弱连通有向图 ，称为有向树。在有向树中，入度为0的结点称为根，出度为0的结点称为 叶，出度大于0的结点称为分支结点，从根至任意结点的距离称为该结点 的层或级，所有结点的级的最大值称为有向树的高度。 n例11.6 图11.4画出了一棵有向树， 是根， 是叶， 是分支 结点，定点 的层数是1，树的高度是3。 图11.4 18 有向树 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)是一棵完全三叉树 。 21 m叉树 图11.5 11.2 有向树及其应用 n定理11.4 若T是完全m叉树，其叶数为t，分枝点数为i，则 证明：在分枝点中，除根的度数为m外，其余各分枝结点的度皆为m+1。 各叶点的度为1，总边数为mi，由图论基本定理得到 即 这个定理实质上可以用每局有m个选手参加的单淘汰制比赛来说明。t个叶表 示t个参赛的选手，i则表示必须按排的总的比赛局数。每一局由m个参赛者中产生 一个优胜者，最后决出一个冠军。 22 m叉树 11.2 有向树及其应用 n例11.8 设有28盏电灯，拟公用一个电源插座，问需要多少块具有四插 座的接线板？ 这个公用插座可以看成是正则四叉树的根，每个接线板看成是其它的 分枝点，灯泡看成是叶，则问题就是求总的分枝点的数目，由定理11.4可 以算得 。因此，至少需要9块接线板才能达到目的。 23 m叉树 11.2 有向树及其应用 n定义11.9 设V是二叉树D的叶子的集合，R+是全体正实数的集合， W:VR+，则称为加权二叉树。对于D的任意叶v，称W(v)为v的 权 ，称 （其中 ,V是叶子的集合）为的叶加权路 径长度，其中W(v)是叶子v的权，L(v)为v的级。 我们用叶子表示字母或符号，用分支结点表示判断，用权表示字母或符号出现 的机率，则叶加权路径长度就表示算法的平均执行时间。 24 11.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.6 11.2 有向树及其应用 n定义11.10 设是叶加权二叉树。如果对于一切叶加权二叉树 只要对于任意正实数r，D和 中权等于r的叶的数目相同，就 有的叶加权路径长度不大于 的叶加权路径长度，则称 为最优的。 这样，我们把求某问题的最佳算法就归结为求最优二叉树的问题。 26 11.2 有向树及其应用 假定我们要找有m片叶，并且它们的权分别为 的最优二 叉树。不妨设 是按递增顺序排列的。 即 。设是满足要求的最优二叉树，D中以 为权的叶分别为 。显然，在所有的叶中， 和 的级最大。不妨设 和 与同一个分支结点 邻接，令 ，并且 ， 容易证明，是最优的，当且仅当 是最优的。这样把求m 片叶的最优二叉树归结为求m-1片叶的最优二叉树。继续这个过程，直到 归结为求两片叶的最优二叉树，问题就解决了。 27 11.2 有向树及其应用 n例11.10 求叶的权分别为0.1、0.3、0.4、0.5、0.5、0.6、0.9的最优二叉树。 计算过程如下： 所得出的最优二叉树如图11.7所示，叶中的数表示权，所有分支结点中的数之 和就是叶加权路径长度。 28 图11.7 11.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.11 11.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为前缀码，当接收的符号串为1001010001001，则可译为1，001，010，001， 001。 33 有序树 11.2 有向树及其应用 n例11.12 图11.12是由前缀码000，001，01，10，11构造二叉树的例子，（a ）中黑点表示前缀码中每个序列对应的叶，（b）是最后得到的编码二叉树。 图11.12 34 有序树 11.2 有向树及其应用 可以在有向有序森林和位置二元有向有序树之间建立一一对应关系。在有向有 序森林中，我们称位于左边的有向有序树的根为位于右边的有向有序树的根的哥哥 。设与有向有序森林F对应的位置二元有向有序树为T。我们规定，它们有相同的结 点。在F中，若 是 的长子，则在T中 是 的左儿子。在F中，若 是 的大弟，则在T中 ， 是 的右儿子。这中对应关系称为有向有序森林和位置二元有向有序树之间的自 然对应关系。例如，图11.13中（a）是有向有序森林，（b）是对应的位置二元有 向有序树。 图11.13 35 有序树 11.2 有向树及其应用 显然当森林中只有一棵树时，上面的转化方法就是把任意m元树转化成二元有 向有序树的方法了。 从上面的讨论我们可以作出以下的结论：如果一个实际问题可以抽象成一个图 ，则 可以将这个图转化成树（求这个图的生成树），对任何一棵树都可以转化成与 其对应的二元树，对二元树我们可以方便地在计算机中存贮与访问。下面我们就来 介绍二元树的存贮与访问方式。利用连接分配技术可以方便地表示二元树，其中所 包含的结点结构为： 这里，LLINK或RLINK分别包含一个指向所论结点的左子树或右子树的指针（或称 指示数、指示字）、DATA包含与这个结点有关的信息。 36 有序树 LLINKDATARLINK 11.2 有向树及其应用 n数据结构中，在使用树作数据结构时，经常需要遍访二元有序树的每一 个节点，就是检查存储于树中的每一数据项。对于一棵根树的每一个节点 都访问一次且仅访问一次称为遍历或周游一棵树。二叉树的遍历算法主要 有下列3种。 （1）前序遍历算法 前序遍历算法的访问次序为： 访问根； 在根的左子树上执行前序遍历； 在根的右子树上执行前序遍历。 37 二叉树的遍历 11.2 有向树及其应用 （2）中序遍历算法 中序遍历算法的访问次序为： 在根的左子树上执行中序遍历算法； 访问根； 在根的右子树上执行中序遍历算法。 （3）后序遍历算法 后序遍历算法的访问次序为： 在根的左子树上执行后序遍历算法； 在根的右子树上执行后序遍历算法； 访问根。 38 二叉树的遍历 11.2 有向树及其应用 如果某一子树是空的（即该结点没有左或右的子孙时）则所谓周游就什么也不 执行。换句话说，当遇到空子树时，则它被认为已完全周游了。 如图11.14所示的树，其前序周游、中序周游和后序周游将按下列次序处理结 点。 ABCDEFGH （前序） CBDAEGHF （中序） CDBHGFEA （后序） 39 二叉树的遍历 图11.14 11.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步。 41 PREORDER算法 11.2 有向树及其应用 其中，算法的第2步和第3步是访问和处理结点。如果该结点的右分枝地址存在 的话，则让它进栈，并跟踪左分枝链直到这个链结束。然后进入第4步，并将最近 遇到的右子树根结点的地址从栈中删除，再按第2步与第3步处理它。对于图11.14 的二元树，追踪上述算法后地址记为“NE”。在这里，所谓访问结点就是输出它的 标号。 42 PREORDER算法 栈的内容P访问P输出串 NAAA NENBBAB NE NDNCCABC NE NDNULL NENDDABCD NENULL NEEABCDE NFNULL NFFABCDEF NGGABCDEFG NHNULL NHHABCDEFGH NULL 11.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.16 11.2 有向树及其应用 下面我们将举例介绍搜索树的DFS算法（深度优先搜索(DeepF