实验5基本检索与周游方法算法设计

算法分析与设计实验报告实验5基本检索与周游方法算法设计姓名 xxx 学号 xxxxx 班级 xxxxxxx时间：xxxxxx 地点：xxxx同 组 人：无指导教师：xxxxx实验目的 1. 掌握基本检索与周游方法算法设计的一般思想。2. 掌握二元树、图的周游和检索算法。3. 理解树、与或树、对策树周游与检索的思想和方法。实验内容 1. 二元树周游2. 图的周游3. 准备模拟二元树和模拟图的数据。4. 用递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。5. 用非递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。6. 用递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。7. 用非递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。实验环境 硬件： Intel(R) Pentium(R) CPU RAM:4G软件：Myeclipse2013编程语言：Java实验前准备1、 算法设计：二元树周游a）、 中根次序周游（LDR）Procedure INORDER(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD/If T0 then call INORDER(LCHILD(T) call VISIT(T) call INORDER(RCHILD(T)endifendINORDERb）、 先根次序周游（DLR）Procedure PREORDER(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD/If T0 then call VISIT(T)call PREORDER(LCHILD(T) call PREORDER(RCHILD(T)endifendPREORDERc）、 后根次序周游（LRD）Procedure POSTORDER(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD/If T0 then call POSTORDER(LCHILD(T) call POSTORDER(RCHILD(T) call VISIT(T)endifendINORDERd）、 中根次序周游的非递归算法Procedure INORDER1(T)/T是一棵二元树，每个结点有三个信息段：LCHILD、DATA、RCHILD/使用大小为m的栈的一个非递归算法/1 integer i, m, STACK(M)2 if T=0 then return endif /T为空/3 PT; i0 /周游T；i为栈顶/4 Loop5 While LCHILD(P)0 do /周游左子树/6 ii+17 If im then print(stack overflow)8 Stop9 Endif10 STACK(i) P; PLCHILD(P)11 Repeat12 Loop13 Call VISIT(P) /P的左子树周游完/14 PRCHILD(P)15 If P0 then exit endif /周游右子树/16 If i=0 then return endif17 PSTACK(i); ii-118 Repeat /访问父结点/19 repeatendINORDER1二、 图的检索与周游 a) 图的宽度优先检索算法Line procedure BFS(v)/宽度优先检索G，它在结点v开始执行。所有已访问结点都标上VISITED(i)=1。图G和数组VISITED是全程量。VISITED开始时都已置成0。/1 VISITED(V) 1; uv2 将Q初始化库空 /Q是未检测结点的队列/3 Loop4 For 邻接于u的所有结点w do 5 If VISITED(w)=0 then call ADDQ(w, Q) /w未检测/6 VISITED(w) 17 Endif8 Repeat9 If Q为空 then return endif /不再有还未检测的结点/10 Call DELETEQ(u, Q) /从队中取一个未检测的结点/11 Repeat12 endBFSb) 图的宽度优先周游Procedure BFT(G, n)Declare VISITED(n)For i1 to n do /将所有结点标注为未访问/ VISITED0RepeatFor i1 to n do /反复调用BFS/ If VISITED(i)=0 then call BFS(i) endifRepeatendBFTc) 图的深度优先检索算法procedure DFS(v)/已知一个n结点无向（或有向）图G=（V，E）以及初值已置为零的数组VISITED(1: n)。这个算法访问由v可以到达的所有结点。G和VISITED是全程量。/ VISITED(V) 1; For 邻接于v的每个结点w do If VISITED(w)=0 then call DFS(w) Endif RepeatendDFSd) 图的深度优先周游算法Procedure DFT(G, n)Declare VISITED(n)For i1 to n do /将所有结点标注为未访问/ VISITED0RepeatFor i1 to n do /反复调用DFS/ If VISITED(i)=0 then call DFS(i) endifRepeatendDFT1、 程序设计：见附1实验步骤1、准备实验数据。准备模拟二元树和模拟图的数据。将二元树和模拟图的数据保存在文件中，在程序运行时读取，分别取名为btree.txt和|Cost.txt其中树的表现形式为第一行为根节点，其余若干行表示每行第一个数为子节点，第二个数为父节点如：图的表示方式为第一行为节点数，边数和是否为有向图，剩下的行是图和节点所组成的邻接矩阵，文件表示如下图：其中表示为无穷即不可达2、递归方法设计二元树周游和检索BinaryTree.java根据算法设计的多段图向前处理法的sparks语言，写出相应的java程序，并调试验证通过。周游和检索的次序可以是先序、中序和后序。（其中的为java中的泛型类，类似c语言中的宏定义）visit（）方法是访问该节点，将其加入到一个链表中，方便以后输出，同时可以减少计算时间时噪声影响。/* * 访问结点 * param node */ public void visit(BinaryTreeNode node) list.add(node.getData(); /* * 递归实现二叉树的前序遍历 * param BT */ public void preOrderRecursive(BinaryTreeNode BT) if(BT!=null) visit(BT); preOrderRecursive(BT.getLChild(); preOrderRecursive(BT.getRChild(); /* * 递归实现二叉树的中序遍历 * param BT */ public void inOrderRecursive(BinaryTreeNode BT) if(BT!=null) inOrderRecursive(BT.getLChild(); visit(BT); inOrderRecursive(BT.getRChild(); /* * 递归实现二叉树的后序遍历 * param BT */ public void postOrderRecursive(BinaryTreeNode BT) if(BT!=null) postOrderRecursive(BT.getLChild(); visit(BT); postOrderRecursive(BT.getRChild(); 分别将其结果保存到文件中，分析其结果3、非递归方法设计二元树周游和检索BinaryTree.java根据最短路径问题的动态规划程序算法的sparks语言写出对应的java程序，并调试验证通过，对比递归和非递归程序，验证其正确性；/* * 非递归实现二叉树的中序遍历 * param BT */ public void inNotOrderRecursive(BinaryTreeNode BT) /*MyArrayStackBinaryTreeNode stack; int maxStackSize=50; stack=new MyArrayStackBinaryTreeNode(maxStackSize);*/ MyLinkedStackBinaryTreeNode stack=new MyLinkedStackBinaryTreeNode(); BinaryTreeNode p=BT; while(p!=null|!stack.isEmpty() while(p!=null)/找到左子树 stack.push(p); p=p.getLChild(); if(!stack.isEmpty() p=stack.pop();/先从栈中弹出要结点 visit(p);/再访问根结点 p=p.getRChild();/然后再指向右子树 输出结果保存到文件中，可以看出与递归结果一致；4、图的宽度优先检索和周游GraphSearch.java用邻接矩阵的方式表示整个图并将每个节点是否访问用一个数组表示，同时访问时将该结点加入到一个链表中去，方便以后输出使用并减少噪声影响；/* * 图的宽度优先检索 * G，它在结点v开始执行，所有已访问结点都标上visitedi=1,图G和数组visited是全程变量,visited开始记为0 * param v */ public void BFS(int v) visit(v); visitedv=1; int u=v; LinkedList Q=new LinkedList();/当作放置未检测结点的队列 while(true) LinkedList list=G.costListu; for(Edge e:list)/邻接于u的所有结点 int w=e.v; if(visitedw=0) Q.add(w);/将未检测的结点为w放入队列 visit(w);/访问该结点 visitedw=1;/将该结点标记为1 if(!Q.isEmpty()/若队列不为空 u=Q.remove();/将未访问的结点从队列取出赋给u，并准备下一轮循环 else/队列为空表示所有结点访问结束 return; /* * 宽度优先周游算法 */ public void BFT() for(int i=1;i=G.n;i+)/将所有结点标注为未访问/ visitedi=0; for(int i=1;iG.n;i+)/反复调动BFS if(visitedi=0) BFS(i); 宽度优先检索结果（最后一行为检索的结果顺序）宽度优先周游的结果：5、图的深度度优先检索和周游GraphSearch.java用邻接矩阵的方式表示整个图并将每个节点是否访问用一个数组表示，同时访问时将该结点加入到一个链表中去，方便以后输出使用并减少噪声影响；/* * 图的深度优先检索 * 已知一个n结点的无向（或有向图）G，以及初会已置为零的数组visited，这个算法可到达访问由v所可以到过的所有结点，G和visite是全程变量 * param v */ public void DFS(int v) visit(v);/访问该结点 visitedv=1;/将该结点标记为1 LinkedList list=G.costListv; for(Edge e:list)/邻接于u的所有结点 int w=e.v; if(visitedw=0) DFS(w); /* * 图的深度优先周游 */ public void DFT() for(int i=1;i=G.n;i+)/将所有结点标注为未访问/ visitedi=0; for(int i=1;iG.n;i+)/反复调动DFS if(visitedi=0) DFS(i); 深度优先检索结果（最后一行为检索的结果顺序）深度优先周游的结果：5、【附】查找族谱中的近亲FamilyTree.java采用二元树相同的方法将村的结果存储在文件中，并以二叉树的方式表示树的结构，但解释与二叉树不中，其中左孩子表示子辈，右孩子表示同辈；查找是否是近亲时首先查找该节点，将该人的父辈祖先保存在栈中，采用一般树的后序遍历方法（即二叉树的中序周游方法）可以达到此效果，然后再比较它们在规定的代数如5代内是否有相同的祖先，如果有则表示他们为近亲；public boolean isNearRelation(myType x,myType y,int n) MyLinkedStackBinaryTreeNode stack0=xStack(x); MyLinkedStackBinaryTreeNode stack1=xStack(y); if(stack0=null)/若有一个结点未找到 System.out.println(未找到结点+x.data); return false; else if(stack1=null) System.out.println(未找到结点+y.data); return false; int i=0; LinkedList arryx=new LinkedList(); LinkedList arryy=new LinkedList(); /将两个结点的父辈们组成的栈加入链表中，只取前n个 while(!stack0.isEmpty()&in) BinaryTreeNode s=stack0.pop(); myType m=s.getData(); arryx.add(m); i+; i=0; while(!stack1.isEmpty()&in) BinaryTreeNode s=stack1.pop(); myType m=s.getData(); arryy.add(m); i+; /比较链表是否有相同元素 for(int j=0;jarryx.size();j+) for(int k=0;karryy.size();k+) if(arryx.get(j).equals(arryy.get(k) return true; return false; /* * 采用后序遍历的方法对就二叉树的中序遍历方法，查找x元素，并将该结点的父辈们加入到一个栈中 * param x * return */ SuppressWarnings(unused) public MyLinkedStackBinaryTreeNode xStack(myType x) BinaryTreeNode p=familyTree.getRoot(); MyLinkedStackBinaryTreeNode stack=new MyLinkedStackBinaryTreeNode(); while(p!=null|!stack.isEmpty() while(p!=null)/先找到子树的最左边结点 stack.push(p); p=p.getLChild(); if(!stack.isEmpty() if(!stack.isEmpty() p=stack.pop();/先从栈中弹出要结点 if(p.getData().equals(x)/找到的话直接结束查找，最终返回的是其父辈的终成的栈 return stack; p=p.getRChild();/然后再指向右子树 /未找到返回空 return null; 族谱结构为（从1开始顺序编号）表示的图形为用二叉树表示如下：比如查找F2和E8是否是5代以内的近亲，由图中可以清楚看到是，结果与之一致查找它们是否为4代以内的近亲时，可以看出它是不是的实验结果及其分析1、递归方法设计二元树周游和检索如果访问一个结点所需要的时间和空间为O(1)，n个结点每个结点均门访问一次，这么算法的时间和空间复杂度均为O(n)；2、图的宽度优先检索和周游图的宽度优先检索，t(n,e)=O(n+e)图的宽度优先检索BFSn102030405060708090100100000次运行耗时12325244765796713351774227628523452图的宽度度优先周游，t(n)=O(n2)图的宽度优先周游BFTn102030405060708090100100000次运行耗时126249440665976134917702290281134773、图的深度优先检索和周游图的深度度优先检索，t(n,e)=O(n+e)图的深度优先检索DFSn102030405060708090100100000次运行耗时13918035463496813351749230429813742图的深度度优先周游，t(n)=O(n2)图的深度优先周游DFTn102030405060708090100100000次运行耗时174198363654967134217822328299335964、总结基本的检索和周游算法主要包括对树和图各结点的遍历访问。二元树的访问根据每个子树的访问次序可分为前序周游，中序周游和后序周游，三种方法周游所需要的时间和空间复杂度相同，但过程中在栈中所存储和结点不同，在实际情况中可根据需要采取不同的周游方法（比如在查找近亲一题中采用了后序周游（对应的是二元树的中序周游）所具有的特性，即访问某结点时，其祖先结点在栈中）；图的检索又分为宽度和深度检索和周游，所需要的时间和空间复杂度也相同的。 附：源代码1、二元树周游和检索BinaryTree.javaimport java.io.File;import java.util.LinkedList;public class BinaryTree BinaryTreeNode root; LinkedList list; public BinaryTree() list=new LinkedList(); public BinaryTree(BinaryTreeNode root) this.root=root; list=new LinkedList(); public BinaryTreeNode getRoot() return root; public void setRoot(BinaryTreeNode root) this.root = root; /* * 采用非递归前序遍历查找结点x，并返回该结点 * param BT * param x * return 找到返回该节点，否则返回空 */ public BinaryTreeNode allBinaryTreeSearch(BinaryTreeNode BT,T x) BinaryTreeNode p=BT; MyLinkedStackBinaryTreeNode stack=new MyLinkedStackBinaryTreeNode(); while(p!=null|!stack.isEmpty() if(p!=null) boolean f=false; if(x instanceof Integer) f=(p.getData()=x); else f=p.getData().equals(x); if(f) return p; else stack.push(p); p=p.getLChild(); else if(!stack.isEmpty() p=stack.pop(); p=p.getRChild(); return null; /* * 访问结点 * param node */ public void visit(BinaryTreeNode node) list.add(node.getData(); /* * 递归实现二叉树的前序遍历 * param BT */ public void preOrderRecursive(BinaryTreeNode BT) if(BT!=null) visit(BT); preOrderRecursive(BT.getLChild(); preOrderRecursive(BT.getRChild(); /* * 递归实现二叉树的中序遍历 * param BT */ public void inOrderRecursive(BinaryTreeNode BT) if(BT!=null) inOrderRecursive(BT.getLChild(); visit(BT); inOrderRecursive(BT.getRChild(); /* * 递归实现二叉树的后序遍历 * param BT */ public void postOrderRecursive(BinaryTreeNode BT) if(BT!=null) postOrderRecursive(BT.getLChild(); postOrderRecursive(BT.getRChild(); visit(BT); /* * 非递归实现二叉树的中序遍历 * param BT */ public void inNotOrderRecursive(BinaryTreeNode BT) /*MyArrayStackBinaryTreeNode stack; int maxStackSize=50; stack=new MyArrayStackBinaryTreeNode(maxStackSize);*/ MyLinkedStackBinaryTreeNode stack=new MyLinkedStackBinaryTreeNode(); BinaryTreeNode p=BT; while(p!=null|!stack.isEmpty() while(p!=null)/找到左子树 stack.push(p); p=p.getLChild(); if(!stack.isEmpty() p=stack.pop();/先从栈中弹出要结点 visit(p);/再访问根结点 p=p.getRChild();/然后再指向右子树 public static BinaryTreeNode init0() BinaryTreeNode f=new BinaryTreeNode(f); BinaryTreeNode g=new BinaryTreeNode(g); BinaryTreeNode e=new BinaryTreeNode(e,g,null); BinaryTreeNode d=new BinaryTreeNode(d); BinaryTreeNode c=new BinaryTreeNode(c,null,f); BinaryTreeNode b=new BinaryTreeNode(b,d,e); BinaryTreeNode a=new BinaryTreeNode(a,b,c); return a; public static void exp0() BinaryTreeNode root=init0(); BinaryTree T=new BinaryTree(root); /T.preOrderRecursive(root); /T.inOrderRecursive(root); /T.postOrderRecursive(root); T.inNotOrderRecursive(root); System.out.println(T.list); public static void exp1() String destDir=E:我的文档大三下算法分析与设计实验实验5 基本检索与周游方法算法设计data; String fileName=btree.txt; File sur=new File(destDir,fileName); BinaryTree tree=TreeFile.readTreeFile(sur); /tree.preOrderRecursive(tree.getRoot(); /tree.inOrderRecursive(tree.getRoot(); /tree.postOrderRecursive(tree.getRoot(); tree.inNotOrderRecursive(tree.getRoot(); for(myType mt:tree.list) System.out.print(mt.getData()+=); public static void main(String args) exp1(); 2、图的检索和周游GraphSearch.javaimport java.io.File;import java.util.Arrays;import java.util.LinkedList;public class GraphSearch private Graph G; private int visited; private LinkedList list; public GraphSearch() public GraphSearch(Graph G) this.G = G; int n = G.n; visited = new intn + 1; list = new LinkedList(); public void clear() Arrays.fill(visited, 0); list.clear(); /* * 访问结点w，将w放到一个链表中去 * * param w */ public void visit(int w) list.add(w); /* * * 图的宽度优先检索 * * G，它在结点v开始执行，所有已访问结点都标上visitedi=1,图G和数组visited是全程变量,visited开始记为0 * * param v */ public void BFS(int v) visit(v); visitedv = 1; int u = v; LinkedList Q = new LinkedList();/ 当作放置未检测结点的队列 while (true) LinkedList list = G.costListu; for (Edge e : list) / 邻接于u的所有结点 int w = e.v; if (visitedw = 0) Q.add(w);/ 将未检测的结点为w放入队列 visit(w);/ 访问该结点 visitedw = 1;/ 将该结点标记为1 if (!Q.isEmpty() / 若队列不为空 u = Q.remove();/ 将未访问的结点从队列取出赋给u，并准备下一轮循环 else / 队列为空表示所有结点访问结束 return; /* * 宽度优先周游算法 */ public void BFT() for (int i = 1; i = G.n; i+) / 将所有结点标注为未访问/ visitedi = 0; for (int i = 1; i G.n; i+) / 反复调动BFS if (visitedi = 0) BFS(i); /* * * 图的深度优先检索 * * 已知一个n结点的无向（或有向图）G，以及初会已置为零的数组visited，这个算法可到达访问由v所可以到过的所有结点，G和visite是全程变量 * * param v */ public void DFS(int v) visit(v);/ 访问该结点 visitedv = 1;/ 将该结点标记为1 LinkedList