tree.cpp

用C实现树和图的相关算法

#include <stdio.h>
#include <malloc.h>
#include "list.h"
#include "string.h"
#include "poly.h"
#include "tree.h"
#include "queue.h"

tree newTree(mystring name)
{
  tree t=(tree)malloc(sizeof(*t));
  t->treeName=name;
  t->vertices=newList();
  return t;
}



vertex newVertex(poly ver)
{
	vertex v=(vertex)malloc(sizeof(*v));
	v->edges=newList();
	v->level=0;
	v->vInfo=ver;
	return v;
}


edge newEdge(vertex start,vertex end)
{
	edge e1=(edge)malloc(sizeof(*e1));
	e1->eInfo=NULL;
	e1->from=start;
	e1->to=end;
	return e1;
}


void treeInsertVertex (tree t, poly x)
{
	vertex v=newVertex(x);
	insertListTail(t->vertices,v);	
}

vertex searchVertex(tree t,poly v)
{
	list l=t->vertices;
	l=l->next;
	while(l)
	{
		if(  ((vertex)(l->element))->vInfo==v )
			return (vertex)(l->element);
		l=l->next;
	}

	printf("\nSearch Failure\n");
	return NULL;
}



void treeInsertEdge (tree t, poly from, poly to)
{
	vertex vFrom=searchVertex(t,from);
	vertex vTo=searchVertex(t,to);
	if(vFrom&&vTo)                               //两个结点都存在
	{
		edge e=newEdge(vFrom,vTo);
		insertListTail(vFrom->edges,e);
	}
	else
		printf("\ninsert edge failure");

}


edge searchEdge(tree t,poly start,poly end)
{
	vertex vFrom=searchVertex(t,start);
	vertex vTo=searchVertex(t,end);
	if(vFrom&&vTo)                             //两个结点都存在
	{
		list l=vFrom->edges;
		l=l->next;
		while(l)
		{
			if( ((edge)(l->element))->to==vTo)
				return (edge)(l->element);
			l=l->next;
		}
	}

	return NULL;
}


void treeInsertEdgeInfo (tree t, poly start, poly end, poly info)
{
	edge e=searchEdge(t,start,end);
	if(e)
	{
		e->eInfo=info;
	}

	else
		printf("\nthe edge no exist\n");

}
  

void visit(poly x)
{
	printf("%s ",x);
}


void treePreOrder (tree t, vertex root)
{
	visit(root->vInfo);
	list l=root->edges;
	l=l->next;
	while(l)
	{
		treePreOrder(t,((edge)(l->element))->to);
		l=l->next;
	}
}




void treeInOrder (tree t, vertex root)
{
	
	list l=root->edges;
	l=l->next;
	if(l==NULL)                                          //结点是否为叶子，是则访问
	{
		visit(root->vInfo);
	}
	else                                                 //不是
	{
		vertex vIn=((edge)(l->element))->to;             //取出最左孩子
		treeInOrder(t, vIn);                             //中根遍历最左孩子

		visit(root->vInfo);                              //中根遍历最左孩子后，访问该结点

		list p=l->next;                                  //最左孩子的兄弟

   	    while(p)                                         //中跟遍历所有最左孩子的兄弟
		{
			treeInOrder(t, ((edge)(p->element))->to);
			p=p->next;
		}
	}


}


void treePostOrder (tree t, vertex root)            
{
	
	list l=root->edges;
	l=l->next;
	
	while(l)
	{
		
		treePostOrder(t,((edge)(l->element))->to);        //以后不要复制代码，之前把前根的复制了过来，调试了很久才发现问题
		l=l->next;
		
	}
	
	
	visit(root->vInfo);


	

}

void treeLevelOrder (tree t)
{
	list l=t->vertices;
	l=l->next;
	vertex root=(vertex)(l->element);

	
	queue q=newQueue();
	enQueue(q,root);

	while(!queueIsEmpty(q))
	{
		poly pTemp=deQueue(q);
		vertex vTemp=(vertex)(pTemp);

		visit(vTemp->vInfo);

		list lTemp=vTemp->edges;
		lTemp=lTemp->next;

		while(lTemp)
		{
//			edge eTemp=(edge)(lTemp->element);
//			vertex vTemp2=eTemp->to;
			enQueue(q,((edge)(lTemp->element))->to);
			lTemp=lTemp->next;
		}


	}



}

/*
 
  void treeToJpg (tree t, char *fileName);
  void treeInOrder (tree t, poly root, visitTy visit);
  void treeLevelOrder (tree t, poly root, visitTy visit);
*/