二、实验要求
1．认真阅读和掌握本实验的程序。 2．上机运行本程序。
3．保存和打印出程序的运行结果，并结合程序进行分析。
4．按照你二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
三、实验内容
程序1： 按先序次序输入二叉树中结点的值（一个字符），`0`表示空树，生成二叉树的二叉链表存储结构， bt为指向根结点的指针。然后按层次顺序遍历二叉树。
算法思想：本算法采用一个队列q，先将二叉树根结点入队列，然后退队列，
输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，遍将右子树根结点入队列，直到队列空为止。因为队列是先进先出，从而达到按层次顺序遍历二叉树的目的。 程序如下：
PROGRAM btreed(input,output);
CONST
M = 100;
TYPE
elemtp = char;
{二叉树的链式存储结构} TYPE
btree = ^node; node = RECORD
data:elemtp; lchild,rchild:btree;
END;
TYPE
vector=ARRAY[0..M] OF btree;
11
{生成二叉树}
VAR root:btree; que:vector;
front,rear:integer;
PROCEDURE create(VAR bt:btree); VAR x:elemtp; BEGIN read(x);
IF (ord(x)=48) THEN bt:=NIL ELSE BEGIN new(bt); bt^.data:=x;
{建根结点}
create(bt^.lchild); {建左子树} create(bt^.rchild); {建右子树}
END;
END;
PROCEDURE inorder(bt:btree); BEGIN IF bt<>NIL THEN BEGIN inorder(bt^.lchild); write(bt^.data,' ');
inorder(bt^.rchild);
END;
END;
12
PROCEDURE enqueue(bt:btree); BEGIN IF front<>((rear+1) MOD M) THEN BEGIN rear:=((rear+1) MOD M);
que[rear]:=bt;
END;
END;
PROCEDURE delqueue(VAR bt:btree); BEGIN IF front=rear THEN bt:=NIL ELSE BEGIN front:=((front+1) MOD M);
bt:=que[front];
END;
END;
PROCEDURE levorder(bt:btree); VAR p:btree; BEGIN
IF bt<>NIL THEN BEGIN enqueue(bt);
WHILE front<>rear DO BEGIN delqueue(p); write(p^.data,' ');
IF p^.lchild<>NIL THEN
13
enqueue(p^.lchild); IF p^.rchild<>NIL THEN enqueue(p^.rchild); END; END;
END;
{主程序} BEGIN
writeln('Please input the tree: '); create(root); inorder(root); writeln(''); front:=0; rear:=0; levorder(root);
END.
实验四 图的操作
一．实验目的
1．掌握图的基本存储方法。
2．掌握有关图的操作算法并用高级语言编程实现； 3．熟练掌握图的两种搜索路径的遍历方法。 二．实验要求
1．认真阅读和掌握本实验的程序。 2．上机运行本程序。
3．保存和打印出程序的运行结果，并结合程序进行分析。
4．按照你对图的操作需要，重新改写主程序并运行，打印出文件清单和运行结果
14
三．实验内容
以邻接矩阵和邻接表的方式存储连通图。然后分别用优先深度算法遍历邻接居真方式存储的图和邻接表方式存储的图。这里假设图只有4个顶点，在实验的时候可以根据需要更改vtxnum的值。 程序如下：
PROGRAM graphd(input,output);
CONST {edge边,vertex顶点,digraph向，weight权} vtxnum=4; {图中顶点数}
k1=0; {是否有向，0为无，非0为有} k2=0; {是否有权，0为无，非0为有}
maxvalue=10000; {定义无穷大}
TYPE elemtp=integer;
TYPE bool=ARRAY[0..vtxnum] OF boolean; {邻接矩阵存储无向无权图} TYPE vtxptr=1..vtxnum; bit=0..1; TYPE
vertex=RECORD data:elemtp; {顶点信息}
END;
TYPE
arc=RECORD
adj:bit; {表示两个顶点之间是否存在关系} END; TYPE graph=RECORD
vexs: ARRAY[vtxptr] OF vertex;
arcs: ARRAY[vtxptr,vtxptr] OF arc;
END;
{邻接表存储无向无权图} TYPE edgeptr=^edgenode;
15