好后缀二叉树620post.cpp

设计一个算法

#include <iostream>
#include <fstream>
using namespace std;


ofstream out("output.txt");

int N,M=0;
int JIE[50000];


class BinaryTreeNode//二叉树结点
{
	friend class BinaryTree;
public:
	BinaryTreeNode(){LeftChild=RightChild=0;}
	void newNode(int e)
	{
		data=e;
		LeftChild=RightChild=0;
	}
private:
	int data;
	BinaryTreeNode *LeftChild,*RightChild;//左右子树
};

//定义二叉树
class BinaryTree
{
public:
	BinaryTree(){root=0;}
	~BinaryTree(){};
	bool Empty()const
	{return((root)?false:true);}
	
	bool Root(int &x);//在x中返回根结点的标号
	void MakeTree(BinaryTreeNode *e,BinaryTreeNode *l,BinaryTreeNode *r,int i);//构建树
	
	void PreOutput()//以前序遍历输出二叉树
	{	
		PreOrder(root);		
	}
	void PostOutput()//以后序遍历输出二叉树
	{
		PostOrder(root);		
	}
	//int Height()const{return Height(root);}//高度
	//int Size(){int count=0;PreOrder(root);return count;}//结点数
private:
	BinaryTreeNode *root;
	void PreOrder(BinaryTreeNode *t);
	void  PostOrder(BinaryTreeNode *t);
	void Output(BinaryTreeNode *t)
	{
		if(t->LeftChild==NULL&&t->RightChild==NULL)
			JIE[M]=0;
		else
			if(t->LeftChild!=NULL&&t->RightChild==NULL)
				JIE[M]=1;
			else
				if(t->LeftChild==NULL&&t->RightChild!=NULL)
					JIE[M]=2;
				else if(t->LeftChild!=NULL&&t->RightChild!=NULL)
					JIE[M]=3;				
		M++;		
	}	
};
//返回根结点的标号
bool BinaryTree::Root(int &x)
{
	if(root)
	{
		x=root->data;
		return true;
	}
	else return false;
}


//构建二叉树
void BinaryTree::MakeTree(BinaryTreeNode *e,BinaryTreeNode *l,BinaryTreeNode *r,int i)
{
	e->LeftChild=l;
	e->RightChild=r;
	if(i==0) root=e;//根结点的情况
}
 
//前序遍历
void BinaryTree::PreOrder(BinaryTreeNode *t)
{
	if(t)
	{
		Output(t);//前序遍历，遍历一个结点就输出一个
		PreOrder(t->LeftChild);
		PreOrder(t->RightChild);
	}
}
//后序遍历
void BinaryTree::PostOrder(BinaryTreeNode *t)
{
	if(t)
	{		
		PostOrder(t->LeftChild);
		PostOrder(t->RightChild);
		Output(t);		//后序遍历，遍历一个结点就输出一个
	}
}
/*
void NoMem(){cout<<"NoMem!"<<endl;}
//前缀函数
void Prefix(int *t,int m)
{		
	int *pre=new int[m+1];
	if(pre==0) throw NoMem();
	pre[1]=0;
	int k=0;
	for(int i=2;i<=m;i++)
	{
		while((t[i-1]!=t[k])&&(k>0)) 
			k=pre[k];
		if(t[i-1]==t[k])
			pre[i]=++k;
		else pre[i]=0;
	}
}
//KMP模式匹配运算
int Match(int *t1,int *t2,int m,int n)
{
	int i=1,j=0,count=0;	;	
	Prefix(t1,m);
	do
	{
		while((i<=n)&&(j<m))
		{
			if(t2[i-1]==t1[j])
			{				
				i++;
				j++;
			}
			else
			{
				if(j==0) i++;
				else j=t1[j];
			}
		}		
		if(j<m&&count>=m) return 1;
		else 
		{
			count+=1;			
		}
		j=0;
	}while(i<=n);
	if(count>=m)
		return 1;
	else return 0;
}

//修改后的前缀函数
/*void ModifiedPrefix(int m)
{
	int *f,i;	
	f=new int[m+1];
	Prefix(m);
	for(i=1;i<=m;i++)
		f[i]=pre[i];
	for(i=1;i<m;i++)
	{
		int k=f[i];
		if((k==0)||(*(str+i)!=*(str+k)))
			pre[i]=k;
		else pre[i]=pre[k];
	}
	delete []f;
}*/
int Match(int *t1,int *t2,int m,int n)
{
	int i=1,j=1;
	while((i<=n)&&(j<=m))
	{
		if(t2[i-1]==t1[j-1])
		{
			i++;j++;
		}
		else
		{
			i=i-j+2;
			j=1;
		}
	}
	if(j<=m) return 0;
	else return 1;	
}
//关键应用函数。。。。
void cmp(int *A1,int *B1,int *A2,int *B2,int n,int m)
{	
	int i,j,s=0,biao=0;
	biao=Match(A1,B1,n,m);
	cout<<biao<<endl;
	biao=Match(A2,B2,n,m);
	/*for(i=0,j=0;i<m;i++,j++)
	{
		if(A1[j]==B1[i])
		{			
			s++;
			if(s==n) break;
		}
		else 
		{
			s=0;
			j=0;
		}
	}
	if(s>=n) biao=1;
	else biao=0;	
	for(i=0,j=0;i<m;i++,j++)
	{
		if(A2[j]==B2[i])
		{			
			s++;
			if(s==n) break;
		}
		else 
		{
			s=0;
			j=0;
		}
	}
	if(s>=n) biao=1;
	else biao=0;*/	
	if(biao==1) out<<"Yes"<<endl;
	else out<<"No"<<endl;
}



int main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"No exit!";
		exit(1);
	}	
	int n,i,x,y,z;
	//构建第一棵二叉树
	in>>n;
	N=n;	
	int *p1=new int[n];
	int *p2=new int[n];
	BinaryTreeNode **a;
	BinaryTree tree1;
	a=new BinaryTreeNode*[n];
	for(i=0;i<n;i++)//先将结点数组按号标号。。。
	{
		a[i]=new BinaryTreeNode;
		a[i]->newNode(i+1);		
	}	
	for(i=0;i<n;i++)
	{
		in>>x>>y>>z;
		if(y==0&&z==0&&i!=0)continue;//该结点无子结点
		else if(y==0&&z==0&&i==0)  tree1.MakeTree(a[x-1],0,0,i);
		else if(y==0)  tree1.MakeTree(a[x-1],0,a[z-1],i);
		else if(z==0)   tree1.MakeTree(a[x-1],a[y-1],0,i);
		else tree1.MakeTree(a[x-1],a[y-1],a[z-1],i);
	}
	tree1.PostOutput();
	for(i=0;i<N;i++)
	{			
		p1[i]=JIE[i];
		cout<<p1[i]<<" ";		
	}
	M=0;
	cout<<endl;
	tree1.PreOutput();
	for(i=0;i<N;i++)
	{		
		p2[i]=JIE[i];
		cout<<p2[i]<<" ";
	}
	M=0;
	cout<<endl;
	//构建第二棵二叉树
	int m;
	in>>m;
	N=m;
	int *q1=new int[m];
	int *q2=new int[m];
	BinaryTreeNode **b;
	BinaryTree tree2;
	b=new BinaryTreeNode*[m];
	for(i=0;i<m;i++)
	{
		b[i]=new BinaryTreeNode;
		b[i]->newNode(i+1);
	}
	for(i=0;i<m;i++)
	{
		in>>x>>y>>z;
		if(y==0&&z==0&&i!=0)continue;//该结点无子结点
		else if(y==0&&z==0&&i==0)  tree2.MakeTree(b[x-1],0,0,i);
		else if(y==0)  tree2.MakeTree(b[x-1],0,b[z-1],i);
		else if(z==0)   tree2.MakeTree(b[x-1],b[y-1],0,i);
		else tree2.MakeTree(b[x-1],b[y-1],b[z-1],i);
	}
	tree2.PostOutput();
	for(i=0;i<N;i++)
	{		
		q1[i]=JIE[i];
		cout<<q1[i]<<" ";		
	}
	M=0;
	cout<<endl;
	tree2.PreOutput();
	for(i=0;i<N;i++)
	{		
		q2[i]=JIE[i];
		cout<<q2[i]<<" ";
	}
	M=0;
	cout<<endl;
	//判断A是否为B的后缀
	if(n>m)
		out<<"No"<<endl;
	else
		cmp(p1,q1,p2,q2,n,m);
	//判断B是否为A的后缀
	if(m>n)
		out<<"No"<<endl;
	else
		cmp(q1,p1,q2,p2,m,n);
	delete []p1;
	delete []p2;
	delete []a;
	delete []b;
	delete []q1;
	delete []q2;
	return 1;
}