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();
}