《树的遍历与生成树》PPT课件

《《树的遍历与生成树》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章树Tree不包含简单回路的连通图称为树，早在1857年英国数学家亚瑟·凯莱就用树去计数某些类型的化合物。随后树已经被用来解决各种学科分支里的问题。Chap7树7.1树的概念/IntroductionofTrees7.2树的应用/ApplicationsofTrees7.3树的遍历/TreeTraversal7.4生成树和最小生成树/SpanningTreesandminimumSpanningTrees有序根树常常用来保存信息，因此掌握访问有序根树的每个顶点以存取数据信息的算法非常必要系统地访问有序根树每个顶点的过程都称为遍历算法前序遍历Preordertraver

2、sal中序遍历Inordertraversal后序遍历Postordertraversal7.3树的遍历TreeTraversal[定义1]设T是带根r的有序根树。若T只包含r，则r是T的前序遍历。否则T1，T2，…，Tn是T里在r处从左到右的子树。前序遍历首先访问r。接着以前序来遍历T1，然后以前序来遍历T2，依此类推，直到以前序遍历了Tn为止。7.3树的遍历TreeTraversal例1前序遍历是以什么顺序访问图中有序根树里的顶点的？7.3树的遍历TreeTraversalabejknopfcdglmhi[定义2]设T是带根r的有序根树。若T只包含r，则r是T的中序遍

3、历。否则T1，T2，…，Tn是T里在r处从左到右的子树。中序遍历首先以中序来遍历T1，然后访问r，接着以中序遍历T2，以中序遍历T3，依此类推，直到以中序遍历了Tn为止。7.3树的遍历TreeTraversal例2中序遍历是以什么顺序访问图中有序根树里的顶点的？7.3树的遍历TreeTraversaljenkopbfaclgmdhi[定义3]设T是带根r的有序根树。若T只包含r，则r是T的后序遍历。否则T1，T2，…，Tn是T里在r处从左到右的子树。后序遍历首先以后序来遍历T1，以后序遍历T2，……，然后以后序遍历Tn，最后访问r。7.3树的遍历TreeTraversal

4、例3后序遍历是以什么顺序访问图中有序根树里的顶点的？7.3树的遍历TreeTraversaljnopkefbclmghida7.3树的遍历TreeTraversal7.3树的遍历TreeTraversal7.3树的遍历TreeTraversal以前序、中序、后序来列出有序根树的顶点的简易方法：首先从根开始围绕有序根树画一条曲线，沿着边移动；7.3树的遍历TreeTraversal前序：当曲线第一次经过一个顶点时，就列出这个顶点中序：当曲线第一次经过一个树叶时，就列出这个树叶，当曲线第二次经过一个内点时就列出这个内点后序：当曲线最后一次经过一个顶点而返回这个顶点的父母时，就

5、列出这个顶点练习：写出该有序根图按照前序、中序、后序遍历访问的顶点顺序7.3树的遍历TreeTraversal前序：abdefgc中序：dbfegac后序：dfgebca中缀、前缀、后缀记法(Infix,prefix,postfixnotation)7.3树的遍历TreeTraversal可用有序树来表示复杂的表达式包括算术表达式、复合命题、集合的组合等表示算术表达式时内点表示运算，树叶表示变量或数字，每个运算都作用在它的子树上例4表示表达式((x+y)2)+((x-4)/3)的有序根树是什么？中缀、前缀、后缀记法(Infix,prefix,postfixnotatio

6、n)7.3树的遍历TreeTraversal对表示一个表达式的有序根树的中序遍历，产生原来的表达式中缀、前缀、后缀记法(Infix,prefix,postfixnotation)7.3树的遍历TreeTraversal对表示一个表达式的二叉树的中序遍历，产生原来的表达式中序遍历得出的中缀表达式有二义性为避免二义性，中序遍历时需加括号，这种表达式称为中缀形式(x+y)/(x+3)(x+(y/x))+3x+(y/(x+3))中序遍历?x+y/x+3中缀、前缀、后缀记法(Infix,prefix,postfixnotation)7.3树的遍历TreeTraversal当以前序来

7、遍历表达式的二叉树时，就获得它的前缀形式，又称波兰记法前缀记法下的表达式无二义性前缀形式？++xy2/-x43已知前缀形式，如何获得对应的表达式呢？从右向左地求对应的表达式当遇到一个运算，就对在这个运算右边紧邻的两个运算对象执行相应的运算每个运算结果是新的运算对象例5前缀表达式+-*235/234的值是什么？7.3树的遍历TreeTraversal中缀、前缀、后缀记法(Infix,prefix,postfixnotation)7.3树的遍历TreeTraversal当以后序来遍历表达式的二叉树时，就获得它的后缀形式，又称逆