BINTREE - Duyệt cây nhị phân

Tác giả: skyvn97

Ngôn ngữ: C++

#include<stdio.h>
#define MAX   50505
struct nod
{
	int parent,left,right;
};
nod bt[MAX];
int pr[MAX];
int in[MAX];
int pr1[MAX];
int in1[MAX];
int n,v;
int vs[MAX];
void build(int num,int fpr,int fin)
{
	if (num<2) return;
	if (in1[pr[fpr]]==fin)
		{
			bt[pr[fpr]].right=pr[fpr+1];
			bt[pr[fpr+1]].parent=pr[fpr];
			build(num-1,fpr+1,fin+1);
			return;
		}
	if (in1[pr[fpr]]==fin+num-1)
		{
			bt[pr[fpr]].left=pr[fpr+1];
			bt[pr[fpr+1]].parent=pr[fpr];
			build(num-1,fpr+1,fin);
			return;
		}
	bt[pr[fpr]].left=pr[fpr+1];
	bt[pr[fpr+1]].parent=pr[fpr];
	bt[pr[fpr]].right=pr[fpr+in1[pr[fpr]]-fin+1];
	bt[pr[fpr+in1[pr[fpr]]-fin+1]].parent=pr[fpr];
	build(in1[pr[fpr]]-fin,fpr+1,fin);
	build(num-in1[pr[fpr]]+fin-1,fpr+in1[pr[fpr]]-fin+1,in1[pr[fpr]]+1);
}
void visit(int x)
{
	if (bt[x].left>0) visit(bt[x].left);
	if (bt[x].right>0) visit(bt[x].right);
	v=v+1;
	vs[v]=x;
}
void process(void)
{
	int i;
	scanf("%d",&n);
	for (i=1;i<=n;i=i+1)
		{
			scanf("%d",&pr[i]);
			pr1[pr[i]]=i;
		}
	for (i=1;i<=n;i=i+1)
		{
			scanf("%d",&in[i]);
			in1[in[i]]=i;
		}
	for (i=1;i<=n;i=i+1)
		{
			bt[i].parent=-1;
			bt[i].left=-1;
			bt[i].right=-1;
		}
	v=0;
	build(n,1,1);	
	visit(pr[1]);
	for (i=1;i<n;i=i+1)
		printf("%d ",vs[i]);
	printf("%d",vs[n]);
}
int main(void)
{	
	process();	
}

Download