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

《实验5基本检索与周游方法算法设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《算法分析与设计》实验报告实验5基本检索与周游方法算法设计姓名XXX学号XXXXX班级XXXXXXX时间：XXXXXX地点：XXXX同组人：无扌旨导教师:XXXXX实验目的1•掌握基本检索与周游方法算法设计的一般思想。2.掌握二元树、图的周游和检索算法。3•理解树、与或树、对策树周游与检索的思想和方法。实验内容1•二元树周游2•图的周游3.准备模拟二元树和模拟图的数据。4•用递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。5•用非递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。

2、6.用递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。7.用非递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。实验环境硬件：Intel(R)Pentium(R)CPURAM:4G软件:Myeclipse2013编程语言：Java实验前准备1、算法设计：二元树周游a)s'I1根次序周游(LDR)ProcedureINORDER(T)〃T是一棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD//IfTHOthencallINORDER(LCHILD(T))callVI

3、SIT(T)callINORDER(RCHILD(T))endifendINORDERb)、先根次序周游(DLR)ProcedurePREORDER(T)〃T是-•棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCHILD//IfTH()thencallVISIT(T)callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))endifendPREORDERc)、后根次序周游(LRD)ProcedurePOSTORDER(T)〃T是-•棵二元树。T的每个结点有三个信息段：LCHILD、DATA、RCH

4、ILD//IfTHOthencallPOSTORDER(LCHILD(T))callPOSTORDER(RCH1LD(T))callVISIT(T)endifendINORDERd)、屮根次序周游的非递归算法ProcedureINORDER1(T)//T是一棵二元树，每个结点有三个信息段：LCHILD>DATA、RCHILD//〃使用大小为m的栈的一个非递归算法〃1integeri,m,STACK(M)2ifT=0thenreturncncHf//T为空//3P-T;i-0//周游T；i为栈顶//4Loop5WhileLCHILD(P)H0do〃周

5、游左子树//6i-i+17Ifi>mthenprint("stackoverflow")8Stop9Endif10STACK(i)-P;P-LCHILD(P)11Repeat12Loop13CallVISIT(P)//P的左子树周游完//14P-RCHTLD(P)15IfPHOthenexitendif〃周游右子树//16Ifi=0thenreturnendif17P-STACK(i);i-i-118Repeat//访问父结点//19repeatendINORDERl图的检索与周游a)图的宽度优先检索算法Line12345procedureBFS(

6、v)//宽度优先检索G,它在结点v开始执行。所有已访问结点都标上VISITED①=1。图G和数组VISITED是全程量。VISITEDJF始时都已置成()。//VISITED(V)-1;u-v将Q初始化库空//Q是未检测结点的队列//LoopFor邻接于u的所有结点wdoIfVISITED(w)=0thencallADDQ(w,Q)//w未检测〃6789VISITED(w)-1EndifRepeatIfQ为空thenreturncncHf〃不再有还未检测的结点//101112CallDELETEQ(u,Q)〃从队屮取一个未检测的结点〃Repeate

7、ndBFSb)图的宽度优先周游ProcedureBFT(G,n)DeclareVISITED(n)Fori—1tondo//将所冇结点标注为未访问//VISITED-0RepeatFori—1tondo/反复调用BPS//IfVISITED(i)=0thencallBFS(i)endifRepeatendBFTc)图的深度优先检索算法procedureDFS(v)〃已知一个n结点无向(或有向)图G二(V,E)以及初值已置为零的数组VISITED(l:n)o这个算法访问山v可以到达的所有结点。G和VISITED是全程量。//VISITED(V)T;F

8、or邻接于v的每个结点wdoIfVISITED(w)=OthencallDFS(w)End讦RepeatcndDFSd)图