（TOJ4406）二叉排序树

描述

输入一系列整数，建立二叉排序树并输出排序后的序列。

输入

输入数据有多组，每组数据第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。

输出

每组数据排序结果输出一行。每行最后一个数据之后有一个空格。

样例输入

5  
1 6 5 9 8 
8
4 6 9 2 5 4 7 3

样例输出

1 5 6 8 9
2 3 4 4 5 6 7 9

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <ctype.h>
 4 #include <math.h>
 5 
 6 typedef struct BiTNode{
 7     int data;       //数据域 
 8     struct BiTNode *lc,*rc;  //左右孩子指针 
 9 }BiTNode,*BiTree;
10 
11 BiTree InsertBST(BiTree T, int e)  //向排序二叉树T中插入新数据e 
12 {
13     BiTree f,p;
14     f=p=T;
15     while(p){
16         f=p;
17         p=(e<=p->data)?p->lc:p->rc;
18     }
19     p=(BiTree)malloc(sizeof(BiTNode));  
20     p->data=e;
21     p->lc=p->rc=NULL;
22     if(T==NULL)
23      T=p;
24   else
25   {
26       if(e<=f->data)
27         f->lc=p;
28       else
29         f->rc=p;
30   }
31   return T;
32 }
33 
34 void display(BiTree T)  //中序遍历并打印二叉排序树所有节点 
35 {
36     if(T){
37         display(T->lc);
38         printf("%d ",T->data);
39         display(T->rc);
40     }
41 }
42 
43 int main()
44 {
45     int n,t,i;
46     BiTree T;
47     while(scanf("%d",&n)!=EOF)
48     {
49         T=NULL;
50         for(i=0; i<n; i++)
51         {
52             scanf("%d",&t);
53             T=InsertBST(T,t);
54         }
55         display(T);
56         printf("\n");
57     }
58     return 0;
59 }
60