7.3~7.4树的遍历与生成树

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,lholder,*,第,7,章 树,Tree,不包含简单回路的连通图称为树，,早在,1857,年英国数学家亚瑟,凯莱就用树去计数某些类型的化合物。随后树已经被用来解决各种学科分支里的问题。,Chap 7,树,7.1,树的概念,/Introduction of Trees,7.2,树的应用,/Applications of Trees,7.3,树的遍历,/Tree Traversal,7.4,生成树和最小生成树,/,Spanning Trees and minimum Spanning Trees,有序根树常常用来保存信息，因此掌握访问有序根树的每个顶点以存取数据信息的算法非常必要,系统地访问有序根树每个顶点的过程都称为遍历算法,前序遍历,Preorder traversal,中序遍历,Inorder traversal,后序遍历,Postorder traversal,7.3,树的遍历,Tree Traversal,定义,1,设,T,是带根,r,的有序根树。若,T,只包含,r,，则,r,是,T,的前序遍历。否则,T,1,，,T,2,，,，,T,n,是,T,里在,r,处从左到右的子树。,前序遍历,首先访问,r,。接着以前序来遍历,T,1,，然后以前序来遍历,T,2,，依此类推，直到以前序遍历了,T,n,为止。,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,定义,2,设,T,是带根,r,的有序根树。若,T,只包含,r,，则,r,是,T,的中序遍历。否则,T,1,，,T,2,，,，,T,n,是,T,里在,r,处从左到右的子树。,中序遍历,首先,以中序来遍历,T,1,，,然后访问,r,，接着,以中序遍历,T,2,，以中序遍历,T,3,，依此类推，直到以中序遍历了,T,n,为止,。,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,的后序遍历。否则,T,1,，,T,2,，,，,T,n,是,T,里在,r,处从左到右的子树。,后序遍历,首先,以后序来遍历,T,1,，,以后序遍历,T,2,，,，然后,以后序遍历,T,n,，,最后访问,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,前序,：当曲线第一次经过一个顶点时，就列出这个顶点,中序,：当曲线第一次经过一个树叶时，就列出这个树叶，当曲线第二次经过一个内点时就列出这个内点,后序,：当曲线最后一次经过一个顶点而返回这个顶点的父母时，就列出这个顶点,练习：,写出该有序根图按照前序、中序、后序遍历访问的顶点顺序,7.3,树的遍历,Tree Traversal,前序：,abdefgc,中序：,dbfegac,后序：,dfgebca,中缀、前缀、后缀记法,(,Infix,prefix,postfix notation),7.3,树的遍历,Tree Traversal,可用有序树来表示复杂的表达式,包括算术表达式、复合命题、集合的组合等,表示算术表达式时内点表示运算，树叶表示变量或数字，每个运算都作用在它的子树上,例,4,表示表达式,(,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,/,x,+3,中缀、前缀、后缀记法,(Infix,prefix,postfix notation),7.3,树的遍历,Tree Traversal,当以前序来遍历表达式的二叉树时，就获得它的,前缀形式,，又称波兰记法,前缀记法下的表达式无二义性,前缀形式？,+,+,xy,2/-,x,43,已知前缀形式，如何获得对应的表达式呢？,从右向左地求对应的表达式,当遇到一个运算，就对在这个运算右边紧邻的两个运算对象执行相应的运算,每个运算结果是新的运算对象,例,5,前缀表达式,+-*2 3 5/,2 3 4,的值是什么？,7.3,树的遍历,Tree Traversal,中缀、前缀、后缀记法,(Infix,prefix,postfix notation),7.3,树的遍历,Tree Traversal,当以后序来遍历表达式的二叉树时，就获得它的,后缀形式,，又称逆波兰记法,后缀记法下的表达式无二义性,后缀形式？,xy,+2,x,4-3/+,已知后缀形式，如何获得对应的表达式呢？,从左向右地求对应的表达式,当两个运算对象后面接着一个运算时，就执行这个运算,每个运算结果是新的运算对象,例,6,后缀表达式,7 2 3*-4,9 3/+,的值是什么？,7.3,树的遍历,Tree Traversal,7.3,树的遍历,Tree Traversal,例：求复合命题 的有序根树，然后基于这个根树求这个表达式的前缀、中缀、后缀形式。,中缀形式：,前缀形式：,后缀形式：,三种记法特点总结,中缀记法的顺序与原表达式相同，但容易产生二义性，故需要加括号；,前缀与后缀记法虽然与原表达式顺序不相同，但因无二义性，且不需要来回扫描，所以被广泛用于计算机的编译系统；,作业,P333,：,针对,4,题的图写出前序遍历、中序遍历和后序遍历的顶点顺序。,8,11(a),Chap 7,树,7.1,树的概念,/Introduction of Trees,7.2,树的应用,/Applications of Trees,7.3,树的遍历,/Tree Traversal,7.4,生成树和最小生成树,/,Spanning Trees and minimum Spanning Trees,7.4,生成树和最小生成树,Spanning Trees and minimum Spanning Trees,缅因州的道路系统图,高速公路部门怎么扫尽可能少的雪，使得州内任两个乡镇都有干净的道路？,确保任两个乡镇都有通路，且不能有多余的边。,求一个包含该图所有顶点的树（,5,条边）,定义,1,生成树：无向简单图,G=(V,E),的生成子图,T,是树，则称,T,为,G,的,生成树,/spanning tree,。,T=(V,E),E,E,例,1,找出下面简单图的生成树。,7.4,生成树和最小生成树,Spanning Trees and minimum Spanning Trees,证明：,必要性,：,T,是生成子图，包含,G,的所有顶点，,T,是树，,T,连通，则,G,连通。,充分性,：若,G,是连通的,1),若,G,无回路，则,G,本身是树，即生成树。,2),若存在回路，去掉回路中任一边，不影响连通性，也不减少顶点,.,所有回路都移去一条边，剩下的子图包含所有顶点，又是无回路的连通图，即为生成树。,注：移去边时可随意，故生成树不唯一。,定理,1,无向简单图,G=(V,E),存在生成树的充要条件是,G,是连通的。,7.4,生成树和最小生成树,Spanning Trees and minimum Spanning Trees,为了从源计算机发送数据到多个接收计算机（一个子网），可以分别发送数据到每个计算机,单点广播,但单点广播是无效的，因为网络上存有发送的相同数据的多个副本,生成树的应用,IP,组播,7.4,生成树和最小生成树,Spanning Trees and minimum Spanning Trees,路由,子网,带接收站的子网,有效的方法,IP,组播,源计算机在网络上发送数据的单一副本，当数据到达中间路由器时，就把数据分发到一个或更多的其他路由器，以便接收计算机都可在它们不同的子网里最终接收到数据,生成树的应用,IP,组播,7.4,生成树和最小生成树,Spanning Trees and minimum Spanning Trees,路由,子网,带接收站的子网,为了让数据尽可能快地到达接收计算机，在数据穿过网络的通路里不应当存在环路,以组播源、路由器和包含接收计算机的子网作为顶点，以边表示计算机和,/,或路由器之间的连接，构造,IP,网络的生成树,生成树的应用,IP,组播,7.4,生成树和最小生成树,Spanning Trees and minimum Spanning Trees,路由,子网,带接收站的子网,思路：首先按照深度优先搜索获得简单图的一个根树，根树对应的无向图即简单图的生成树,DFS,：,任选图中一个顶点作为根，通过相继添加边来形成从这个顶点开始的通路，其中每条新边都与通路上的最后一个顶点以及还不在通路上的一个顶点关联。,尽可能地添加边到这条通路，如该通路经了所有顶点，即为生成树，否则退到该通路的倒数第二个顶点，若有可能，则形成从这个顶点上开始的经过还没有访问过的顶点的通路。若不行，则后退到通路的另外一个顶点，再试；直到经过了所有顶点,生成树的建立方法,深度优先搜索,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(,n,2,),思路：首先按照宽度优先搜索获得简单图的一个根树，根树对应的无向图即简单图的生成树,BFS,：,任选图中一个顶点作为根，然后添加与这个顶点关联的所有边，添加的顶点成为生成树在,1,层的顶点（任意排序）,按顺序访问,1,层上的每个顶点：只要不产生回路，就将与这个顶点相关联的每条边添加到树，产生,2,层的顶点,遵循相同的过程，直到已经添加了所有顶点,因为,BFS,的结果无回路，且是包含所有顶点的连通图，故是图的生成树,生成树的建立方法,宽度优先搜索,breadth-first search,7.4,生成树和最小生成树,Spanning Trees and minimum Spanning Trees,7.4,生成树和最小生成树,Spanning Trees and minimum Spanning Trees,例,3,用宽度优先搜索找出下图的生成树,生成