binarytree.cpp

数据结构中binarytree 遍历及查找,对初学者很有帮助

#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define MAX_VERTEX_NUM 100
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
Boolean Visited[MAX_VERTEX_NUM];

/*--------------------主要数据结构 图------------------------*/
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
	int info;
}ArcNode;
typedef ArcNode* ArcNot;
typedef struct VNode{
	char data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;

/*-------------------辅助数据结构 栈-----------------------*/
typedef struct{
	 ArcNode **base;
	 ArcNode **top;
	 int stacksize;
 }sqstack;

/*-------------------辅助数据结构 队列---------------------*/
typedef struct QNode{
	ArcNot data;
	char vex;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
/*---------------------ADT MFSet--------------------------*/
typedef struct PTNode{
	char data;
	int parent;
}PTNode;
typedef struct {
	PTNode nodes[MAX_VERTEX_NUM];
	int r,n;
}MFSet;
/*---------------------自定义数据结构 边集---------------------*/
typedef struct Linevex{
	char vex1;
	char vex2;//vex1和vex2为边的两顶点
	int info;//边权
}linevex;
typedef struct pvex{
	Linevex vertices[MAX_VERTEX_NUM];//边的集合
}pvex;

/*-------------------------基本操作-------------------------*/
Status InitStack(sqstack &s,int n){
	 s.base=(ArcNode **)malloc(n*sizeof(ArcNode *));
	 if(!s.base)exit(OVERFLOW);
	 s.top=s.base;
	 s.stacksize=n;
	 return OK;
 }
  Status pop(sqstack &s,ArcNot &e){
	 if(s.top==s.base)return ERROR;
	 e=*--s.top;
	 return OK;
 }
 Status push(sqstack &s,ArcNode *e)
 {
	 *s.top++=e;
	 return OK;
 }
 Status StackEmpty(sqstack s)
 {
	 if(s.top==s.base)
		 return TRUE;
	 return FALSE;
 }

Status InitQueue(LinkQueue &Q){                                 //建立队列
	Q.front=(QueuePtr)malloc(sizeof(QNode));
    Q.rear=Q.front;
	//if(!Q.front)exit(OVERFLOW);
	Q.front->next=NULL;
	return OK;
}
Status EnQueue(LinkQueue &Q,ArcNode *e){                          //入列
	QueuePtr p;
	p=(QueuePtr)malloc(sizeof(QNode));
	//if(!p)exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}
Status DeQueue(LinkQueue &Q,ArcNot &e){                         //出列
	QueuePtr p;
	if(Q.front==Q.rear)return ERROR;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)Q.rear=Q.front;
	free(p);
	return OK;
}
Status QueueEmpty(LinkQueue Q){                                 //判断队列是否为空
	if(Q.front==Q.rear)
		return OK;
	else return FALSE;
}

Status Initial_mfset(MFSet &s,ALGraph G)                        //等价类的初始化
{
	int i;
	for(i=0;i<G.vexnum;i++)
	{
		s.nodes[i].data=G.vertices[i].data;
		s.nodes[i].parent=-1;
	}
	s.n=G.vexnum;
	return OK;
}

int find_mfset(MFSet s,char vex)                                //寻找根结点
{
	int i;
	for(i=0;i<s.n;i++)
		if(s.nodes[i].data==vex)
		{
			for(;s.nodes[i].parent>0;i=s.nodes[i].parent);
			break;
		}
	return i;
}

Status merge_mfset(MFSet &s,int i,int j)                        //等价类的合并                       
{
	if(i<0||i>s.n||j<0||j>s.n)return ERROR;
	s.nodes[i].parent=j;
	return OK;
}
/*=============================================================================*/

int count=0;      //边集计数器

Status CreateALGraph(ALGraph &G)                                  //图的建立
{
	int i,j,m,n,num,quan;
	char vex;
	ArcNode *point;
	printf("输入图中总的顶点数和边数x,y");
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	printf("依次输入每个顶点的名称x y z .....");
	for(i=0;i<G.vexnum;i++)
	{
		getchar();
		scanf("%c",&G.vertices[i].data);
	}
	for(j=0;j<G.vexnum;j++)
	{
		printf("与顶点%c相邻的顶点数以及（名称，权值）：",G.vertices[j].data);
		getchar();
		scanf("%d",&num);
		for(m=0;m<num;m++)
		{
			getchar();
			scanf("(%c,%d)",&vex,&quan);
			for(n=0;n<G.vexnum;n++)
				if(G.vertices[n].data==vex)break;
			if(m==0)
			{
				if(!(G.vertices[j].firstarc=(ArcNode *)malloc(sizeof(ArcNode))))exit(OVERFLOW);
				G.vertices[j].firstarc->adjvex=n;
				G.vertices[j].firstarc->info=quan;
				point=G.vertices[j].firstarc;
			}
			else
			{
				if(!(point->nextarc=(ArcNode *)malloc(sizeof(ArcNode))))exit(OVERFLOW);
				point->nextarc->adjvex=n;
				point->nextarc->info=quan;
				point=point->nextarc;
			}
		}
		point->nextarc=NULL;
	}
	return OK;
}


void DFSTraverse(ALGraph G)                                  //深度优先遍历
{
	sqstack s;
	ArcNode *p;	
	int i,v;
	char vex;
	InitStack(s,G.arcnum);
	printf("输入访问开始的顶点:");
	getchar();
	scanf("%c",&vex);
	for(i=0;i<G.vexnum;i++)
		if(G.vertices[i].data==vex)
			break;
	for(v=0;v<G.vexnum;v++)
		Visited[v]=FALSE;
	printf("%c",G.vertices[i].data);
	Visited[i]=TRUE;
	for(p=G.vertices[i].firstarc;p;)
	{
		push(s,p);
		while(!StackEmpty(s))
		{
			if(p!=NULL)
			{
				if(!Visited[p->adjvex])
				{
					printf("%c",G.vertices[p->adjvex].data);
					Visited[p->adjvex]=TRUE;
					p=G.vertices[p->adjvex].firstarc;
					push(s,p);				
				}
				else
				  p=p->nextarc;
			}
			else
			{
				pop(s,p);
				p=p->nextarc;
			}
		}
	}
}


void BFSTraverse(ALGraph G)                                          //广度优先遍历
{
	LinkQueue Q;
	int i,v;
	char vex;
	ArcNode *p;
	InitQueue(Q);
	printf("输入访问开始的顶点:");
	getchar();
	scanf("%c",&vex);
	for(i=0;i<G.vexnum;i++)
		if(G.vertices[i].data==vex)
			break;
	for(v=0;v<G.vexnum;v++)
		Visited[v]=FALSE;
	printf("%c",G.vertices[i].data);
	Visited[i]=TRUE;
	for(p=G.vertices[i].firstarc;p;p=p->nextarc)
	{
		EnQueue(Q,p);
		Visited[p->adjvex]=TRUE;
	}
	while(!QueueEmpty(Q))
	{
		DeQueue(Q,p);
		printf("%c",G.vertices[p->adjvex].data);
		for(p=G.vertices[p->adjvex].firstarc;p;p=p->nextarc)
		{
			if(!Visited[p->adjvex])
			{
				EnQueue(Q,p);
				Visited[p->adjvex]=TRUE;
			}
		}
	}
}


Status Create(pvex &t,ALGraph G)                                           //边集的建立
{
	int v,i;
	ArcNode *p;
	for(v=0;v<G.vexnum;v++)
		Visited[v]=FALSE;
	for(i=0;i<G.vexnum;i++)
	{
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
		{
			if(!Visited[p->adjvex])
			{
				t.vertices[count].vex1=G.vertices[i].data;
				t.vertices[count].vex2=G.vertices[p->adjvex].data;
				t.vertices[count].info=p->info;
				count++;
			}
		}
		Visited[i]=TRUE;
	}
	return OK;
}


void OrderLinevex(ALGraph G,pvex &t)                                       //边集的排序
{
	int i,j;
	pvex p;
	for(i=0;i<=count-2;i++)
		for(j=0;j<=count-i-1;j++)
		{
			if(t.vertices[j].info>t.vertices[j+1].info)
			{
				p.vertices[0]=t.vertices[j];
				t.vertices[j]=t.vertices[j+1];
				t.vertices[j+1]=p.vertices[0];
			}
		}
}	

Status Findtree(pvex t,MFSet &s)                                           //等价类的合并
{
	int i,n1,n2;
	for(i=0;i<count;i++)
	{
		n1=find_mfset(s,t.vertices[i].vex1);
		n2=find_mfset(s,t.vertices[i].vex2);
		if(n1!=n2)
		{
			merge_mfset(s,n1,n2);
			printf("%c----%c,边权为:%d\n",t.vertices[i].vex1,t.vertices[i].vex2,t.vertices[i].info);
		}
	}
	return OK;
}



void main()
{
	ALGraph G;
	pvex t;
	MFSet s;
 	CreateALGraph(G);
	DFSTraverse(G);
	printf("\n");
	BFSTraverse(G);
	printf("\n");
	Create(t,G);
	Initial_mfset(s,G);
	OrderLinevex(G,t);
	printf("该图的最小生成树为:\n");
	Findtree(t,s);
}