第六节基本检索和周游方法.ppt

《第六节基本检索和周游方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第六章基本检索与周游方法问题描述许多涉及到二元树、树和图的问题涉及问题中数据结点的访问和处理有的问题需要访问结构中所有结点，有的访问结构的部分结点。本章介绍的方法将适用于树、二元树，有些方法可以用于图、树、二元树6.1一般方法1.检索与周游检索：以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为检索周游：当检索过程必须检索到数据对象的每一个结点时，则该检索过程称为周游访问结点：当算法对一个结点的信息段进行处理时，称该结点被访问。结点被访问可以是结点被打印、或作某种处理2.二元树周游（遍历）1）周游次序在

2、二元树的周游中，以D、L、R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：★LDR：中根次序周游（中根遍历）★LRD：后根次序周游（后根遍历）★DLR：先根次序周游（先根遍历）★RDL：逆中根次序周游★RLD：逆后根次序周游★DRL：逆先根次序周游2）二元树周游算法⑴中根次序周游算法6.1中根次序周游的递归表示procedureINORDER(T)//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallINORDER(LCHILD(T))cal

3、lVISIT(T)callINORDER(RCHILD(T))endifendINORDER⑵先根次序周游算法6.2先根次序周游的递归表示procedurePREORDER(T)//T是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallVISIT(T)callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))endifendPREORDER⑵后根次序周游算法6.3后根次序周游的递归表示procedurePOSTORDER(T)//T

4、是一棵二元树。T的每个结点有三个信息段:LCHILD,DATA,RCHILD//ifT≠0thencallPOSTORDER(LCHILD(T))callPOSTORDER(RCHILD(T))callVISIT(T)endifendPREORDER中根次序周游：FDHGIBEAC先根次序周游:ABDFGHIEC后根次序周游:FHIGDEBCAABDEGCHFI注：一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列唯一确定。但不能由先根遍历序列＋后根遍历序列唯一确定。如已知一棵二元树的中根遍历次序是

5、：DGBEAFHC先根遍历次序是：ABDGECFH则这棵二元树唯一确定如下:ABDEGCFH定理6.1当输入的树T有n≥0个结点时，设t(n)和s(n)分别表示这些周游算法中的任意一个算法所需要的最大时间和空间。如果访问一个结点所需要的时间和空间是Θ(1)，则t(n)=Θ(n),s(n)=Θ(n)。证明：时间:由于已知访问一个结点所需时间是Θ(1),故可用常数c1限界。设T的左子树中的结点数是n1，则t(n)有：t(n)=maxn1{t(n1)+t(n-n1-1)+c1}n≥1其中，t(0)≤c1。归纳法证明t(n)≤

6、c2n+c1，其中c2是一使得c2≥2c1的常数。1)当n=0时，成立2)假定当n=0,1,…,m-1时均成立。则当n=m时有，设T是一棵有m个结点的树，T左子树结点数为n1,则t(n)＝maxn1{t(n1)+t(n-n1-1)+c1}≤maxn1{c2n1+c1+c2(n-n1-1)+c1+c1}＝maxn1{c2n+3c1-c2}≤c2n+c1同理，存在c'2和c'1有t(n)≥c'2n+c'1。所以t(n)=Θ(n)空间：若T的深度为d，则所需空间为Θ(d),d≤n，所以s(n)=Θ(n)。3.树的周游1)树的

7、子树顺序无序→有序2)森林F的周游⑴树的先根次序周游A.若F为空，则返回B.访问F的第一棵树的根C.按树先根次序周游F的第一棵树的子树D.按树先根次序周游F的其它树⑵树的中根次序周游⑶树的后根次序周游树转换成二元树方法：设有一棵树T(它的根是T1)，人为安排它的子树有序且设为T11,T12,…,T1K。用T1做二元树的根，T11做T1的左子树，然后T1i做T1i-1的右子树，2≤i≤k。T1T11T12T1K…T1T11T12T1K…设T是由森林F转换成的二元树,则：T的先根次序周游相当于按树先根次序周游访问FT的中根

8、次序周游相当于按树中根次序周游访问F对T的后根次序周游无类似的自然对应4.图的检索和周游4.1宽度优先检索和周游1)宽度优先检索①从结点v开始，给v标上已到达（或访问）标记——此时称结点v还没有被检测，而当算法访问了邻接于某结点v的所有结点时，称该结点被检测了。②访问邻接于v且尚未被访问的所有结点——这些结点是新的未被检测的结点。