中間シーケンスと後シーケンスの遍歴に基づいて階層遍歴を導出する
12885 ワード
入力:合計ノード数n中シーケンス後シーケンス出力:階層遍歴シーケンス注意出力の最後にスペースがない
試験サンプル:入力:7 2 3 1 5 7 6 4 1 2 3 4 6 7出力:4 1 6 3 7 2
全体的な考え方:2つのシーケンスの入力、ツリーの作成、階層ツリーの遍歴
試験サンプル:入力: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;
}