word算法分析与设计实验报告实验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）、 中根次序周游LDRProcedure INORDER(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD/If T0 then call INORDER(LCHILD(T) call VISIT(T) call INORDER(RCHILD(T)endifendINORDERb）、 先根次序周游DLRProcedure PREORDER(T)/T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD/If T0 then call VISIT(T)call PREORDER(LCHILD(T) call PREORDER(RCHILD(T)endifendPREORDERc）、 后根次序周游LRDProcedure 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、准备实验数据。准备模拟二元树和模拟图的数据。其中树的表现形式为第一行为根节点，其余假如干行表示每行第一个数为子节点，第二个数为父节点如：图的表示方式为第一行为节点数，边数和是否为有向图，剩下的行是图和节点所组成的邻接矩阵，文件表示如如下图：其中表示为无穷即不可达2、递归方法设计二元树周游和检索BinaryTree.java根据算法设计的多段图向前处理法的sparks语言，写出相应的java程序，并调试验证通过。周游和检索的次序可以是先序、中序和后序。其中的为java中的泛型类，类似c语言中的宏定义visit方法是访问该节点，将其参加到一个链表中，方便以后输出，同时可以减少计算时间时噪声影响。/* * 访问结点 * param node */publicvoid visit(BinaryTreeNode node) list.add(node.getData();/* * 递归实现二叉树的前序遍历 * param BT */publicvoid preOrderRecursive(BinaryTreeNode BT)if(BT!=null) visit(BT); preOrderRecursive(BT.getLChild(); preOrderRecursive(BT.getRChild();/* * 递归实现二叉树的中序遍历 * param BT */publicvoid inOrderRecursive(BinaryTreeNode BT)if(BT!=null) inOrderRecursive(BT.getLChild(); visit(BT); inOrderRecursive(BT.getRChild();/* * 递归实现二叉树的后序遍历 * param BT */publicvoid postOrderRecursive(BinaryTreeNode BT)if(BT!=null) postOrderRecursive(BT.getLChild(); visit(BT); postOrderRecursive(BT.getRChild();分别将其结果保存到文件中，分析其结果3、非递归方法设计二元树周游和检索BinaryTree.java根据最短路径问题的动态规划程序算法的sparks语言写出对应的java程序，并调试验证通过，比照递归和非递归程序，验证其正确性；/* * 非递归实现二叉树的中序遍历 * param BT */publicvoid 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();/