subt.cpp

对于给定的2 棵二叉树A和B

#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");


int n,m;


template<class T>
class Queue
{
public:
	Queue(int Max=50000);
	~Queue()
	{
		delete[]queue;
	}
	bool Empty()const
	{
		return front==rear;
	}
	bool Full()const
	{
		return(((rear+1)%Maxsize==front)?1:0);
	}
	T First()const;
	T Last()const;
	Queue<T>& EnQueue(const T& x);
	Queue<T>& DeQueue(T& x);
private:
	int front;
	int rear;
	int MaxSize;
	T *queue;
};


template<class T>
Queue<T>::Queue(int Max)
{
	MaxSize=Max+1;
	queue=new T[MaxSize];
	front=rear=0;
}

 
template<class T>
T Queue<T>::First()const
{
	if(Empty()) 
		throw outofbounds();
	return queue[(front+1)%MaxSize];
}


template <class T>
T Queue<T>::Last()const
{
	if(Empty())
		throw OutOfBounds();
	return queue[rear];
}


template<class T>
Queue<T>&Queue<T>::EnQueue(const T& x)
{
	rear=(rear+1)%MaxSize;
	queue[rear]=x;
	return *this;
}


template<class T>
Queue<T>& Queue<T>::DeQueue(T& x)
{
	front=(front+1)%MaxSize;
	x=queue[front];
	return *this;
}


class BinaryTreeNode
{
public:
	friend class BinaryTree;
	BinaryTreeNode()
	{
		LeftChild=RightChild=0;
	}
	BinaryTreeNode(const int& e)
	{
		data=e;
		LeftChild=RightChild=0;
	}
	BinaryTreeNode(const int&e,BinaryTreeNode *l,BinaryTreeNode *r)
	{
		data=e;
		LeftChild=l;
		RightChild=r;
	}
	int data;
	BinaryTreeNode *LeftChild,*RightChild;
};


class BinaryTree
{
public:
	BinaryTree()
	{
		root=0;
	}
	~BinaryTree(){};
	bool Empty()const
	{
		return ((root)?false:true);
	}
	bool Root(int &x)const;
	void MakeTree(const int& element, BinaryTree &left,BinaryTree& right);	
	int Height(BinaryTreeNode *t);	
	BinaryTreeNode *root;
};


bool BinaryTree::Root(int &x)const
{
	if(root)
	{
		x=root->data;
		return true;
	}
	else
		return false;
}


void BinaryTree::MakeTree(const int& element,BinaryTree &left,BinaryTree &right)
{
	root=new BinaryTreeNode(element,left.root,right.root);
	left.root=right.root=0;
}


int tonggou1(BinaryTreeNode *t,BinaryTreeNode *u)  //判断是否同构
{
	int x=1;
	if(t==NULL&&u!=NULL)    //判断树是否为空
	{
		x=0;
		goto loop;
	}
	else if(t!=NULL&& u!=NULL)
	{
		x=tonggou1(t->LeftChild,u->LeftChild);
		if(x==0)
			goto loop;//递规调用
		x=tonggou1(t->RightChild,u->RightChild);
		if(x==0)
			goto loop;
	}
loop:
	return x;
}	

			
void Judge1(BinaryTreeNode *t,BinaryTreeNode *u)   //扫描整颗树，把结点依次入队
{
	int temp;
	BinaryTreeNode *p;
	Queue<BinaryTreeNode *> q;    //队列初始化 
    if(t!=NULL)
	{
		q.EnQueue(t);                  /*入队列*/
        while(!q.Empty())      /*若队列非空*/
		{
			q.DeQueue(p);      /*出队*/
			temp=tonggou1(p,u); //以出队的结点为根结点开始扫描判断
			if(temp==1)
			{
				out<<"No"<<endl<<"Yes"<<endl;
				goto loop;
			}//找到同构的就马上输出，结束
			else
			{
				if(p->LeftChild!=NULL)
					q.EnQueue(p->LeftChild);   /*入队列*/
				if (p->RightChild!=NULL)
					q.EnQueue(p->RightChild);        /*入队列*/
			}
		}
    }
	if(temp==0)
		out<<"No"<<endl<<"No";
loop:;
}


/*int tonggou2(BinaryTreeNode *t,BinaryTreeNode *u)//判断同构
{
	int x=1;
	if(t==NULL&& u!=NULL)
	{
		x=0;
		goto loop;
	}
	else if(t!=NULL&& u!=NULL)
	{
		x=tonggou2(t->LeftChild,u->LeftChild);
		if(x==0)
			goto loop;
		x=tonggou2(t->RightChild,u->RightChild);
		if(x==0)
			goto loop;
	}
loop:
	return x;
}*/

		
void Judge2(BinaryTreeNode *t,BinaryTreeNode *u)//依次判断各个结点
{
	int temp;
	BinaryTreeNode *p;
	Queue<BinaryTreeNode *> q;    //队列初始化 
    if(t!=NULL)
	{
		q.EnQueue(t);                  //入队列
        while (!q.Empty())      //若队列非空
		{
			q.DeQueue(p);      //出队
			temp=tonggou1(p,u);
			if(temp==1) 
			{
				out<<"Yes"<<endl<<"No"<<endl;
				goto loop;
			}
			else
			{
				if(p->LeftChild!=NULL)
					q.EnQueue(p->LeftChild);   //入队列
				if (p->RightChild!=NULL)
					q.EnQueue(p->RightChild);        //入队列
			}
		}
    }
	if(temp==0)
		out<<"No"<<endl<<"No";
loop:;
}


int tonggou3(BinaryTreeNode *t,BinaryTreeNode *u)  //判断是否同构
{
	int x=1;
	if((t!=NULL&&u==NULL)||(t==NULL&& u!=NULL))    //判断树是否为空
	{
		x=0;
		goto loop;
	}
	else if(t!=NULL&& u!=NULL)
	{
		x=tonggou3(t->LeftChild,u->LeftChild);
		if(x==0)
			goto loop;//递规调用
		x=tonggou3(t->RightChild,u->RightChild);
		if(x==0)
			goto loop;
	}
loop:
	return x;
}	

			
void Judge3(BinaryTreeNode *t,BinaryTreeNode *u)   //扫描整颗树，把结点依次入队
{
    int temp;
    if(t!=NULL)
	{
		temp=tonggou3(t,u); //以出队的结点为根结点开始扫描判断
		if(temp==1) 
			out<<"Yes"<<endl<<"Yes"<<endl;//找到同构的就马上输出，结束
		else 
			out<<"No"<<endl<<"No";
	}
}


void main()
{
	if(in.fail ())
	{
		cout<<"The input.txt is not exist!"<<endl;
		exit(1);
	}
	

	in>>n;
	int **a=new int *[n];   //动态开辟二维数组
	for(int i=0;i<n;i++)
		a[i]=new int [3];
	for(i=0;i<n;i++)       //把数据存在二维数组中
		for(int j=0;j<3;j++)
			in>>a[i][j];
	BinaryTree *tree1=new BinaryTree[n];
	for(i=n-1;i>=0;i--)
		tree1[a[i][0]].MakeTree(a[i][0],tree1[a[i][1]],tree1[a[i][2]]);  //建树
	in>>m;
    int **b=new int *[m];  //动态开辟二维数组
	for(i=0;i<m;i++)
		b[i]=new int [3];
	for(i=0;i<m;i++)   //把数据存在二维数组中
		for(int j=0;j<3;j++)
			in>>b[i][j];
	BinaryTree *tree2=new BinaryTree[m];
	for(i=m-1;i>=0;i--)
		tree2[b[i][0]].MakeTree(b[i][0],tree2[b[i][1]],tree2[b[i][2]]); //建树
	if(n>m)    //因为当n>=m时，n不可能是m的子树
	{
		Judge1(tree1[a[0][0]].root,tree2[b[0][0]].root);
	}
    else if(n==m)
	{
		Judge3(tree1[a[0][0]].root,tree2[b[0][0]].root);
	}
	else 
	{
		Judge2(tree2[b[0][0]].root,tree1[a[0][0]].root);
	}
	for(i=0;i<3;i++)   //与new对应
		delete[] a[i];
	for(i=0;i<3;i++)
		delete[] b[i];
}