中間シーケンスと後シーケンスの遍歴に基づいて階層遍歴を導出する

12885 ワード

入力:合計ノード数n中シーケンス後シーケンス出力:階層遍歴シーケンス注意出力の最後にスペースがない
試験サンプル:入力:7 2 3 1 5 7 6 4 1 2 3 4 6 7出力:4 1 6 3 7 2
全体的な考え方:2つのシーケンスの入力、ツリーの作成、階層ツリーの遍歴
#include 
#include 
#include 
using namespace std;

const int MAX=50;
struct Node 
{
	int val; 
	Node* lchild;
	Node* rchild;
	Node(int a)
	{
		val=a;
		lchild=NULL;
		rchild=NULL;
	}
	Node()
	{
		val=0;
		lchild=NULL;
		rchild=NULL;
	}
};
int in[MAX],post[MAX];
int n;


// , ,  
Node* createTree(int post[],int i,int in[],int j,int n)
{
	Node* t;
	int ch;
	int p,k;
	if(n<=0) return NULL;
	ch=post[i+n-1];//  
	t=new Node(ch);
	p=j;//  
	while(p<j+n)//  
	{
		if(in[p]==ch)
		break;
		p++;
	}
	k=p-j;//  
	t->lchild=createTree(post,i,in,j,k);
	t->rchild=createTree(post,i+k,in,p+1,n-k-1);
	return t;
	
} 

void BFS(Node* root)
{
	int num=0;// ,  
	queue<Node*> q;
	q.push(root);
	while(!q.empty())
	{
		Node* now=q.front();
		q.pop();
		cout<<now->val;
		num++;
		if(num<n) cout<<" ";//  
		if(now->lchild) q.push(now->lchild);
		if(now->rchild) q.push(now->rchild);
	}
}

int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>post[i];
	}
	for(int i=0;i<n;i++)
	{
		cin>>in[i];
	}
	Node* root=createTree(post,0,in,0,n);
	BFS(root);
	return 0;
}