子树问题545subt.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
class BinaryTreeNode
{
	friend class BinaryTree;
	friend  bool PartEqual(BinaryTreeNode *t1,BinaryTreeNode *t2);
	public:
		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;
		}
	private:
		int data;
		BinaryTreeNode *LeftChild,
				       *RightChild;
};
class BinaryTree
{
	public:
		BinaryTree(){root=0;num=0;}
		BinaryTree(int e , int *p);////////
        ~BinaryTree(){}
		bool Empty() const
		{
			return ((root) ? false : true);
		}
		void PostOrder( void(*Visit)(BinaryTreeNode *u) )
		{
			PostOrder(Visit,root);
		}
		void InOrder( void(*Visit)(BinaryTreeNode *u) )
		{
			InOrder(Visit,root);
		}
		void Delete()
		{
			delete []first;
		}
		void PostOutput(){PostOrder(Output,root);cout<<endl;}//for examine
		BinaryTreeNode *root;
		int num;
		BinaryTreeNode *first;
	private:				
		static void Output(BinaryTreeNode *t){cout<<t->data<<' ';}//for examine
		void PostOrder( void(*Visit)(BinaryTreeNode *u) , BinaryTreeNode *t);////
		void InOrder( void(*Visit)(BinaryTreeNode *u) , BinaryTreeNode *t);////
		static void Free(BinaryTreeNode *t)
		{
			delete t;
		}
};
bool PartEqual(BinaryTreeNode *t1,BinaryTreeNode *t2)
{
	if(t1&&t2)
	{
	//	if(    ((t1->LeftChild==0 && t2->LeftChild==0)||(t1->LeftChild && t2->LeftChild))
	//		&& ((t1->RightChild==0 && t2->RightChild==0)||(t1->RightChild && t2->RightChild)) 
	//	  )
	//	{
			if( PartEqual(t1->LeftChild,t2->LeftChild) )
			{
				return PartEqual(t1->RightChild,t2->RightChild);
			}else return false;
	//	}else return false;
	}
	if(!t2) return true;
	else return false;
}
bool SunTree(BinaryTree &a1,BinaryTree &a2)
{
	for(int i=1; i<=a1.num; i++)
	{
		if( PartEqual(&a1.first[i], a2.root)) return true;
	}
	return false;
}
void BinaryTree::InOrder( void(*Visit)(BinaryTreeNode *u) , BinaryTreeNode *t)
{
	if(t)
	{
		InOrder(Visit , t->LeftChild);
		Visit(t);
		InOrder(Visit , t->RightChild);
	}
}
void BinaryTree::PostOrder( void(*Visit)(BinaryTreeNode *u) , BinaryTreeNode *t)
{
	if(t)
	{
		PostOrder(Visit , t->LeftChild);
		PostOrder(Visit , t->RightChild);
		Visit(t);		
	}
}
BinaryTree::BinaryTree(int e , int *p)//注意！！数组p从下标为1开始存数element 为元素个数
{
	BinaryTreeNode *tree1 = new BinaryTreeNode [e+1];
	first=tree1;
	tree1[0].data =0;
	tree1[0].LeftChild =0;
	tree1[0].RightChild =0;
	for(int i = 1 , j = 1 ; j <= e ; j++)
	{
		int n=p[i];
		tree1[n].data = p[i];
		i++;
		if(p[i])
		{
			tree1[n].LeftChild = &tree1[p[i]];
		}else
			tree1[n].LeftChild = 0;
		i++;
		if(p[i])
		{
			tree1[n].RightChild = &tree1[p[i]];
		}else
			tree1[n].RightChild =0;
		i++;
	}
	root = &tree1[1];
	num = e;
}
void main()
{	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"The input.txt is not exit!!"<<endl;
	}
	ofstream out("output.txt");
	int m,n;
	in>>m;
	int *p = new int [3*m+1];
	for(int g=1 ; g<=3*m ; g++)
	{
		in>>p[g];
	}
	in>>n;	
	int *h = new int [3*n+1];
	for(int a=1 ; a<=3*n ; a++)
	{
		in>>h[a];
	}

	BinaryTree tree1(m,p);
	BinaryTree tree2(n,h);
	if(m>n)
	{
		out<<"No"<<endl;
		if( SunTree(tree1,tree2) )out<<"Yes";
		else out<<"No";
	}else if(m==n)
	{	
		if( SunTree(tree1,tree2) )out<<"Yes"<<endl<<"Yes";
		else out<<"No"<<endl<<"No";	
	}
	else
	{
		if( SunTree(tree2,tree1) )out<<"Yes"<<endl;
		else out<<"No"<<endl;
		out<<"No";
	}
	tree1.Delete ();
	tree2.Delete ();
}