//四叉樹的建立;前序遍歷;求并
//By Yake_wyt*04/11/12
//輸入規則:第i個結點的nw,ne,sw,se分別為4i,4i+1,4i+2,4i+3,結束時輸入0 0
//G:2,B:1,W:0
#include <iostream.h>
#include <stdlib.h>
#define MAX 64

typedef struct quadtree
{	int data;
	struct quadtree *nw,*ne,*sw,*se;
}Quadtree;

int i=0,j=0,m=0,u=0,v=0;
int prea[32],preb[32],prec[32];
Quadtree *nar[MAX];

Quadtree *creatQuadtree()
{	int r,s,w;
	Quadtree *q,*t;	
	cout<<"請輸入結點的編號及其內容:\n";
	cin>>r>>s;
	while(r!=0)
	{	q=(Quadtree *)malloc(sizeof(Quadtree));
		q->data=s;q->nw=NULL;q->ne=NULL;q->sw=NULL;q->se=NULL;
		nar[r]=q;
		if(r==1) t=q;
		else
		{	w=r/4;
			if(r%4==0) nar[w]->nw=q;
			if(r%4==1) nar[w]->ne=q;
			if(r%4==2) nar[w]->sw=q;
			if(r%4==3) nar[w]->se=q;
		}
		cout<<"請輸入結點的編號及其內容:\n";
		cin>>r>>s;
	}
	return t;
}

void preordera(Quadtree *p)
{	if(p!=NULL)
	{	prea[u++]=p->data;
		prea[u]=3;
		cout<<p->data<<" ";
		preordera(p->nw);
		preordera(p->ne);
		preordera(p->sw);
		preordera(p->se);
	}
}

void preorderb(Quadtree *q1)
{	if(q1!=NULL)
	{	preb[v++]=q1->data;
		preb[v]=3;
		cout<<q1->data<<" ";
		preorderb(q1->nw);
		preorderb(q1->ne);
		preorderb(q1->sw);
		preorderb(q1->se);
	}
}

void aalsob()
{	if((prea[0]==2)&&(preb[0]==2))
	{	prec[m]=2;i++;j=j+1;m++;
		while((prea[i])!=3)
		{	if(prea[i]==2&&preb[j]==2)
			{	prec[m]=2;
				for(int n=1;n<=4;n++)
				{	j++;prec[++m]=(prea[++i])||(preb[j]);}
				if((prec[m]==1)&&(prec[m-1]==1)&&(prec[m-2]==1)&&(prec[m-3]==1))
				{	prec[m-4]=1;m=m-4;}
				i++;j++;m++;}
			if((prea[i]==2)&&(preb[j]==0))
			{	prec[m]=2;
				for(int n=1;n<=4;n++)
					prec[++m]=prea[++i];
				i++;j++;m++;}
			if((prea[i]==2)&&(preb[j]==1))
			{	prec[m]=1;i=i+5;j++;m++;}
			if((prea[i]==1)&&(preb[j]==2))
			{	prec[m]=1;j=j+5;i++;m++;}
			if((prea[i]==1)&&(preb[j]==1))
			{	prec[m]=1;i++;j++;m++;}
			if((prea[i]==1)&&(preb[j]==0))
			{	prec[m]=1;i++;j++;m++;}
			if((prea[i]==0)&&(preb[j]==2))
			{	prec[m]=2;
				for(int n=1;n<=4;n++)
					prec[++m]=preb[++j];
				i++;j++;m++;}
			if((prea[i]==0)&&(preb[j]==1))
			{	prec[m]=1;i++;j++;m++;}
			if((prea[i]==0)&&(preb[j]==0))
			{	prec[m]=0;i++;j++;m++;}
			prec[m]=3;}
	}
	if(prea[0]==1)
	{	prec[0]=1;prec[1]=3;}
	if(preb[0]==1)
	{	prec[0]=1;prec[1]=3;}
	if((prea[0]==0)&&(preb[0]==2))
	{	while(preb[j]!=3)	
			prec[m++]=preb[j++];
		prec[m]=3;}
	if((prea[0]==2)&&(preb[0]==0))
	{	while(prea[i]!=3)	
			prec[m++]=prea[i++];
		prec[m]=3;}
	if((prea[0]==0)&&(preb[0]==0))
	{	prec[0]=0;prec[1]=3;}
}

void main()
{	int k=0;
	Quadtree *heada,*headb;

	heada=creatQuadtree();
	cout<<"A的前序遍歷:\n";
	preordera(heada);
	
	cout<<"\n";

	headb=creatQuadtree();
	cout<<"B的前序遍歷:\n";
	preorderb(headb);
	
	cout<<"\n";
	
	aalsob();

	cout<<"A||B=\n";

	while(prec[k]!=3)
	{	cout<<prec[k]<<" ";
		k++;
	}

	cout<<"\n";
}