lab_4.cpp

树的遍历

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

int tree1[1000],tree2[1000];
int tag1[1000],tag2[1000];
int n;
int m;
bool ok;
int f[1000];
int index[1000];
int now;
ifstream file;

void init(int* tag, int* tree,int n)
{
	for (int i=0; i<n; i++)
	{
		char ch;
		file>>ch;
		tag[i]=ch;
	}
	tree[0]=tag[0];
	index[0]=0;
	int a[1000],b[1000];
	for (i=0; i<n; i++) file>>a[i];
	for (i=0; i<n; i++) file>>b[i];
	for (i=0; i<n; i++)
	{
		int x=a[i];
		if (x!=-1) {
			tree[index[i]*2+1]=tag[x];
			index[x]=index[i]*2+1;
		}
		x=b[i];
		
		if (x!=-1) {
			tree[index[i]*2+2]=tag[x];
			index[x]=index[i]*2+2;
		}
	}
}

void visit(int k,int p, int q)
{
	if (tree1[p]==0 || tree2[q]==0) return ;
	if (k==1) 
	{
		if (tree1[p*2+1]!=0 && tree1[p*2+1]==tree2[q*2+1])
			f[p]=now;
		if (tree1[p*2+2]!=0 && tree1[p*2+2]==tree2[q*2+2])
			f[p]=now;
	}
	if (k>=2 && tree1[p]==tree2[q])
	{
	//	cout<<(char)tree1[p]<<' ';
		f[p]=now;
	}
	visit(k+1,p*2+1,q*2+1);
	visit(k+1,p*2+2,q*2+2);
}
	
void print()
{
	for (int i=0; i<n*2; i++)
		if (f[i]==now) cout<<(char)tree1[i]<<' ';
	cout<<endl;
	now++;
}

void process()
{
	memset(f,0,sizeof(f));
	now=1;
	for (int p=0; p<n; p++)
	{
		if (f[index[p]]) continue;
		int x=-1;
		for (int i=0; i<m; i++)
			if (tree2[index[i]]==tree1[index[p]]) 
			{
				x=index[i]; break;
			}
		if (x==-1) continue;
		int q=x;
		visit(1,index[p],q);
		if (f[index[p]])print();
	}
}


int main(){

	file.open("c://data.txt");
	memset(tag1,0,sizeof(tag1));
	memset(tree1,0,sizeof(tree1));
	memset(tag2,0,sizeof(tag2));
	memset(tree2,0,sizeof(tree2));
	memset(index,0,sizeof(index));
	
	file>>n;
	init(tag1,tree1,n);
	file>>m;
	init(tag2,tree2,m);
	//for (int i=0; i<16; i++) cout<<(char)tree1[i]<<' ';
//	cout<<endl;
//	for (i=0; i<16; i++) cout<<(char)tree2[i]<<' ';
//	cout<<endl;
	process();
	file.close();
	return 0;
}