树的遍历与生成树.ppt

该【树的遍历与生成树 】是由【sanyuedoc】上传分享，文档一共【49】页，该文档可以免费在线阅读，需要了解更多关于【树的遍历与生成树 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第7章 树Tree
不包含简单回路的连通图称为树， 早在1857年英国数学家亚瑟·凯莱就用树去计数某些类型的化合物。随后树已经被用来解决各种学科分支里的问题。
DEFENCE
logo
01
04
02
03
树的概念/Introduction of Trees
树的应用/Applications of Trees
树的遍历/Tree Traversal
生成树和最小生成树/
Spanning Trees and minimum Spanning Trees
Chap 7 树
系统地访问有序根树每个顶点的过程都称为遍历算法
前序遍历 Preorder traversal
中序遍历 Inorder traversal
后序遍历 Postorder traversal
有序根树常常用来保存信息，因此掌握访问有序根树的每个顶点以存取数据信息的算法非常必要
树的遍历
Tree Traversal
树的遍历
Tree Traversal
[定义1] 设T是带根r的有序根树。若T只包含r，则r是T的前序遍历。否则T1，T2，…，Tn是T里在r处从左到右的子树。前序遍历首先访问r。接着以前序来遍历T1 ，然后以前序来遍历T2 ，依此类推，直到以前序遍历了Tn为止。
树的遍历
Tree Traversal
例1 前序遍历是以什么顺序访问图中有序根树里的顶点的？
a b e j k n o p f c d g l m h i
树的遍历
Tree Traversal
[定义2] 设T是带根r的有序根树。若T只包含r，则r是T的中序遍历。否则T1，T2，…，Tn是T里在r处从左到右的子树。中序遍历首先以中序来遍历T1 ，然后访问r，接着以中序遍历T2 ，以中序遍历T3 ，依此类推，直到以中序遍历了Tn为止。
树的遍历
Tree Traversal
例2 中序遍历是以什么顺序访问图中有序根树里的顶点的？
j e n k o p b f a c l g m d h i
树的遍历
Tree Traversal
[定义3] 设T是带根r的有序根树。若T只包含r，则r是T的后序遍历。否则T1，T2，…，Tn是T里在r处从左到右的子树。后序遍历首先以后序来遍历T1 ，以后序遍历T2 ，……，然后以后序遍历Tn，最后访问r 。
树的遍历
Tree Traversal
例3 后序遍历是以什么顺序访问图中有序根树里的顶点的？
j n o p k e f b c l m g h i d a
树的遍历
Tree Traversal