实验二 用递归算法遍历二叉树
[实验目的]
学习掌握二叉树各种遍历方法的基本操作算法。
[实验内容]
建立一棵二叉树，并用递归算法分别用前序、中序和后序遍历之。
[实验要点及说明]
由于二叉树的定义是递归的，因而一棵非空二叉树可以看作是由根结点、左子树和右子树这三个基本部分组成的。如果能依次遍历这三个部分的信息，也就遍历了整个二叉树。由此得到的二叉树的遍历是按某种策略访问二叉树中的每一个结点且仅访问一次的过程。二叉树的遍历按访问根结点的先后次序不同分为前序、中序和后序三种。
前序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）访问根结点；
（2）前序遍历左子树；
（3）前序遍历右子树。
中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
[实验要求与步骤]
1． 基本要求：采用递归算法实现前序、中序和后序遍历；
2． 测试数据：
3． 实现提示：二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访
问一次且只被访问一次；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
#include
#define null 0
int counter=0;
typedef struct btreenode
{int data;
struct btreenode *lchild;
struct btreenode *rchild;
}bnode;
bnode *p;
bnode *creat(int x,bnode *lbt, bnode *rbt)
{bnode *p;
p=(bnode*)malloc(sizeof(bnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return(p);
}
bnode *ins_lchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->lchild!=null)
q->rchild=p->lchild;
p->lchild=q;
}
}
bnode *ins_rchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->rchild!=null)
q->lchild=p->rchild;
p->rchild=q;
}}
void prorder(bnode*p)
{if(p==null)
return;
printf("%d\t%u\t%d\t%u\t%u\n",++counter,p,p->data,p->lchild,p->rchild); if(p->lchild!=null)
proder(p->lchild);
if(p->rchild!=null)
proder(p->rchild);
}
void preorder(bnode *p)
{if(p==null)
return;
printf("%d",p->data);
if(p->lchild!=null)
preoder(p->lchild);
if(p->rchild!=null)
preoder(p->rchild);
}
void inorder(bnode *p)
{if(p==null)
return;
if(p->lchild!=null)
inoder(p->lchild);
printf("%d",p->data);
if(p->rchild!=null)
inoder(p->rchild);
}
void postorder(bnode *p)
{if(p==null)
return;
if(p->lchild!=null)
postoder(p->lchild);
if(p->rchild!=null)
postoder(p->rchild);
printf("%d",p->data);
}
main()
{bnode *bt,*p,*q;
int x;
printf("Input root:");
scanf("%d",&x);
p=creat(x,null,null);
bt=p;
scanf("%d",&x);
while(x!=-1)
{p=bt;
q=p;
wihle(x!=p->data&&q!=null)
{
p=q;
if(x
data)
q=p->lchild;
else
q=p->rchild;
}
if(x==p->data)
{printf("The data is exit.");
return;
}
else
{if(x
data)
ins_lchild(p,x);
else
ins_rchild(p,x);}
scanf("%d",&x);
}
p=bt;
printf("structure of the binary tree:\n");
printf("number\taddress\tdata\tlchild\trchild\n");
prorder(p);
printf("preorder:");
preorder(p);
printf("\n");
printf("inorder:");
inorder(p);
printf("\n");
printf("postorder:");
postorder(p);
printf("\n");
}
实验三 图遍历的演示
[实验目的]
学习掌握图的两种搜索路径的遍历。
[实验内容]
试写一个程序，演示在连通的无向图上遍历全部结点的操作
[实验要点及说明]
1． 深度优先搜索遍历图的算法：首先访问指定的起始顶点 v0，从v0出发，访问v0的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问过的顶点w2，然后从w2出发，访问w2的一个未被访问过的邻接顶点w3，依次类推，直到一个所有邻接点都被访问过为止。
2． 广度优先搜索遍历图的算法：首先访问指定的起始顶点 v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2，…，wk，然后再依次从w1，w2，…，wk出发，访问它们的所有未被访问过的邻接顶点，依次类推，直到图中所有未被访问过的邻接顶点都被访问过为止。
[实验要求与步骤]
1． 基本要求：采用邻接表作存储结构，实现连通无向图的深度优先搜索遍历和广度优先搜索遍历。
2． 测试数据：如下图：
3． 实现提示：根据广度优先搜索的规则，在其算法实现中，借助一个队列g-queque来存放已被访问过的顶点。从指定顶点开始，每访问一个顶点，就将它入队并排在队尾，然后从队头取出一个顶点，访问该顶点的所有未被访问的邻接点，依次类推，直至队列为空且图中结点均被访问过为止；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
1、深度优先搜索遍历图
#include
#include
#define maxnode 40
#define null 0
typedef struct st_arc
{int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode]; void trave(adjlist g,int n)
{int i,visited[maxnode];
void dfs();
for(i=0;i
visited[i]=0;
for(i=0;i
if(visited[i]==0)
dfs(g,i,visited);
}
void dfs(adjlist g, int k,int visited[]) {arcnode *p;
int w;
visited[k]=1;
printf("%d",g[k].vertex);
p=g[k].firstarc;
while(p!=null)
{w=p->adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}}
main()
{int i,j,n,k,v;
arcnode *p,*q;
adjlist g;
printf("Input node: ");
scanf("%d",&n);
for(k=0;k
{printf("node%d=",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null;
}
for(;;)
{printf("Insert edge i-j:");
scanf("%d",&i);
scanf("%d",&j);
if(i==-1&&j==-1)
break;
q=(arcnode*)malloc(sizeof(arcnode)); q->adjvex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode*)malloc(sizeof(arcnode)); p->adjvex=i;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
printf("dfs:");
trave(g,n);
printf("\n");
}
2、广度优先搜索遍历图
#include
#include
#define null 0
#define maxnode 40
typedef struct st_arc
{int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode]; typedef struct
{int queue[maxnode];
int front,rear;
}qqtype;
void initiate(qqtype *q)
{q->front=-1;
q->rear=-1;
}
int enter(qqtype *q, int x)
{if(q->rear==maxnode-1)
return(-1);
else
{q->rear++;
q->queue[q->rear]=x;
return(0);
}}
int delete(qqtype *q )
{if(q->front==q->rear)
return(null);
else
{q->front++;
return(q->queue[q->front]);
}}
int emtype(qqtype *q)
{if(q->front==q->rear)
return(-1);
return(0);
}
void bfs(adjlist g,int k,int visited[]) {arcnode *p;
int w;
initiate(g);
visited[k]=1;
printf("%d",g[p->adjvex].vertex); enter(g,k);
while(emtype(g)==0)
{w=delete(g);
p=g[w].firstarc;
while(p!=null)
{if(visited[p->adjvex]==0)
{printf("%d",g[p->adjvex].vertex); visited[p->adjvex]=1;
enter(g,p->adjvex);
}
p=p->nextarc;
}}}
void trave(adjlist g,int n)
{int i, visited[maxnode];
for(i=0;i
visited[i]=0;
for(i=0;i
if(visited[i]==0)
bfs(g,i,visited);
}
main()
{int i,j,n,k,v;
arcnode *p,*q;
adjlist g;
printf("Input node:");
scanf("%d",&n);
for(k=0;k
{printf("node%d=",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null;
}
for(;;)
{printf("Insert edge i-j:"); scanf("%d",&i);
scanf("%d",&j);
if(i==-1&&j==-1)
break;
q=(arcnode*)malloc(sizeof(arcnode)); q->adjvex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode*)malloc(sizeof(arcnode)); p->adjvex=i;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
printf("bfs:");
trave(g,n);
printf("\n");
}
实验二 用递归算法遍历二叉树
[实验目的]
学习掌握二叉树各种遍历方法的基本操作算法。
[实验内容]
建立一棵二叉树，并用递归算法分别用前序、中序和后序遍历之。
[实验要点及说明]
由于二叉树的定义是递归的，因而一棵非空二叉树可以看作是由根结点、左子树和右子树这三个基本部分组成的。如果能依次遍历这三个部分的信息，也就遍历了整个二叉树。由此得到的二叉树的遍历是按某种策略访问二叉树中的每一个结点且仅访问一次的过程。二叉树的遍历按访问根结点的先后次序不同分为前序、中序和后序三种。
前序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）访问根结点；
（2）前序遍历左子树；
（3）前序遍历右子树。
中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
[实验要求与步骤]
1． 基本要求：采用递归算法实现前序、中序和后序遍历；
2． 测试数据：
3． 实现提示：二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访
问一次且只被访问一次；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
#include
#define null 0
int counter=0;
typedef struct btreenode
{int data;
struct btreenode *lchild;
struct btreenode *rchild;
}bnode;
bnode *p;
bnode *creat(int x,bnode *lbt, bnode *rbt)
{bnode *p;
p=(bnode*)malloc(sizeof(bnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return(p);
}
bnode *ins_lchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->lchild!=null)
q->rchild=p->lchild;
p->lchild=q;
}
}
bnode *ins_rchild(bnode *p,int x)
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->rchild!=null)
q->lchild=p->rchild;
p->rchild=q;
}}
void prorder(bnode*p)
{if(p==null)
return;
printf("%d\t%u\t%d\t%u\t%u\n",++counter,p,p->data,p->lchild,p->rchild); if(p->lchild!=null)
proder(p->lchild);
if(p->rchild!=null)
proder(p->rchild);
}
void preorder(bnode *p)
{if(p==null)
return;
printf("%d",p->data);
if(p->lchild!=null)
preoder(p->lchild);
if(p->rchild!=null)
preoder(p->rchild);
}
void inorder(bnode *p)
{if(p==null)
return;
if(p->lchild!=null)
inoder(p->lchild);
printf("%d",p->data);
if(p->rchild!=null)
inoder(p->rchild);
}
void postorder(bnode *p)
{if(p==null)
return;
if(p->lchild!=null)
postoder(p->lchild);
if(p->rchild!=null)
postoder(p->rchild);
printf("%d",p->data);
}
main()
{bnode *bt,*p,*q;
int x;
printf("Input root:");
scanf("%d",&x);
p=creat(x,null,null);
bt=p;
scanf("%d",&x);
while(x!=-1)
{p=bt;
q=p;
wihle(x!=p->data&&q!=null)
{
p=q;
if(x
data)
q=p->lchild;
else
q=p->rchild;
}
if(x==p->data)
{printf("The data is exit.");
return;
}
else
{if(x
data)
ins_lchild(p,x);
else
ins_rchild(p,x);}
scanf("%d",&x);
}
p=bt;
printf("structure of the binary tree:\n");
printf("number\taddress\tdata\tlchild\trchild\n");
prorder(p);
printf("preorder:");
preorder(p);
printf("\n");
printf("inorder:");
inorder(p);
printf("\n");
printf("postorder:");
postorder(p);
printf("\n");
}
实验三 图遍历的演示
[实验目的]
学习掌握图的两种搜索路径的遍历。
[实验内容]
试写一个程序，演示在连通的无向图上遍历全部结点的操作
[实验要点及说明]
1． 深度优先搜索遍历图的算法：首先访问指定的起始顶点 v0，从v0出发，访问v0的一个未被访问过的邻接顶点w1，再从w1出发，访问w1的一个未被访问过的顶点w2，然后从w2出发，访问w2的一个未被访问过的邻接顶点w3，依次类推，直到一个所有邻接点都被访问过为止。
2． 广度优先搜索遍历图的算法：首先访问指定的起始顶点 v0，从v0出发，访问v0的所有未被访问过的邻接顶点w1，w2，…，wk，然后再依次从w1，w2，…，wk出发，访问它们的所有未被访问过的邻接顶点，依次类推，直到图中所有未被访问过的邻接顶点都被访问过为止。
[实验要求与步骤]
1． 基本要求：采用邻接表作存储结构，实现连通无向图的深度优先搜索遍历和广度优先搜索遍历。
2． 测试数据：如下图：
3． 实现提示：根据广度优先搜索的规则，在其算法实现中，借助一个队列g-queque来存放已被访问过的顶点。从指定顶点开始，每访问一个顶点，就将它入队并排在队尾，然后从队头取出一个顶点，访问该顶点的所有未被访问的邻接点，依次类推，直至队列为空且图中结点均被访问过为止；
4． 按要求编写程序；
5． 上机录入程序，并进行编辑、编译、调试，直到运行成功。
[参考程序]
1、深度优先搜索遍历图
#include
#include
#define maxnode 40
#define null 0
typedef struct st_arc
{int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode]; void trave(adjlist g,int n)
{int i,visited[maxnode];
void dfs();
for(i=0;i
visited[i]=0;
for(i=0;i
if(visited[i]==0)
dfs(g,i,visited);
}
void dfs(adjlist g, int k,int visited[]) {arcnode *p;
int w;
visited[k]=1;
printf("%d",g[k].vertex);
p=g[k].firstarc;
while(p!=null)
{w=p->adjvex;
if(visited[w]==0)
dfs(g,w,visited);
p=p->nextarc;
}}
main()
{int i,j,n,k,v;
arcnode *p,*q;
adjlist g;
printf("Input node: ");
scanf("%d",&n);
for(k=0;k
{printf("node%d=",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null;
}
for(;;)
{printf("Insert edge i-j:");
scanf("%d",&i);
scanf("%d",&j);
if(i==-1&&j==-1)
break;
q=(arcnode*)malloc(sizeof(arcnode)); q->adjvex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode*)malloc(sizeof(arcnode)); p->adjvex=i;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
printf("dfs:");
trave(g,n);
printf("\n");
}
2、广度优先搜索遍历图
#include
#include
#define null 0
#define maxnode 40
typedef struct st_arc
{int adjvex;
int weight;
struct st_arc *nextarc;
}arcnode;
typedef struct
{int vertex;
struct st_arc *firstarc;
}vernode;
typedef vernode adjlist[maxnode]; typedef struct
{int queue[maxnode];
int front,rear;
}qqtype;
void initiate(qqtype *q)
{q->front=-1;
q->rear=-1;
}
int enter(qqtype *q, int x)
{if(q->rear==maxnode-1)
return(-1);
else
{q->rear++;
q->queue[q->rear]=x;
return(0);
}}
int delete(qqtype *q )
{if(q->front==q->rear)
return(null);
else
{q->front++;
return(q->queue[q->front]);
}}
int emtype(qqtype *q)
{if(q->front==q->rear)
return(-1);
return(0);
}
void bfs(adjlist g,int k,int visited[]) {arcnode *p;
int w;
initiate(g);
visited[k]=1;
printf("%d",g[p->adjvex].vertex); enter(g,k);
while(emtype(g)==0)
{w=delete(g);
p=g[w].firstarc;
while(p!=null)
{if(visited[p->adjvex]==0)
{printf("%d",g[p->adjvex].vertex); visited[p->adjvex]=1;
enter(g,p->adjvex);
}
p=p->nextarc;
}}}
void trave(adjlist g,int n)
{int i, visited[maxnode];
for(i=0;i
visited[i]=0;
for(i=0;i
if(visited[i]==0)
bfs(g,i,visited);
}
main()
{int i,j,n,k,v;
arcnode *p,*q;
adjlist g;
printf("Input node:");
scanf("%d",&n);
for(k=0;k
{printf("node%d=",k);
scanf("%d",&g[k].vertex);
g[k].firstarc=null;
}
for(;;)
{printf("Insert edge i-j:"); scanf("%d",&i);
scanf("%d",&j);
if(i==-1&&j==-1)
break;
q=(arcnode*)malloc(sizeof(arcnode)); q->adjvex=j;
q->nextarc=g[i].firstarc;
g[i].firstarc=q;
p=(arcnode*)malloc(sizeof(arcnode)); p->adjvex=i;
p->nextarc=g[j].firstarc;
g[j].firstarc=p;
}
printf("bfs:");
trave(g,n);
printf("\n");
}