hdu 3999-The order of a Tree（二叉樹の先序エルゴード）

http://acm.hdu.edu.cn/showproblem.php?pid=3999
The order of a Tree
Time Limit：2000/1000 MS（Java/Others）    メモリLimit：32768/32768 K（Java/Others）Total Submission（s）：1361    Acceepted Submission(s)：695
Problem Description
As we know，the shop 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 empy tree，the n 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 cal the order of keys we insert「the order of a tree」、your tass is、given a oder of a tree、find the order of a tree with the least lexicograp order that generame the same the same the the same and the the the same the find the the find the the find the same the find the the the the the the same the find the the find the the the find the find the re
 
Input
The e e are multile test cases in input file.The firs t line of each testcase is a n integer n(n==100,000)、represent the number of nodes.The second line has n intergers，k 1 to kn，represent the the oremader of
 
Output
One line with n intergers、which are the order of a tree that generate the same tree with the least lexicographc.
 
Sample Input
4 1 3 4 2
 
Sample Output
1 3 2 4
 
 
 
 
題名とは、数列を挿入して、一本の二叉樹を形成するという意味です。辞書の序文の一番小さい挿入方法を与えて、同じ木を建ててください。はっきり言って、先のシーケンスを求めます。
コード:

 1 #include <fstream>

 2 #include <iostream>

 3 

 4 using namespace std;

 5 

 6 typedef struct Node{

 7     Node *lch,*rch,*nex;

 8     int x;

 9     Node(int x){

10         this->x=x;

11         lch=NULL;

12         rch=NULL;

13     }

14 }inode;

15 

16 int n,tn;

17 inode *head;

18 

19 void insert(int t);

20 void preOrder(inode *p);

21 

22 int main()

23 {

24     //freopen("D:\\input.in","r",stdin);

25     //freopen("D:\\output.out","w",stdout);

26     int t;

27     while(~scanf("%d",&n)){

28         scanf("%d",&t);

29         head=new inode(t);

30         for(int i=1;i<n;i++){

31             scanf("%d",&t);

32             insert(t);

33         }

34         tn=0;

35         preOrder(head);

36     }

37     return 0;

38 }

39 void insert(int t){

40     inode *p=head,*s=new inode(t);

41     while(p!=NULL){

42         if(t<p->x)

43             if(p->lch!=NULL)    p=p->lch;

44             else{

45                 p->lch=s;

46                 break;

47             }

48         else

49             if(p->rch!=NULL)    p=p->rch;

50             else{

51                 p->rch=s;

52                 break;

53             }

54     }

55 }

56 void preOrder(inode *p){

57     if(p!=NULL){

58         printf("%d",p->x);

59         if(++tn<n)  printf(" ");

60         else    printf("
");

61         preOrder(p->lch);

62         preOrder(p->rch);

63         delete p;

64     }

65 }