1009040130-贺程-实验5

《算法分析与设计》实验报告

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

姓名 贺程 学号 1009040130 班级 电子商务1002班

时间 2013/3/22 地点 文波机房 同 组 人 无 指导教师 朱少林

实验目的与要求

a) 掌握基本检索与周游方法算法设计的一般思想。

b) 掌握二元树、图的周游和检索算法。

c) 理解树、与或树、对策树周游与检索的思想和方法。

实验内容

d) 二元树周游 e) 图的周游

相关内容

一、 二元树周游

a）、

中根次序周游（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

b）、 先根次序周游（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

c）、 后根次序周游（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

d）、 中根次序周游的非递归算法

Procedure INORDER1(T) //T是一棵二元树，每个结点有三个信息段：LCHILD、DATA、RCHILD// 1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

//使用大小为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 i>m 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。//

1 VISITED(V) ←1; u←v

2 将Q初始化库空 //Q是未检测结点的队列//

3 Loop

4 For 邻接于u的所有结点w do

5 If VISITED(w)=0 then call ADDQ(w, Q)

//w未检测//

6 VISITED(w) ←1 7 Endif 8 Repeat

9 If Q为空 then return endif

//不再有还未检测的结点//

10 Call DELETEQ(u, Q) //从队中取一个未检测的结点// 11 Repeat 12 endBFS b) 图的宽度优先周游

Procedure BFT(G, n)

Declare VISITED(n)

For i←1 to n do //将所有结点标注为未访问// VISITED←0 Repeat

For i←1 to n do /反复调用BFS//

If VISITED(i)=0 then call BFS(i) endif Repeat endBFT

c) 图的深度优先检索算法

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 Repeat endDFS

d) 图的深度优先周游算法

Procedure DFT(G, n) Declare VISITED(n)

For i←1 to n do //将所有结点标注为未访问// VISITED←0 Repeat For i←1 to n do /反复调用DFS//

If VISITED(i)=0 then call DFS(i) endif Repeat endDFT

实验步骤

f) 准备模拟二元树和模拟图的数据。

g) 用递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以是先序、中序和后序。

h) 用非递归方法设计二元树周游和检索程序，调试通过。周游和检索的次序可以i) j)

是先序、中序和后序。

用递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。

用非递归方法设计图的周游程序，调试通过。周游的次序可以是深度优先，也可以是宽度优先。

附加实验与思考

设计一个图的D-Search检索和周游算法，上机调试通过，检验其结果。

实验步骤

1． 树的遍历和周游算法

为便于比较遍历结果，采用对一个二叉排序树进行遍历，首先需要构造二叉排序树，如果出现相同节点，则去掉该节点，否则将该节点插入到二叉排序树中。在该实验中对文件treeTest.txt中的数据进行操作。

treeTest.txt：

10

15 22 4 0 13 6 8 10 17 9

以文件treeTest.txt中给出的数据来构造一棵树。

程序代码： #include #include

typedef struct Node{ int data;

Node *leftchild; Node *rightchild;

}Node;

//初始化一棵二叉树排序树。

void InitBinaryTree(Node**root,int elem){

*root=(Node*)malloc(sizeof(Node)); if(!(*root)){ }

printf(\return;

(*root)->data=elem;

(*root)->leftchild=NULL;

(*root)->rightchild=NULL; }

//向二叉树排序树中插入结点。 void InsertNode(Node *root,int elem){

newnode=(Node*)malloc(sizeof(Node));

if(!newnode){ printf(\ return; Node *newnode=NULL;

Node *p=root,*last_p=NULL;