exp3_1.cpp

二叉树的基本操作（1）在二叉链表上设计和实现下列二叉树运算的算法 ① 设计递归算法

#include <iostream.h>
enum ResultCode{Duplicate,Failure,Success,Underflow,NotPresent,overflow}; 

template <class T>
class Graph
{
public:
	virtual ResultCode Insert(int u,int v,T& w)=0;
	virtual ResultCode Remove(int u,int v)=0; 
	virtual bool Exist(int u,int v)const=0; 
    virtual int Vertices()const {return n;} 
protected: 
    int n,e; 
}; 

//*************邻接矩阵类******************************************************************************************

template<class T>
class MGraph:public Graph<T>
{
public:
    MGraph(int mSize,const T& noedg);
	~MGraph();
    ResultCode Insert(int u,int v, T& w);
	ResultCode Remove(int u,int v);
	bool Exist(int u,int v)const;


    void Output(ostream& out)const;
protected:
 T**a;
 T noEdge;
};

template<class T>		
MGraph<T>::MGraph(int mSize, const T& noedg)   //构造函数
{
	n=mSize;e=0;noEdge=noedg;
	a= new T*[n];
	for(int i=0;i<n;i++)
	{
		a[i]=new T [n];
		for (int j=0;j<n;j++) a[i][j]=noEdge;
		a[i][i]=0;
	}
}

template<class T>		
MGraph<T>::~MGraph()  //析构函数
{
	for(int i=0;i<n;i++) delete []a[i];
	delete []a;
}

template<class T>	
ResultCode MGraph<T>::Insert(int u,int v, T& w) 	//插入函数
{
    if(u<0||v<0||u>n-1||v>n-1||u==v) return Failure;
    if(a[u][v]!=noEdge)return Duplicate;
    a[u][v]=w; e++;
    return Success;
}


template<class T>	
ResultCode MGraph<T>::Remove(int u,int v)	//删除函数
{
	if(u<0||v<0||u>n-1||v>n-1||u==v) return Failure;
	if(a[u][v]==noEdge)return NotPresent;
	a[u][v]=noEdge;e--;return Success;
}

template<class T>		
bool MGraph<T>::Exist(int u,int v)   //搜索函数
{
	if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==noEdge) return false;
	return true;
}

//**********************扩充MGraph类******************************************************************************************************
template <class T>
class ExtMGraph: public MGraph<T> 
{
public:
    ExtMGraph(int mSize,const T& noedg):MGraph<T>(mSize,noedg){} //调用父类的构造函数
	void DFS();
	void BFS();
private:
    void DFS(int v,bool* visited);
	void BFS(int v,bool* visited);
};


template <class T>                                 //公有DFS函数定义
void ExtMGraph<T>::DFS()
{
	bool *visited=new bool[n];
	for(int i=0;i<n;i++)
		visited[i]=false;
	for(i=0;i<n;i++)
	{
		if(!visited[i]) DFS(i,visited);
	}
	delete[]visited;
	cout<<endl;
}


template <class T>                                 //私有DFS函数定义
void ExtMGraph<T>::DFS(int v,bool *visited)
{
	visited[v]=true;
	cout<<" "<<v;
	for(int i=0;i<n;i++)
	{
		if(a[v][i]==1&&!visited[i])
		DFS(i,visited);
	}
}

template <class T>                                 //公有BFS函数定义
void ExtMGraph<T>::BFS()
{
	bool *visited=new bool[n];
	for(int i=0;i<n;i++)
		visited[i]=false;
	for(i=0;i<n;i++)
	{
		if(!visited[i]) BFS(i,visited);
	}
	delete[]visited;
	cout<<endl;
}











//***********************邻接表类****************************************************************************************
template<class T>
struct ENode   //边结点结构体
{
    ENode(){ nextArc=NULL; }
    ENode(int vertex,T weight,ENode* next)
    {
        adjVex=vertex;w=weight;nextArc=next;
    }
    int adjVex;
    T w;
    ENode* nextArc;
};

template<class T>
class LGraph:public Graph<T>
{
    public:
        LGraph(int mSize);
        ~LGraph();
        ResultCode Insert(int u,int v,T& w);
        ResultCode Remove(int u,int v);
        bool Exist(int u,int v)const;
    protected:
        ENode<T> **a;
};

template <class T>
LGraph<T>::LGraph(int mSize)    //构造函数
{
   n=mSize;e=0;
   a=new ENode<T>* [n];
   for(int i=0;i<n;i++)a[i]=NULL;
}

template<class T>
LGraph<T>::~LGraph()     //析构函数
{
   ENode<T> *p,*q;
   for(int i=0;i<n;i++){
   p=a[i];q=p;
   while(p){
       p=p->nextArc;delete q;q=p;
   }
   }
   delete[] a;
}

template<class T>
ResultCode LGraph<T>::Insert(int u,int v,T& w)  //插入函数
{
  if(u<0||v<0||u>n-1||v>n-1||u==v)return Failure;
  if(Exist(u,v))return Duplicate;
  ENode<T>* p=new ENode<T>(v,w,a[u]);
  a[u]=p;e++;
  return Success;
}

template<class T>
ResultCode LGraph<T>::Remove(int u,int v)    //删除函数
{
  if(u<0||v<0||u>n-1||v>n-1||u==v)return Failure;
   ENode<T> *p=a[u],*q=NULL;
  while(p&&p->adjVex!=v)  { q=p;p=p->nextArc;  }
   if(!p)return NotPresent;
   if(q)q->nextArc=p->nextArc;
     else a[u]=p->nextArc;
   delete p;
    e--;
   return Success;
}

template<class T>
bool LGraph<T>::Exist(int u,int v)const //搜索函数
{
  if(u<0||v<0||u>n-1||v>n-1||u==v)return false;
  ENode<T>* p=a[u];
  while(p&&p->adjVex!=v) p=p->nextArc;
  if(!p)return false;
  else return true;
}