《树的遍历与生成树.ppt》由会员分享，可在线阅读，更多相关《树的遍历与生成树.ppt（49页珍藏版）》请在三一办公上搜索。
1、第7章 树Tree,不包含简单回路的连通图称为树，早在1857年英国数学家亚瑟凯莱就用树去计数某些类型的化合物。随后树已经被用来解决各种学科分支里的问题。,Chap 7 树,7.1 树的概念/Introduction of Trees7.2 树的应用/Applications of Trees7.3 树的遍历/Tree Traversal7.4 生成树和最小生成树/Spanning Trees and minimum Spanning Trees,有序根树常常用来保存信息，因此掌握访问有序根树的每个顶点以存取数据信息的算法非常必要系统地访问有序根树每个顶点的过程都称为遍历算法前序遍历 Preo
2、rder traversal中序遍历 Inorder traversal后序遍历 Postorder traversal,7.3 树的遍历Tree Traversal,定义1 设T是带根r的有序根树。若T只包含r，则r是T的前序遍历。否则T1，T2，Tn是T里在r处从左到右的子树。前序遍历首先访问r。接着以前序来遍历T1，然后以前序来遍历T2，依此类推，直到以前序遍历了Tn为止。,7.3 树的遍历Tree Traversal,例1 前序遍历是以什么顺序访问图中有序根树里的顶点的？,7.3 树的遍历Tree Traversal,a b e j k n o p f c d g l m h i,定义
3、2 设T是带根r的有序根树。若T只包含r，则r是T的中序遍历。否则T1，T2，Tn是T里在r处从左到右的子树。中序遍历首先以中序来遍历T1，然后访问r，接着以中序遍历T2，以中序遍历T3，依此类推，直到以中序遍历了Tn为止。,7.3 树的遍历Tree Traversal,例2 中序遍历是以什么顺序访问图中有序根树里的顶点的？,7.3 树的遍历Tree Traversal,j e n k o p b f a c l g m d h i,定义3 设T是带根r的有序根树。若T只包含r，则r是T的后序遍历。否则T1，T2，Tn是T里在r处从左到右的子树。后序遍历首先以后序来遍历T1，以后序遍历T2，然
4、后以后序遍历Tn，最后访问r。,7.3 树的遍历Tree Traversal,例3 后序遍历是以什么顺序访问图中有序根树里的顶点的？,7.3 树的遍历Tree Traversal,j n o p k e f b c l m g h i d a,7.3 树的遍历Tree Traversal,7.3 树的遍历Tree Traversal,7.3 树的遍历Tree Traversal,以前序、中序、后序来列出有序根树的顶点的简易方法：首先从根开始围绕有序根树画一条曲线，沿着边移动；,7.3 树的遍历Tree Traversal,前序：当曲线第一次经过一个顶点时，就列出这个顶点,中序：当曲线第一次经过
5、一个树叶时，就列出这个树叶，当曲线第二次经过一个内点时就列出这个内点,后序：当曲线最后一次经过一个顶点而返回这个顶点的父母时，就列出这个顶点,练习：写出该有序根图按照前序、中序、后序遍历访问的顶点顺序,7.3 树的遍历Tree Traversal,前序：abdefgc中序：dbfegac后序：dfgebca,中缀、前缀、后缀记法(Infix,prefix,postfix notation),7.3 树的遍历Tree Traversal,可用有序树来表示复杂的表达式包括算术表达式、复合命题、集合的组合等,表示算术表达式时内点表示运算，树叶表示变量或数字，每个运算都作用在它的子树上,例4 表示表达
6、式(x+y)2)+(x-4)/3)的有序根树是什么？,中缀、前缀、后缀记法(Infix,prefix,postfix notation),7.3 树的遍历Tree Traversal,对表示一个表达式的有序根树的中序遍历，产生原来的表达式,中缀、前缀、后缀记法(Infix,prefix,postfix notation),7.3 树的遍历Tree Traversal,对表示一个表达式的二叉树的中序遍历，产生原来的表达式中序遍历得出的中缀表达式有二义性为避免二义性，中序遍历时需加括号，这种表达式称为中缀形式,(x+y)/(x+3),(x+(y/x)+3,x+(y/(x+3),中序遍历?,x+y/
7、x+3,中缀、前缀、后缀记法(Infix,prefix,postfix notation),7.3 树的遍历Tree Traversal,当以前序来遍历表达式的二叉树时，就获得它的前缀形式，又称波兰记法前缀记法下的表达式无二义性,前缀形式？,+xy2/-x43,已知前缀形式，如何获得对应的表达式呢？,从右向左地求对应的表达式当遇到一个运算，就对在这个运算右边紧邻的两个运算对象执行相应的运算每个运算结果是新的运算对象,例5 前缀表达式+-*2 3 5/2 3 4的值是什么？,7.3 树的遍历Tree Traversal,中缀、前缀、后缀记法(Infix,prefix,postfix notati
8、on),7.3 树的遍历Tree Traversal,当以后序来遍历表达式的二叉树时，就获得它的后缀形式，又称逆波兰记法后缀记法下的表达式无二义性,后缀形式？,xy+2x4-3/+,已知后缀形式，如何获得对应的表达式呢？,从左向右地求对应的表达式当两个运算对象后面接着一个运算时，就执行这个运算每个运算结果是新的运算对象,例6 后缀表达式7 2 3*-4 9 3/+的值是什么？,7.3 树的遍历Tree Traversal,7.3 树的遍历Tree Traversal,例：求复合命题 的有序根树，然后基于这个根树求这个表达式的前缀、中缀、后缀形式。,中缀形式：前缀形式：后缀形式：,三种记法特点总
9、结,中缀记法的顺序与原表达式相同，但容易产生二义性，故需要加括号；前缀与后缀记法虽然与原表达式顺序不相同，但因无二义性，且不需要来回扫描，所以被广泛用于计算机的编译系统；,作业,P333：针对4题的图写出前序遍历、中序遍历和后序遍历的顶点顺序。8,11(a),Chap 7 树,7.1 树的概念/Introduction of Trees7.2 树的应用/Applications of Trees7.3 树的遍历/Tree Traversal7.4 生成树和最小生成树/Spanning Trees and minimum Spanning Trees,7.4 生成树和最小生成树Spanning
10、Trees and minimum Spanning Trees,缅因州的道路系统图,高速公路部门怎么扫尽可能少的雪，使得州内任两个乡镇都有干净的道路？,确保任两个乡镇都有通路，且不能有多余的边。,求一个包含该图所有顶点的树（5条边）,定义1生成树：无向简单图G=(V,E)的生成子图T是树，则称T为G的生成树/spanning tree。T=(V,E),EE,例1 找出下面简单图的生成树。,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,证明：必要性：T是生成子图，包含G的所有顶点，T是树，T连通，则G连通。充分性：若G是连通的,1
11、)若G无回路，则G本身是树，即生成树。2)若存在回路，去掉回路中任一边，不影响连通性，也不减少顶点.所有回路都移去一条边，剩下的子图包含所有顶点，又是无回路的连通图，即为生成树。,注：移去边时可随意，故生成树不唯一。,定理1 无向简单图G=(V,E)存在生成树的充要条件是G是连通的。,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,为了从源计算机发送数据到多个接收计算机（一个子网），可以分别发送数据到每个计算机单点广播但单点广播是无效的，因为网络上存有发送的相同数据的多个副本,生成树的应用IP组播,7.4 生成树和最小生成树Span
12、ning Trees and minimum Spanning Trees,路由子网带接收站的子网,有效的方法IP组播源计算机在网络上发送数据的单一副本，当数据到达中间路由器时，就把数据分发到一个或更多的其他路由器，以便接收计算机都可在它们不同的子网里最终接收到数据,生成树的应用IP组播,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,路由子网带接收站的子网,为了让数据尽可能快地到达接收计算机，在数据穿过网络的通路里不应当存在环路以组播源、路由器和包含接收计算机的子网作为顶点，以边表示计算机和/或路由器之间的连接，构造IP网络的生成
13、树,生成树的应用IP组播,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,路由子网带接收站的子网,思路：首先按照深度优先搜索获得简单图的一个根树，根树对应的无向图即简单图的生成树DFS：任选图中一个顶点作为根，通过相继添加边来形成从这个顶点开始的通路，其中每条新边都与通路上的最后一个顶点以及还不在通路上的一个顶点关联。尽可能地添加边到这条通路，如该通路经了所有顶点，即为生成树，否则退到该通路的倒数第二个顶点，若有可能，则形成从这个顶点上开始的经过还没有访问过的顶点的通路。若不行，则后退到通路的另外一个顶点，再试；直到经过了所有顶点,
14、生成树的建立方法深度优先搜索depth-first search,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,生成树的建立方法深度优先搜索depth-first search,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,例2 用深度优先搜索找出下图的生成树,生成树的建立方法深度优先搜索depth-first search,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,O(e)或O(n2),思路：首先按
15、照宽度优先搜索获得简单图的一个根树，根树对应的无向图即简单图的生成树BFS：任选图中一个顶点作为根，然后添加与这个顶点关联的所有边，添加的顶点成为生成树在1层的顶点（任意排序）按顺序访问1层上的每个顶点：只要不产生回路，就将与这个顶点相关联的每条边添加到树，产生2层的顶点遵循相同的过程，直到已经添加了所有顶点因为BFS的结果无回路，且是包含所有顶点的连通图，故是图的生成树,生成树的建立方法宽度优先搜索breadth-first search,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,7.4 生成树和最小生成树Spanning
16、Trees and minimum Spanning Trees,例3 用宽度优先搜索找出下图的生成树,生成树的建立方法宽度优先搜索breadth-first search,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,O(e)或O(n2),生成树的建立方法宽度优先搜索breadth-first search,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,问题：一个公司建立一个通信网络来连接它的五个计算机中心，可以租用电话线连接这些中心的任何一对，应当建立哪些连接，以
17、便保证任两个计算机中心都有通路，且网络成本最小？,首先要尽可能少的边，只要保证任两个顶点连通,其次边上的权值之和尽可能的小（最小）,顶点：计算机中心边：可能租用的电话线边上的权：月租费,求图的生成树,求最小生成树,定义 最小生成树：设连通加权图G=(V,E,W)，T=(V,E)是G的生成树，称w(T)=为T的权，使权w(T)达到最小值的G的生成树称的G的最小生成树。,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,定义2 最小生成树：连通加权图里的最小生成树是具有最小可能的边的权之和的生成树。,最小生成树的求解算法普林算法 和 克鲁
18、斯卡尔算法都是基于贪心思想：添加还没使用的、具有规定性质的、权最小的边进行,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,普林算法 Prims algorithm：首先选择带最小权的边，把它放进生成树里相继地向树里添加与已在树里的顶点关联的、并且不与已在树里的边形成简单回路的权最小的边当已经添加了n-1条边时就停止。,procedure Prim(G:带n个顶点的连通无向图)T:=权最小的边for i:=1 to n-2 begin e:=与T里顶点关联、且若添加到T里则不形成简单回路的权最小的边 T:=添加e之后的Tend T
19、是G的最小生成树,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,例4 用普林算法求下图的最小生成树,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,例5 用普林算法求下图的最小生成树,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,克鲁斯卡尔算法 Kruskals algorithm：添加图中权最小的一条边到生成树相继添加不与已经选择的边形成简单回路的权最小的边在已经挑选了n-1条边之后停止,procedur
20、e Kruskal(G:带n个顶点的带权连通无向图)T:=空图for i:=1 to n-1 begin e:=当添加到T里不形成简单回路的G中权最小边T:=添加e之后的Tend T 是G的最小生成树,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,例6 用克鲁斯卡尔算法求下图的最小生成树,生成树不唯一，但每个最小生成树的权都是相等的！,7.4 生成树和最小生成树Spanning Trees and minimum Spanning Trees,例7 用克鲁斯卡尔算法求下图的最小生成树,解题过程：(1）边排序:(v1,v2),(v2
21、,v7),(v1,v6),(v6,v7)(v1,v4),(v5,v6),(v4,v5),(v3,v4),(v3,v8)(v5,v8),(v2,v3),(v7,v8)(2)选s1=e1 e1=(v1,v2)(3)选e2=(v2,v7)(4)e3=(v1,v6)(5)e4=(v1,v4)=5(6)e5=(v5,v6)=6(7)e6=(v3,v4)=8(8)e7=(v3,v8),小 结,1、生成树的定义与存在的充分必要条件2、生成树的深度优先搜索DFS和宽度优先搜索BFS解法3、最小生成树的定义与求法（Prim、Kruskal算法）,进一步的思考,1、求最小生成树的其他方法2、最大生成树问题,作业,P342：用DFS和BFS求2题中简单图的生成树P347：2、4,
