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

《算法分析与设计》实验报告 实验5基本检索与周游方法算法设计姓名 xxx 学号 xxxxx 班级 xxxxxxx 时间：xxxxxx 地点：xxxx 同 组 人：无 指导教师：xxxxx 实验目的 掌握基本检索与周游方法算法设计的一般思想。 掌握二元树、图的周游和检索算法。 理解树、与或树、对策树周游与检索的思想和方法。 实验内容 二元树周游 图的周游 准备模拟二元树和模拟图的数据。 用递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。 用非递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。 用递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。 用非递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。 实验环境 硬件： Intel(R) Pentium(R) CPU RAM:4G 软件：Myeclipse2013 编程语言：Java 实验前准备 算法设计： 二元树周游 中根次序周游（LDR） Procedure INORDER(T) //T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD// If T≠0 then call INORDER(LCHILD(T)) call VISIT(T) call INORDER(RCHILD(T)) endif endINORDER 先根次序周游（DLR） Procedure PREORDER(T) //T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD// If T≠0 then call VISIT(T) call PREORDER(LCHILD(T)) call PREORDER(RCHILD(T)) endif endPREORDER 后根次序周游（LRD） Procedure POSTORDER(T) //T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD// If T≠0 then call POSTORDER(LCHILD(T)) call POSTORDER(RCHILD(T)) call VISIT(T) endif endINORDER 中根次序周游的非递归算法 Procedure INORDER1(T) //T是一棵二元树，每个结点有三个信息段：LCHILD、DATA、RCHILD// //使用大小为m的栈的一个非递归算法// integer i, m, STACK(M) if T=0 then return endif //T为空// P←T; i←0 //周游T；i为栈顶// Loop While LCHILD(P)≠0 do //周游左子树// i←i+1 If im then print(‘stack overflow’) Stop Endif STACK(i) ←P; P←LCHILD(P) Repeat Loop Call VISIT(P) //P的左子树周游完// P←RCHILD(P) If P≠0 then exit endif //周游右子树// If i=0 then return endif P←STACK(i); i←i-1 Repeat //访问父结点// repeat endINORDER1 图的检索与周游 a) 图的宽度优先检索算法 Line procedure BFS(v) //宽度优先检索G，它在结点v开始执行。所有已访问结点都标上VISITED(i)=1。图G和数组VISITED是全程量。VISITED开始时都已置成0。// VISITED(V) ←1; u←v 将Q初始化库空 //Q是未检测结点的队列// Loop For 邻接于u的所有结点w do If VISITED(w)=0 then call ADDQ(w, Q) //w未检测// VISITED(w