/*
分析:
又是一个月黑风高的夜晚,终于。。。又可以刷题了,囧~,
十几分钟就能敲完的代码,白天愣是被打断了3、4次,终于敲完
了。。。
水~
其实就是把这个树构成,然后遍历一遍输出,遍历顺序就
是先root、然后左子树、然后右子树。
我这个建树的思想来自写的字典树,所以就分类到字典树
里面了。囧~~
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; }