第五讲-检索与周游.ppt

1、算法设计与分析,第五讲 检索与周游,主要内容 检索与周游概念 二元树、树、图的检索与周游方法 重点 二元树的常用周游算法 图的常用检索算法 图的常用周游算法,5.1 术语,检索 周游,5.2 二元树周游,一、周游顺序,中根序周游 left child treerootright child tree,先根序周游 rootleft child treeright child tree,后根序周游 left child treeright child treeroot,二、周游算法,二元树表示,typedef struct NODE ElemType data; struct NODE *lch,

2、 *rch; *BINTREE;,递归算法,/ 中根序 inorder1(BINTREE T) if(T!=NULL) inorder(T-lch); visit(T-data); inorder(T-rch); ,/ 先根序 preorder1(BINTREE T) if(T!=NULL) visit(T-data); preorder(T-lch); preorder(T-rch); ,/ 后根序 postorder1(BINTREE T) if(T!=NULL) postorder(T-lch); postorder(T-rch); visit(T-data); ,定理5.1 当输入的树

3、T有n0个结点时, 设t(n)和s(n)分别表示上述任意算法所需要的最大时间和空间. 如果访问一个节点所需要的时间和空间是O(1), 则: t(n)=s(n)=O(n).,计算复杂度,非递归算法,preorder2(BINTREE T) / 先根序周游 BINTREE stackn, p=T; int s=0; if(p=NULL) return; while(1) visit(p-data); while(p-lch!=NULL) stack+s=p; p=p-lch; visit(p-data); while(1) if(p=p-rch)!=NULL) break; if(s=0) ret

4、urn; p=stacks-; ,/ 时间和空间复杂度均为O(n),typedef struct NODE ElemType data; struct NODE *lch, *rch, *parent; *BINTREE;,/ 空间复杂度为O(1),preorder3(BINTREE T) / 先根序周游 BINTREE p=T; if(p=NULL) return; while(1) visit(p-data); while(p-lch!=NULL) p=p-lch; visit(p-data); while(1) if(p-rch!=NULL) p=p-rch ; break; while

5、(p-parent!=NULL) ,5.3 树周游,将树看成是只有一棵树的森林，将森林看成是由一棵树去掉根而得到，利用森林的周游来递归定义树周游可得到树先根序、中根序、后根序周游算法。,树和森林的递归定义可参见数据结构教材的相关内容。,5.4 图的检索与周游,已知: G=(V, E)，|V|=n, |E|=e. 检索: 确定与已知节点vV 有通路的所有节点. 周游: 访问G的所有节点.,两个术语: 已访问, 已检测.,一、问题描述,检索顺序,数据结构,二、宽度优先检索与周游,从节点v出发，依次访问节点v的所有邻接节点后，再从已访问的未检测节点中取一个节点作为待检测节点.,外部数组visited

6、n，初值为0 队列q,检索算法,时间复杂度: 对邻接表为O(e), 对邻接矩阵为O(n2). 空间复杂度: O(n).,void BFS(int v) QUEUE q; visitedv-1=1; u=v; while(1) for(u的所有邻接节点w) if(visitedw-1=0) SetTail(w,q); visitedw-1=1; if(q为空) return; u=GetHead(q); ,周游算法,BFS: 得到连通图的宽度优先生成树, 最优化. BFT: 判断图的连通性, 获得图的各连通分量.,void BFT(int n) int i; for(i=0; in; i+) i

7、f(visitedi=0) BFS(i+1); ,应用,检索顺序,数据结构,三、深度优先检索与周游,外部数组visitedn，初值为0,周游算法,应用说明,void DFT(int n) int i; for(i=0; in; i+) if(visitedi=0) DFS(i+1); ,检索算法,void DFS(int v) visitedv-1=1; for(v的所有邻接节点w) if(visitedw-1=0) DFS(w); ,DFS: 得到连通图的深度优先生成树, 最优化 DFT: 判断图的连通性, 获得图的各连通分量 DFS, DFT分别与BFS, BFT等效,课外练习：,设计空间复杂度为O(n)和