2015
04-14

# The order of a Tree

As we know,the shape of a binary search tree is greatly related to the order of keys we insert. To be precisely:
1.  insert a key k to a empty tree, then the tree become a tree with
only one node;
2.  insert a key k to a nonempty tree, if k is less than the root ,insert
it to the left sub-tree;else insert k to the right sub-tree.
We call the order of keys we insert “the order of a tree”,your task is,given a oder of a tree, find the order of a tree with the least lexicographic order that generate the same tree.Two trees are the same if and only if they have the same shape.

There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.

There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.

4

1 3 4 2

1 3 2 4

/*

又是一个月黑风高的夜晚，终于。。。又可以刷题了，囧~，

水~
其实就是把这个树构成，然后遍历一遍输出，遍历顺序就

我这个建树的思想来自写的字典树，所以就分类到字典树

2013-10-22
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"

int n;
struct Tree
{
struct Tree *left,*right;
int num;
};
struct Tree *root;
int ans[100111],k;

void insert(int aim)
{
struct Tree *now,*next;
now=root;
while(now->num)
{
if(aim<now->num)
{
if(now->left==NULL)
{
next=(struct Tree *)malloc(sizeof(struct Tree));
next->left=next->right=NULL;
next->num=0;
now->left=next;
now=next;
}
else	now=now->left;
}
else
{
if(now->right==NULL)
{
next=(struct Tree *)malloc(sizeof(struct Tree));
next->left=next->right=NULL;
next->num=0;
now->right=next;
now=next;
}
else	now=now->right;
}
}
now->num=aim;
}
void solve(struct Tree *now)
{
ans[k++]=now->num;
if(now->left!=NULL)	solve(now->left);
if(now->right!=NULL)solve(now->right);
}
int main()
{
int i;
int temp;
while(scanf("%d",&n)!=-1)
{
if(n<=0)	continue;
root=(struct Tree *)malloc(sizeof(struct Tree));
root->left=root->right=NULL;
root->num=0;
for(i=0;i<n;i++)	{scanf("%d",&temp);insert(temp);}

k=0;
solve(root);
printf("%d",ans[0]);
for(i=1;i<k;i++)	printf(" %d",ans[i]);
printf("\n");
}
return 0;
}