《数据结构》(C语言版)实验(6)

}

void PreOrder(BiTree p){ /* 先序遍历二叉树*/ if ( p!= NULL ) {

printf(\ PreOrder( p->lchild ) ; PreOrder( p->rchild) ; } }

void InOrder(BiTree p){ /* 中序遍历二叉树*/ if( p!= NULL ) {

InOrder( p->lchild ) ; printf(\ InOrder( p->rchild) ; } }

void PostOrder(BiTree p){ /* 后序遍历二叉树*/ if ( p!= NULL ) {

PostOrder( p->lchild ) ; PostOrder( p->rchild) ; printf(\ } }

void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/ BiTree stack[MAX],q; int top=0,i;

for(i=0;i

while(q!=NULL){

printf(\

if(q->rchild!=NULL) stack[top++]=q->rchild; if(q->lchild!=NULL) q=q->lchild; else

if(top>0) q=stack[--top]; else q=NULL; } }

void release(BiTree t){ /*释放二叉树空间*/ if(t!=NULL){

release(t->lchild); release(t->rchild); free(t);

26

} }

int main(){

BiTree t=NULL; createBiTree(&t);

printf(\ PreOrder(t);

printf(\ InOrder(t);

printf(\ PostOrder(t);

printf(\先序遍历序列（非递归）:\ Preorder_n(t); release(t); return 0; }

运行程序 输入：

ABC##DE#G##F###

?

运行结果：

2、在上题中补充求二叉树中求结点总数算法（提示：可在某种遍历过程中统计遍历的结点数），并在主函数中补充相应的调用验证正确性。 算法代码：

3、在上题中补充求二叉树中求叶子结点总数算法（提示：可在某种遍历过程中统计遍历的叶子结点数），并在主函数中补充相应的调用验证正确性。

27

算法代码：

4、在上题中补充求二叉树深度算法，并在主函数中补充相应的调用验证正确性。 算法代码：

选做实验：（代码可另附纸） 5、补充二叉树层次遍历算法。（提示：利用队列实现）

6、补充二叉树中序、后序非递归算法。

7、在二叉链表存储结构中加上前驱或后继的线索，则构成线索二叉树，在线索二叉树中进行遍历可以很方便地得到访问二叉树的线性序列。

8、赫夫曼树是一类带权路径长度最短的树，利用赫夫曼树进行编码可以得到最优的二进制前缀编码。

四、实验小结

五、教师评语

28

实验五 图

一、实验目的

1、掌握图的邻接矩阵和邻接表表示

2、掌握图的深度优先和广度优先搜索方法 3、理解图的应用方法

二、实验预习

说明以下概念

1、深度优先搜索遍历：

2、广度优先搜索遍历：

3、拓扑排序：

4、最小生成树：

5、最短路径：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果。 #include #define N 20 #define TRUE 1 #define FALSE 0 int visited[N];

typedef struct /*队列的定义*/ {

int data[N]; int front,rear; }queue;

typedef struct /*图的邻接矩阵*/ {

int vexnum,arcnum; char vexs[N]; int arcs[N][N]; }

graph;

void createGraph(graph *g); /*建立一个无向图的邻接矩阵*/ void dfs(int i,graph *g); /*从第i个顶点出发深度优先搜索*/

29

void tdfs(graph *g); /*深度优先搜索整个图*/

void bfs(int k,graph *g); /*从第k个顶点广度优先搜索*/ void tbfs(graph *g); /*广度优先搜索整个图*/ void init_visit(); /*初始化访问标识数组*/

void createGraph(graph *g) /*建立一个无向图的邻接矩阵*/ { int i,j; char v;

g->vexnum=0; g->arcnum=0; i=0;

printf(\输入顶点序列(以#结束)：\\n\ while((v=getchar())!='#') {

g->vexs[i]=v; /*读入顶点信息*/ i++; }

g->vexnum=i; /*顶点数目*/

for(i=0;ivexnum;i++) /*邻接矩阵初始化*/ for(j=0;jvexnum;j++) g->arcs[i][j]=0;

printf(\输入边的信息：\\n\

scanf(\读入边i,j*/

while(i!=-1) /*读入i,j为－1时结束*/ {

g->arcs[i][j]=1; g->arcs[j][i]=1;

scanf(\ } }

void dfs(int i,graph *g) /*从第i个顶点出发深度优先搜索*/ {

int j;

printf(\ visited[i]=TRUE;

for(j=0;jvexnum;j++)

if((g->arcs[i][j]==1)&&(!visited[j])) dfs(j,g); }

void tdfs(graph *g) /*深度优先搜索整个图*/ {

int i;

30