实验四 树
一、 实验目标
1． 掌握二叉树的前序遍历、中序遍历、后序遍历和层次遍历算法在链式存储结构上实现。
2． 掌握利用遍历二叉树的递归思想实现建立二叉树、复制二叉树、交换二叉树和求二叉树中叶子结点数目等
算法。
3． 理解建立中序线索二叉树和遍历中序线索二叉树算法。
二、 实验内容
1． 建立二叉树、遍历二叉树、统计二叉树中叶子结点数目、交换二叉树的左右子树、复制二叉树操作运算在链式存储结构上实现。其中函数createbitree的功能是利用前序遍历二叉树的算法思想实现建立一棵二叉树，函数preorder、inorder、postorder和levelorder的功能分别是实现前序遍历、中序遍历、后序遍历和层次遍历二叉树，函数swapbiree的功能是实现交换二叉树中所有结点左右子树，函数copybitree的功能是实现复制一棵二叉树，函数countleaf的功能是实现统计二叉树中叶子结点数目。 #include \#include \#define m 100
typedef char datatype;
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; void visitnode(bitree *bt) {
printf(\}
void createbitree(bitree *&bt)
{
char ch; scanf(\ if(ch=='#') {bt=0; return;}
bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); }
void preorder(bitree *bt) {
if(bt!=0) { visitnode(bt); preorder(bt->lchild); preorder(bt->rchild);} }
void inorder(bitree *bt) {
if(bt!=0) { inorder(bt->lchild);visitnode(bt); inorder(bt->rchild);} }
void postorder(bitree *bt) {
if(bt!=0) { postorder(bt->lchild);postorder(bt->rchild); visitnode(bt); } }
void levelorder(bitree *bt)
{
struct {int front,rear; bitree *q[m];}queue; bitree *p=bt;
- 11 -
queue.rear=queue.front=0;
if(bt!=0) {queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p;}
while (!(queue.front==queue.rear)) {
queue.front=(queue.front+1)%m; p=queue.q[queue.front]; visitnode(p);
if(p->lchild!=0){queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p->lchild;}; if(p->rchild!=0){queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=p->rchild;}; }
}
void countleaf(bitree *bt,int &count) {
if(bt==0) return;
if(bt->lchild==0 && bt->rchild==0) count++; if(bt->lchild!=0) countleaf(bt->lchild,count); if(bt->rchild!=0) countleaf(bt->rchild,count); }
void swapbitree(bitree *bt) {
bitree *p;
if(bt==0) return;
swapbitree(bt->lchild); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p; }
void copybitree(bitree *bt1,bitree *&bt2) {
if (bt1==0) {bt2=0; return;}
bt2=(bitree *)malloc(sizeof(bitree)); bt2->data=bt1->data;
copybitree(bt1->lchild,bt2->lchild); copybitree(bt1->rchild,bt2->rchild); }
main( ) {
bitree *bt=0,*bt2=0; int count=0;
createbitree(bt); printf(\ preorder(bt); printf(\ inorder(bt); printf(\ postorder(bt); printf(\ levelorder(bt);printf(\
countleaf(bt,count); printf(\ swapbitree(bt); preorder(bt); printf(\ copybitree(bt,bt2); preorder(bt2);printf(\
}
2． 建立中序线索二叉树和遍历中序线索二叉树的算法。其中函数createbitree的功能是实现建立一棵二叉树，函数createthreadbitree的功能是实现根据已知一棵二叉树建立一棵线索二叉树，函数inthread的功能是实现对以p为根指针的二叉树进行中序线索化，函数inorderthreadbitree的功能是实现中序遍历线索二叉树。 #include \#include \
- 12 -
typedef char datatype;
typedef struct node {datatype data; struct node *lchild,*rchild;int ltag,rtag;} threadbitree; threadbitree *pre; /* 指针变量pre始终指向刚刚被访问过的结点，是一个全局变量 */ void createbitree(threadbitree *&bt) {
char ch; scanf(\ if(ch=='#') {bt=0; return;}
bt=(threadbitree*)malloc(sizeof(threadbitree)); bt->data=ch; createbitree(bt->lchild); createbitree(bt->rchild); }
void inthread(threadbitree *p) {
if(p!=0) {
inthread(p->lchild);
if (p->lchild==0) {p->ltag=1; p->lchild=pre;} /* 建立前驱线索 */
if (pre->rchild==0) {pre->rtag=1; pre->rchild=p;} /* 建立后继线索 */ pre=p; inthread(p->rchild); } }
void createthreadbitree(threadbitree *&head, threadbitree *bt) {
head=(threadbitree *)malloc(sizeof(threadbitree)); head->ltag=0; head->rtag=1; head->rchild=head; if (bt==0) {head->lchild=head; head->ltag=1; return;} head->lchild=bt; pre=head; inthread(bt);
pre->rchild=head; pre->rtag=1; head->rchild=pre; head->rtag=1; /* 最后一个结点线索化 */ }
void inorderthreadbitree(threadbitree *head) {
threadbitree *p=head->lchild;
while (p!=head) {
while (p->ltag==0) p=p->lchild; printf(“%c\\t”,p->data);
while (p->rtag==1 && p->rchild!=head){p=p->rchild; printf(“%c\\t”,p->data);} p=p->rchild; }
}
main( ) {
threadbitree *bt=0,*head=0; createbitree(bt);
createthreadbitree(head,bt); inorderthreadbitree(head); }
- 13 -
实验五 图
一、 实验目标
1． 掌握建立无向图（有向图）的邻接矩阵和邻接表算法。 2． 掌握无向图的深度优先遍历和广度优先遍历算法。 3． 理解连通图的最小生成树算法（普里姆算法）。 4． 理解有向无环图的拓扑排序算法。
二、 实验内容
1. 图的深度优先遍历在链式存储结构（邻接表）上的实现。其中函数createadjlist的功能是实现建立邻接表，函数dfs的功能是实现图的深度优先遍历算法。 #include \#define m 100 #include \#define n 6 #define e 6
int visited[m];
typedef struct node1{int info;int adjvertex; struct node1 *nextarc;}glinklistnode; typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; void createadjlist(glinkheadnode g[ ]) {
int i,j,k; glinklistnode *p;
for(i=0;i scanf(\ p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; } } void dfs(glinkheadnode g[ ], int v0) { glinklistnode *p; printf(\ while(p!=0){ if(visited[p->adjvertex]==0)dfs(g,p->adjvertex); p=p->nextarc; } } main( ) { glinkheadnode g[m]; createadjlist(g); dfs(g,0); } 2. 图的广度优先遍历在顺序存储结构（邻接矩阵）上的实现。其中函数creatematrix的功能是实现建立邻接矩阵，函数bfs的功能是实现图的广度优先遍历。 #include \ - 14 - #define m 100 #define n 6 #define e 6 int visited[m]; typedef struct {int vertex[m]; int edge[m][m];}gadjmatrix; void createadjmatrix(gadjmatrix &g) { int i,j,k; for(i=0; i for(i=0; i for (k=0;k void bfs(gadjmatrix g, int v0) { struct {int front; int rear; int q[m];}queue; int i,j; printf(\ queue.front=queue.rear=0; queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=v0; while(queue.front!=queue.rear) { queue.front=(queue.front+1)%m; i=queue.q[queue.front]; for(j=0;j { printf(\ queue.rear=(queue.rear+1)%m; queue.q[queue.rear]=j; } } } main( ) { gadjmatrix g; createadjmatrix(g); bfs(g,0); } 3. 连通图的最小生成树算法（普里姆算法）在顺序存储结构上的实现。函数prim的功能是实现从编号为v0顶点开始构造最小生成树。 #include \#define max 32767 #define n 6 void prim(int matrix[n][n],int v0) { int i,j,k,min,lowcost[n],closet[n]; for(i=0; i<=n-1;i++) if (i!=v0){lowcost[i]=matrix[v0][i];closet[i]=v0;} else lowcost[i]=0; for(i=1;i<=n-1;i++) { for(min=max,j=0;j<=n-1;j++) if (min>lowcost[j]&&lowcost[j]!=0) {min=lowcost[j];k=j;} - 15 -