第五讲-检索与周游.pptVIP

* 算法设计与分析 第五讲 检索与周游 算法设计与分析 第五讲 检索与周游 主要内容 检索与周游概念 二元树、树、图的检索与周游方法 重点 二元树的常用周游算法 图的常用检索算法 图的常用周游算法 5.1 术语 检索 周游 5.2 二元树周游 一、周游顺序 中根序周游 left child tree→root→right child tree 先根序周游 root→left child tree→right child tree 后根序周游 left child tree→right child tree→root 二、周游算法 二元树表示 typedef struct NODE{ ElemType data; struct NODE *lch, *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 当输入的树T有n≥0个结点时, 设t(n)和s(n)分别表示上述任意算法所需要的最大时间和空间. 如果访问一个节点所需要的时间和空间是O(1), 则: t(n)=s(n)=O(n). 计算复杂度 非递归算法 preorder2(BINTREE T) // 先根序周游 { BINTREE stack[n], 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) return; p=stack[s--]; } } } // 时间和空间复杂度均为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((p-parent!=NULL)( p-parent- rch==p)) p=p-parent; if(p-parent ==NULL) return; else p= p-parent; } } } 5.3 树周游 将树看成是只有一棵树的森林，将森林看成是由一棵树去掉根而得到，利用森林的周游来递归定义树周游可得到树先根序、中根序、后根序周游算法。 树和森林的递归定义可参见数据结构教材的相关内容。 5.4 图的检索与周游 已知: G=(V, E)，|V|=n, |E|=e. 检索: 确定与已知节点v∈V 有通路的所有节点. 周游: 访问G的所有节点. 两个术语: 已访问, 已检测. 一、问题描述 检索顺序 数据结构 二、宽度优先检索与周游 从节点v出发，依次访问节点v的所有